判断一个数能否被 7, 13, 17, 19 整除的方法

elimqiu

这些东西只有数论练习的价值.陆教授的方法的思路是一种截尾法.是比较实用的,其实相当于倒过来的除法. 我的分析给出了这种处理的一般方法.ccmmjj兄给出了一个不同的思路。值得仔细思考。

elimqiu

下面引用由ccmmjj在 2010/04/28 04:39pm 发表的内容： 说实话，在这方面，我是专家。比如说7和11及13，有一个统一的方法。 如123456788分割为123，456，788。然后计算123-456+788=455因为455能被7和13整除，所以123456788能被7和13整除；因为455不能被11整除，所以12 ...

大概明白了ccmmjj兄的理论。 我的理解是， 如果存在 k 使得 p|(10^k+1), 那么 p | n = a(m)(10^k)^m + a(m-1)(10^k)^(m-1)+...+a(1)10^k+a(0) 当且仅当 p | a(0)-a(1)+...+(-1)^m a(m) 其中 0≤a(i)<10^k 由于 7,11,13 皆能整除 1001 = 10^3 + 1, 所以 123456788分割为123，456，788。然后计算123-456+788=455... 容易知道，如果存在 k 使得 p|(10^k - 1)，那么 p | n = a(m)(10^k)^m + a(m-1)(10^k)^(m-1)+...+a(1)10^k+a(0) 当且仅当 p | a(0)+a(1)+...+a(m) 其中 0≤a(i)<10^k 这就是p = 3 或 9 的情况。

ccmmjj

对于其它类型，我也有分析过另一些处理方法（如截尾法）等。当时作为初一学生课外兴趣小组的课程教给他们。可惜没有留下讲义，不然的话可以请人打下来供人一噱。有一本书，可能很难找到，是丽水师专早年编的《初等数学复习与研究》。白白的书皮。分上下册。里面有这方面的部分内容。

lizh714285

[这个贴子最后由lizh714285在 2010/04/29 11:25am 第 2 次编辑]

从有限群方面出发，可以得到如下结论：
对于任意与10互质的自然数P， 都有类似于3楼陆老师形式的辨别法。
对应于P， 集合{1,2,3，....，p-1} 关于P的同余乘法构成一个群。
（“关于P的同余乘法”，定义为：对集合内任意两元所进行的普通乘法，其结果再除以P取余数）
如果10属于这个集合，则令r=10,否则，令r=10除以p的余数（譬如，当p=7时令r=3）
容易得到 r^(p-1)=r  （这里，乘方a^b的定义是对b个a连续施行“关于p的同余乘法”）   
--------------------
引用这个结论，本命题就得到： 一个自然数乘以10^(p-1)后与它自己同余于p。 换言之
elimqiu老师在12楼中所说“如果存在 k 使得 p|(10^k - 1)......”，这个k是存在的，它是p-1 （或p-1的一个因数）。
---------------------
（因为任何一个自然数去除P，获得的余数只能有p种情况，即：除尽，余1，余2,....余p-1；如果10与P互质，10,10^2,10^3，....10^(p-1);都不会被p整除，它们除以p的余数或者互不相同，分别取定前p-1个自然数，或者就会出现相同的情况，从而必定有一个余1，相同情况形成一种循环，各个余数会因此分组（所谓陪集）。）
————————————————————————————

设自然数Q=A*10^m+B  (其中A,B均为非负整数，m为自然数)
Q*10^(p-1)≡Q(mod p)
即: A*10^(m+p-1)+B*10^(p-1))≡A*10^m+B(mod p)
即: ( A + B*10^(p-1-m) ) *10^m ≡A*10^m+B(mod p)
取u,v;另u为10^(p-1-m)除以p的余数，v为10^m除以p的余数
( A + B*u) *v ≡A*10^m+B(mod p)
-------------------
如果不保具体余数不变，仅判断是否能整除，那么仅做变换：
A*10^m+B ∽ A+B*u  亦不失去能否被P整除性质。
其中 u为10^(p-1-m)除以p的余数。
检验一下：令P=7，m=1时，u=10^5除以7的余数，是5。
即截末位后，加上末位乘以5。（加上末位乘5和减去末位乘2，两步骤均不失能否被7整除的性质）
          令p=7,m=2； u=10^4除以7的余数，是4。
所以我在7楼写到
“一个数 将个、十两位截去， 然后加上（截去的两位数*4）”
如果要保余，这个变换要乘以u， 100/7余2,所以我主张这个变换再乘以2。
         令p=7,m=3； u=10^3除以7的余数，是6。
即截三位后，加上截去的数乘6。 加上尾数乘6和减去尾数，两步骤均不失能否被7整除的性质。
根据这一方法，任何与10互质的数P均可构造检验方法。
不失一般性，对于其它进制也能得到相类似的结论。

elimqiu

参见我的9楼的帖子
k 可以通过辗转相除法得到。
不错只要 (10^r, p) = 1, 就有相应的k
例如 p = 3, r = 1, 由 1x10-3x3=1 的 k = 1, 但也可以取与之同余的 -2
于是 314159265 → 11120202 → 1112020-4 = 1112016 → 111201 → 11120 - 2 = 11118 →11112 →1111 -4 = 1107 →1101→110-2=108→102→10-4 = 6 故 3 | 314159265
这里我用了截尾+削平法。 削平法把每位上的数都‘削平（减3的倍数）’到小于3的分上

白新岭

6楼luyuanhong教授证明13的整除性方法时有笔误的地方。那里显示的是被19整除，而不是被13整除。