1、第六讲 能被 30 以下质数整除的数的特征大家知道,一个整数能被 2 整除,那么它的个位数能被 2 整除;反过来也对,也就是一个数的个位数能被 2 整除,那么这个数本身能被 2整除.因此,我们说“一个数的个位数能被 2 整除”是“这个数能被 2 整除”的特征.在这一讲中,我们通过寻求对于某些质数成立的等式来导出能被这些质数整除的数的特征。为了叙述方便起见,我们把所讨论的数 N 记为:有时也表示为我们已学过同余,用 mod2 表示除以 2 取余数 .有公式:Na0 (mod2)Na1a0(mod4)Na2a1a0 (mod8)Na3a2a1a0(mod16)这几个公式表明一个数被 2(4,8,1
2、6)整除的特性,而且表明了不能整除时,如何求余数。此外,被 3(9)整除的数的特征为:它的各位数字之和可以被3(9)整除.我们借用同余记号及一些运算性质来重新推证一下.如(mod9),如果,N=a 3a2a1a0=a31000+a2100+a110+a0a 3( 9991) a2(99+1)a 1(9+1)+a 0(a 3+a2+a1+a0)+(a 3999+a299+a19),那么,等式右边第二个括号中的数是 9 的倍数,从而有Na 3 a2+a1+a0(mod9)对于 mod3,理由相仿,从而有公式:N(a 3a 2a 1a 0)(mod9),N(+a 3a 2a 1a 0)(mod3)。
3、对于被 11 整除的数,它的特征为:它的奇位数字之和与偶位数字之和的差(大减小)能被 11 整除。先看一例.N=31428576 ,改写 N 为如下形式:N=67(11-1)5(991)8(1001-1)2(99991)4(100001-1)+1(999999+1)+3(10000001-1)=6-7+5-8+2-4+1-3+711+59981001+29999+4100001+1 999999310000001。由于下面这两行里,11、99、1001、9999、100001、999999、10000001 都是 11 的倍数,所以N=6-75-82-4 1-3(mod11)。小学生在运算时,
4、碰上“小减大”无法减时,可以从上面 N 的表达式最后一行中“借用”11 的适当倍数(这样,最后一行仍都是 11 的倍数),把它加到“小减大”的算式中,这样就得到:N116-75-8 2-4 1-3 3(mod11)。现在总结成一般性公式(推理理由与例题相仿).则 N(a0-a1+a2-a3a4-a5 a6-a7+)(mod11)或者:N(a0+a2+a4+ )- (a1+a3+a5+)(mod11 )(当不够减时,可添加 11 的适当倍数)。因此,一个自然数能被 11 整除的特征是:它的奇位数字之和与偶位数字之和的差(大减小)能被 11 整除。我们这里的公式不仅包含整除情况,还包含有余数的情况
5、。下面研究被 7、11、13 整除的数的特征。有一关键性式子:71113=1001。所以 N 能被 7、11、13 整除,相当于能被 7、11、13 整除.总结为公式:(mod11);(mod13)当倍数)。表述为:判定某数能否被 7 或 11 或 13 整除,只要把这个数的末三位与前面隔开,分成两个独立的数,取它们的差(大减小),看它是否被 7 或 11 或 13 整除。此法则可以连续使用。例:N=31428576.判定 N 是否被 11 整除。因为 822 不能被 11 整除,所以 N 不能被 11 整除。例:N215332.判定 N 是否被 7、11、13 整除。由于 117139,所以
6、 117 能被 13 整除,但不能被 7、11 整除,因此 N 能被 13 整除,不能被 7、11 整除。此方法的优点在于当判定一个较大的数能否被 7 或 11 或 13 整除时,可用减法把这个大数化为一个至多是三位的数,然后再进行判定。如 N987654321.判定 N 能否被 13 整除?而 654=5013+4,所以原数不能被 13 整除.如直接计算,很费力:987654321=75973409134。下面研究可否被 17、19 整除的简易判别法.回顾对比前面,由等式100171113 的启发,才有简捷的“隔位相减判整除性”的方法.对于质数 17,我们有下面一些等式:176102,175
7、9=1003,17588=9996 ,175882=99994 ,我们不妨从 1759=1003 出发。因此,判定一个数可否被 17 整除,只要将其末三位与前面隔开,看末三位数与前面隔出数的 3 倍的差(大减小)是否被 17 整除。例:N=31428576,判定 N 能否被 17 整除。而 429=2517+4,所以 N 不能被 17 整除。例:N2661027 能否被 17 整除?又 935=5517。所以 N 可被 17 整除。下面来推导被 19 整除的简易判别法。寻找关键性式子:1952=988,1953=1007.因此,判定一个数可否被 19 整除,只要将其末三位与前面隔开,看末三位与
8、前面隔出数的 7 倍的差(大减小)是否被 19 整除。例:N123456789 可否被 19 整除?又 6033119+14,所以 N 不能被 19 整除。例:N=6111426 可否被 19 整除?又 57=319,所以 N 可被 19 整除:321654 19=6111426。下面来推导被 23、29 整除的简易判别法。寻找关键性式子,随着质数增大,简易法应该在 N 的位数多时起主要作用,现有2343510005,29345=10005,由此启发得到一个末四位隔开的方法:因此,判定一个数可否被 23 或 29 整除,只要将其末四位与前面隔开,看末四位与前面隔出数的 5 倍的差(大减小)是否被 23 或 29 整除。例:N6938801 能否被 23 或 29 整除?又 53362323223298,所以很快判出 N 可被 23 及 29 整除。最后,如读者还想寻找以上数的更简明判别法,或被 31 以上质数整除的判别法,都是可以去探索的.把这一节得到的公式简列于下:(可在上述这些同余式的右端加上相应质数的适当倍数).后两式没有证明,读者不难从 999=3727,9923132 启发出“隔位加”的判别法。