博文
整数相除求商取余的一种新思路
||
一、引言
整数除法，特别是判断整除、取余的方法，一直是受人们关注和讨论的热点。除法从本质上可以理解为减法，也有认为是加法、乘法，也就是说可以把除法运算转化为减法、加法或乘法运算。例如：
862/7
=(700+(862-700))/7
=100+162/7
=100+(140+22)/7
=100+20+(21+1)/7
=100+200+3+1/7
=123…1
近期辅导小朋友数学作业，看到笔记本上整理的老师教的关于快速判断一个整数能被特殊整数整除的简便方法，如：
ü 如果一个整数的所有数字之和能被3整除，则这个数能被3整除；
ü 如果一个整数的个位为0或5，则这个数能被5整除；
ü 如果一个整数的所有数字之和能被9整除，则这个数能被9整除；
ü 如果一个整数所有奇数位的数字之和所有偶数位的数字之和的差能被11整除，那么这个数能被11整除；
ü .....
突然萌生了一个想法：能不能找到一种更为普适、能够（较为）简便地判断一个整数能否被另一个整数整除的方法呢？
朝着这个小目标，经过一番冥思苦想，终有所发现收获，特整理出来，与大家分享。
PS：研究过程中，看到阿里巴巴的数据库专家叶正盛(MKing)先生与2008年发表的一篇名为“如何快速判断一个整数是否可以整除另一个整数的理论分析”的博文（https://blog.csdn.net/yzsind/article/details/2412328），与本文“取余新思路”部分的研究有异曲同工之妙，本质上都是利用余数的加法定理、乘法定理，将被除数从一个较大数降为一个对除数同余的较小数，从而达到更容易判断是否整除或取余的目的。本文中的一些描述和案例借鉴了叶正盛先生的博文，致敬叶正盛先生无私分享！
二、取余新思路
首先，做如下规定：
（1）设X为一个n+1（n为正整数）位的十进制正整数，表示为：X=XnXn-1….X2X1X0。其中，X0为X的个位（100），X1为X的十位（101），X2为X的百位（102），Xn为X的从右向左第n+1位（10n）。因此，X=X0+X1*101+X2*102+……+Xn*10n。例如，如X=862=2+6*101+8*102。
（2）m为一个十进制正整数，10-m为m的（十）补数，记为m。
（3）“%”为求余数的运算符号。
根据余数的加法定理和乘法定理：
10%m
=(m+(10-m))%m
=m%m
进而：
X%m
=(X0*100+X1*101+X2*102+……+Xn*10n)%m
=(X0+X1*(101%m)+X2*(102%m)+……+Xn*(10n%m))%m
=(X0+X1*(m1%m)+X2*(m2%m)+……+Xn*(mn%m))%m
=(X0+X1*m1+X2*m2+……+Xn*mn)%m
即：
X%m=(X0+X1*m1+X2*m2+……+Xn*mn)%m
（当然，可以根据上述公式括号中数值的大小，决定是否再运算一次。）
这或许可以视为余数的三大定理之外的又一个定理，暂称之为“换补同余定理”，相应运算称之为“换补取余运算”。
根据换补同余定理，可以验证前文提到的关于快速判断一个整数能被特殊整数整除的简便方法。
（1）如果一个整数的所有数字之和能被3整除，则这个数能被3整除。
X%3
=(X0+X1*71+X2*72+……+Xn*7n)%3
由于71%3=1，72%3=1…..，7n%3=1，所以：
X%3
=(X0+X1+X2+……+Xn)%3
（2）如果一个整数的所有数字之和能被9整除，则这个数能被9整除。
X%9
=(X0+X1*11+X2*12+……+Xn*1n)%9
=(X0+X1+X2+……+Xn)%9
（3）如果一个整数的个位为0或5，则这个数能被5整除。
X%5
=(X0+X1*51+X2*52+……+Xn*5n)%5
=X0%5
（4）如果一个整数所有奇数位的数字之和所有偶数位的数字之和的差能被11整除，那么这个数能被11整除。
X%1
=(X0+X1*(-1)1+X2*(-1)2+……+Xn*(-1)n)%1
（5）如果一个整数的个位数的1倍、10位数的2倍、百位数的4倍，三者之和能被8整除，则这个数能被8整除。
X%8
=(X0+X1*21+X2*22+X3*23+……+Xn*2n)%8
=(X0+X1*2+X2*4)%8
（6）当除数为7时
X%7
=(X0+X1*31+X2*32+……+Xn*3n)%7
（7）当除数为12时
X%1
=(X0+X1*(-2)1+X2*(-2)2+……+Xn*(-2)n)%1
上面的证明和举例中，被除数和除数均默认限定为十进制，补数亦为十补数。但上述方法同样适用于被除数为其他进制的情况。补数需要变为相应的百补数、千补数等。不过，除数保持十进制。例如，扩展到百进制，可以证明。
（8）将一个整数的各位数从右向左依次切分，两位一组（相当于一个十进制的二位数），从十进制变为百进制。如果（从右向左）各组数字之和能被99整除，则这个数能被99整除。
X%99
=((X0+X1*10)+(X2+X3*10)*11+(X4+X5*10)*12+……)%99
=((X0+X1*10)+(X2+X3*10)+(X4+X5*10)+……)%99
（9）将一个整数的各位数从右向左依次切分，两位一组（相当于一个十进制的二位数），从十进制变为百进制。如果（从右向左）所有奇数组数字之和与所有偶数组数字之和的差能被101整除，那么这个数能被101整除。
X%101
=((X0+X1*10)+(X2+X3*10)*(-1)1+(X4+X5*10)*(-1)2+……)%99
=((X0+X1*10)-(X2+X3*10)+(X4+X5*10)-……)%99
再如，扩展到千进制，可以证明。
（10）将一个整数的各位数从右向左依次切分，三位一组（相当于一个十进制的三位数），从十进制变为千进制。如果（从右向左）各组数字之和能被999整除，则这个数能被999整除。
（11）将一个整数的各位数从右向左依次切分，三位一组（相当于一个十进制的三位数），从十进制变为百进制。如果（从右向左）所有奇数组数字之和与所有偶数组数字之和的差能被1001整除，那么这个数能被1001整除。
上述方法同样适用于其他任意进制的情况。比如，假设除数为47，可以首先将被除数转换为50进制，然后取47的五十补数（3），就可以利用上述方法计算出余数。当然，这仅为一种思路，实际的计算过程可能会反而变得更繁琐，得不偿失。
三、求商新思路
上一节论证了关于整数相除的换补同余定理，提出了一种普适的整数相除取余的新思路，并进行了举例说明，但尚未解决整数相除求商的问题。本节将对此进行讨论。
首先需要引出、论证关于整数相除进行换补求商取余运算前后被除数数值变化相对除数的倍数的定理，暂称之为“换补差倍定理”
还是如上节规定，X=Xn….X3X2X1X0为10进制n+1位正整数，X=X0*100+X1*101+X2*102+……+Xn*10n。
规定：对于任何非负整数n，f(10,m,n)=(10n-mn)/m（10为进制，扩展至100进制亦适用）。例如，f(10,m,0)=(100-m0)/m=0，f(10,m,1)=(101-m1)/m=1。
可以看出，在进行换补求商取余运算前后，被除数右边第1位（个位）的数值是没有变化，从第2位开始会有变化。对于任何正整数n，可以得到：
f(10,m,n)
=(10n-mn)/m
=((10n-10mn-1)+(10mn-1-mn))/m
=(10*(10n-1-mn-1)+mn-1*(10-m))/m
=10*f(10,m,n-1)+mn-1。
例如，
f(10,m,1)=10*f(10,m,0)+m0=1
f(10,m,2)=10*f(10,m,1)+m1=10+m
f(10,m,3)=10*f(10,m,2)+m2=10(10+m)+m2=100+10m+m2
f(10,m,4)=10*f(10,m,3)+m3=10(100+10m+m2)+m3=1000+100m+10m2+m3……
可以进一步推导出，f(10,m,n)=(10n-mn)/m=10n-1m0+10n-2m1+10n-3m2+……+101mn-2+100mn-1=10n-1+10n-2m1+10n-3m2+……+10mn-2+mn-1。
结合上节论证的换补同余定理，可以得到：
X/m
=(X0*100+X1*101+X2*102+……+Xn*10n)
=(X1*(101-m1)+X2*(102-m3)+……+Xn*(10n-mn))/m+(X0+X1*m1+X2*m2+……+Xn*mn)/m
=X1*(101-m1)/m+X2*(102-m3)/m+……+Xn*(10n-mn)/m+(X0+X1*m1+X2*m2+……+Xn*mn)/m
= X1+X2*(10+m)+ ……+Xn*(10n-1+10n-2m1+10n-3m2+……+10mn-2+mn-1)+(X0+X1*m1+X2*m2+……+Xn*mn)/m
例如（10进制）：
4538/8
=3+5*(10+2)+4*(100+20+4)+(8+3*21+5*22+4*23)/8
=559+66/8
=559+8……2
=567……2
再如（100进制）：
31816/97
=18+3*(100+3)+(16+18*31+3*32)/97
=327+(97)/97
=328
四、讨论
本文尝试探索了整数相除求商取余的一种新思路，基本思路可以归结为“换补同余”思想。
当然，正如文中提到的，这仅仅是整数相除求商取余的一个“可行”思路而已。当除数为进制数值（10、100、1000等）附近的整数时，或许可以提高手算整数相除求商取余，特别是取余的效率，但大多数情况下可能会反而得不偿失。
本文纯属有感而生，本人并非数学研究人员，亦未开展深入文献调研，文中错误、遗漏、不严谨之初，还请专家斧正！
马廷灿
2021年3月13日晚
于武昌●茶港
https://blog.sciencenet.cn/blog-5168-1276581.html
上一篇：朗缪尔1918年关于固体表面气体吸附的论文
下一篇：新文分享：引文分布指数及其在论文长期影响测量中的应用
