关于十以内整数的整除性小证明

上厕所时无聊想到的，其实也很简单。

定义

mod 取余

div 整除（不习惯的可看作 \ ）

1不用讨论了。



先讨论2，4.

众所周知，对于整数n，

（n mod 10）mod 2=0 ----> n mod 2=0

(n mod 100) mod 4=0 ----> n mod 4=0

第一个好理解，只要是偶数，就能被2整除；但第二个为什么呢？

我们可以把n变成(n div 100)*100 + n mod 100
因为(n div 100)*100 中100是可以被4整除的，因此只要保证n mod100能被4整除就行了。
推广开来，10^n=2^n*5^n，因此要看2^n能否整除k，只需看k的后n位能否被2^n整除。
同理对于5^n也是一样道理。
比如说，对于123457694575该数来说，是明显能被5整除的，那么25行不行呢？我们只需看后两位75 mod 25=0，所以该数能被25整除。

对于3.
为什么只要n各位数加起来和能被3整除，那么n mod 3=0呢？
事实上，道理和上述差不多。
假设n为k位数
则n=n[k]*10^(k-1)+...+n[2]*10+n[1]*1 .........（I式）
因为对于10^n（n>=0）来说，其mod 3一定等于1.因此我们可以利用同余的方法将I式转化成
m=1*（n[k]mod 3）+1*(n[k-1]mod 3)+..+(n[1]mod 3)，只要m=0，那么n mod 3=0。因此事实上求各位数和除3余数本质是求各位数余数之和。9同理可证。
那么27是否也拥有这种性质呢？很明显没有。因为10^n mod 27不一定为1.我们也可以举个反例，如9918，9+9+1+8=27，9918 mod 27>0。

对于6，只需判断2和3的性质是否同时满足。

对于7，这个相对比较麻烦。
我们可以借鉴3的那个性质来讨论。
1 mod 7=1
10 mod 7=3
100 mod 7=2
1000 mod 7=6
10000 mod 7=4
100000 mod 7=5
1000000 mod 7=1
.....................
可以发现132645六个数为一个周期出现，因此我们只需对应求其乘起来的和mod 7。
如一个数 n=abcdefg 对应的是1546231（要反过来写）则S=a*1+b*5+c*4+d*6+e*2+f*3+g*1
S≡n mod 7
或许有人会觉得这六个数会忘记，没戏都要除6次得到这六个数，很麻烦。
其实若记不住，可以用另一种方法得到。
142857这六个数想来印象应该更深一些。
只需要记得第一位为1，第二位变为10-7*1=3，第三位为10-(7*4)mod 10。。最后一位7重复，按这样便可得到这六个数。