截尾法判断整除——同余定理的应用

上一篇我们推导出了质数17的截尾法公式，我们看看19。

如果M=10a+b能够被19整除，那么2(10a+b)也可以被19整除，而2(10a+b)=20a+2b=19a+a+2b，19可以整除19(废话)，因此，M=10a+b与a+2b对19同余。也就是截断M的尾数后，还要加上尾数的2倍，如果结果能被19整除，那么原数就能被19整除。

下面不细致描述了，直接解出剩下质数的规则。

(10a+b) Mod 23 = 7(10a+b) Mod 23=(70a+7b) Mod 23 = (69a+a+7b) Mod 23 = (a+7b) Mod 23，截尾后加上尾数的7倍

(10a+b) Mod 29 = 3(10a+b) Mod 29=(30a+3b) Mod 29 = (29a+a+3b) Mod 29 = (a+3b) Mod 29，截尾后加上尾数的3倍

(10a+b) Mod 31 = 3(10a+b) Mod 31=(30a+3b) Mod 31 = (31a-a+3b) Mod 31 = (a-3b) Mod 31，截尾后减去尾数的3倍

(10a+b) Mod 37 = 11(10a+b) Mod 37=(110a+11b) Mod 37 = (111a-a+11b) Mod 37 = (a-11b) Mod 37，截尾后减去尾数的11倍

(10a+b) Mod 41 = 4(10a+b) Mod 41=(40a+4b) Mod 41 = (41a-a+4b) Mod 41 = (a-4b) Mod 41，截尾后减去尾数的4倍

(10a+b) Mod 43 = 13(10a+b) Mod 43=(130a+13b) Mod 43 = (129a+a+13b) Mod 43 = (a+13b) Mod 43，截尾后加上尾数的13倍

(10a+b) Mod 47 = 14(10a+b) Mod 47=(140a+14b) Mod 47 = (141a-a+14b) Mod 47 = (a-14b) Mod 47，截尾后减去尾数的14倍

如果得到的结果能被对应的质数整除，那么原数也能整除该质数。其实，7,11,13，也可以用截尾法，只是计算量比较大，不如三位划分方便，现把规则也列如下：

(10a+b) Mod 7 = 2(10a+b) Mod 7=(20a+2b) Mod 7 = (21a-a+2b) Mod 7 = (a-2b) Mod 7，截尾后减去尾数的2倍

(10a+b) Mod 11 = (11a-a+b) Mod 11 = (a-b) Mod 11，截尾后减去尾数

(10a+b) Mod 13 = 4(10a+b) Mod 13=(40a+4b) Mod 13 = (39a+a+4b) Mod 13 = (a+4b) Mod 13，截尾后加上尾数的4倍

截尾法测试一个数是否能被一个质数p整除，就讨论这么多了。其实这个算法还可以推演到更大的质数，原理是相同且有效的。为了说明这种方法的普适性，博主把剩下100内的质数截尾法的公式推导如下，网友们很容易就能辅导孩子熟悉和判断整除了：

(10a+b) Mod 53 = 16(10a+b) Mod 53=(160a+16b) Mod 53 = (159a+a+16b) Mod 53 = (a+16b) Mod 53，截尾后加上尾数的16倍

(10a+b) Mod 59 = 6(10a+b) Mod 59=(60a+6b) Mod 59 = (59a+a+6b) Mod 59 = (a+6b) Mod 59，截尾后加上尾数的6倍

(10a+b) Mod 61 = 6(10a+b) Mod 61=(60a+6b) Mod 61 = (61a-a+6b) Mod 61 = (a-6b) Mod 61，截尾后减去尾数的6倍

(10a+b) Mod 67 = 20(10a+b) Mod 67=(200a+20b) Mod 67 = (201a-a+20b) Mod 67 = (a-20b) Mod 67，截尾后减去尾数的20倍

(10a+b) Mod 71 = 7(10a+b) Mod 71=(70a+7b) Mod 71 = (71a-a+7b) Mod 71 = (a-7b) Mod 71，截尾后减去尾数的7倍

(10a+b) Mod 73 = 22(10a+b) Mod 73=(220a+22b) Mod 73 = (219a+a+22b) Mod 73 = (a+22b) Mod 73，截尾后加上尾数的22倍

(10a+b) Mod 79 = 8(10a+b) Mod 79=(80a+8b) Mod 79 = (79a+a+8b) Mod 79 = (a+8b) Mod 79，截尾后加上尾数的8倍

(10a+b) Mod 83 = 25(10a+b) Mod 83=(250a+25b) Mod 83 = (249a+a+25b) Mod 83 = (a+25b) Mod 83，截尾后加上尾数的25倍

(10a+b) Mod 89 = 9(10a+b) Mod 89=(90a+9b) Mod 89 = (89a+a+9b) Mod 89 = (a+9b) Mod 89，截尾后加上尾数的9倍

(10a+b) Mod 97 = 29(10a+b) Mod 97=(290a+29b) Mod 97 = (291a-a+29b) Mod 97 = (a-29b) Mod 97，截尾后减去尾数的29倍

再大就不推演了，其实50以后的质数的整除性，现实中已经用的很少了。我们用一个简单的C#代码（其他如php，Java，python也类似）来计算质数p的截尾法参数算法如下：

static int GetPrimeRuleParam(int prime)
{
        switch(prime % 10)
        {
                case 3: return (prime * 3 + 1) / 10;
                case 9: return (prime + 1) / 10;
                case 7: return -(prime * 3 - 1) / 10;
                case 1: return -(prime-1) / 10;
                default: return 0;
        }
}