题目

关于数学中整除的割尾法

提问时间：2021-02-27

答案

割尾,顾名思义,是指用数的高位形成的数-低位数(常用最后的个位)形成的数的倍数.割,就是减；尾,就是低位形所的数.
整除的割尾法,就是用上述方式所得数的整除性来判别原数的整除性.
以除数7为例,原理是这样：
10a+b==0 mod 7 注：即对于除数(模)7余数为0,亦即整除
-2(10a+b)==0==a-2b
也就是说,一个数x=10a+b被7整除,等价于十位数及其前面数字构成的数-个位数的2倍被7整除,这便是割尾,并可以迭用.
如1624,变成162-8=154,再变成15-8=7,最后7被7整除,从而原数被7整除.
实际上,其实使用并不方便,并没有一步到位,减法过程中还有借位,判别效率并不高.并且如果要割去的倍数为较多倍,也不便于计算.
同时,称作割,强调了减法,在术语上是有局限的；同类的方法,并不排除加法.
如判别对于除数13的整除性,利用到4*(10a+b)=a+4b.就以13本身为例,1+3*4被13整除,等价于13被13整除.
我们还可以不限于最后的个位.如
100a+b==0 mod 7 2a+b==0 mod 7,于是可以从高位向低位处理,这样不但可以判别整除性,还可以直接求得余数.
再如1000a+b==-a+b,我们可以将一个多位数三位一分段,各段构成的数加减交替,最后得到一个三位数；于是只需判别这个三位数的整除性或求余.
此外,如果我们不是判别整除性,而是为了求余,怎么办?
那就是洪伯阳方法,使用分数来计算余数,利用分数的性质,比例的性质,同余的性质,综合为用,效率很高.
以除数(模7)为例.
20a=-a mod 7,计作10a=a/(-2)=-a/2 mod 7.
并且可以化为带分数(整数加分数),分子与分母还可以同时乘相同的数,还可以
在分子或分母上加减除数7的任意倍数,还可以利用合分比定理,而所得余数不变.
譬如求1253 mod 7==(-6+5)*10+3==0 mod 7
36245 mod 7==(((-18)+2)/(-2)+4)/(-2)+5==-6+5==6
当然可以利用100a==2a,及3*2a==-a的改写式2a==-a/3==100a来作：
36245 mod 7==(72+24)/(-2)+5==(-2)/(-2)+5=6
或者(-12+24)/(-2)+5==-6+5==6