初等数论《 整除 》 习题集 (连载 1)

目     录

前言：我为什么要做初等数论《整除》习题  ……   1

整除判断方法概述   …………………………………  1 —  4

习题   …………………………………………………  5 — 20

尾声小贴士   …………………………………………  20

 

 

前言：我为什么要做初等数论《整除》习题

 

数论是研究整数性质的一门理论。按照研究方法的难易程度来看，数论大致上可以分为初等数论（古典数论）和高等数论（近代数论）。

　　据《百度》，初等数论主要有以下几部分内容：(很惭愧，其中有些术语我还不大懂呢)

　1  整除理论。引入整除、因数、倍数、质数等基本概念。这一理论的主要成果有：欧几里德 的辗转相除法、算术基本定理、素数个数无限证明。  　　

 2  同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余 、 同余方程等概念。 主要成果：二次互反律、欧拉定理、费马小定理、威尔逊定理、孙子定理（即中国剩余定理）等等。  

 3  连分数理论。引入了连分数概念和算法等等。特别是研究了整数平方根的连分数展开。 主要成果：循环连分数展开、最佳逼近问题、佩尔方程求解。  　　

 4  不定方程。主要研究了低次代数曲线对应的不定方程，比如勾股方程的商高定理、佩尔方程的连分数求解。也包括了4次费马方程的求解问题等等。  　　

 5  数论函数。比如欧拉函数、莫比乌斯变换等等。

退休后学了一点《初等数论》的皮毛。其中“整除”算是初等数论中最基础、最简单的内容。但就是这看来最简单的整除，己经使我汗颜了，觉得自己不应该学《数论》，是在自找烦恼，但又像要坚持下去。几年来也做过一些习题。有关整除的算题，特别是证明题，真是无从下手。于是就拣自己能做的习题，集中的做了一些，算是整理一下学习成果，留一个纪念罢。以后还可以复习复习。

至于其他内容，如奇偶、余数、平方数、最大公约数、最小公倍数、同余、不定方程等等，是否也要出习题集，那就没有把握，只能看情况而定了。

 

整除判断方法概述

 

除数Z             被除数A能整除Z的条件，使A÷Z=N整数 ( Z∣A )         

2        末位上的数字是偶数 0、 2 、4、 6 、8  

3        各个数位上数字的和能被3整除

4       末两位数能被4整除 04  08  12  16  20 24  28  32 … 96。

5       末位上的数字是 0、 5

6       先判2，再判3

7       尾前数 减 尾数乘2，其结果被7整除。还有：

末三位上的数，与末三位以前的数，之差，能被7整除。即“前位减后三位=7的倍数”

8     末三位数能被8整除 008  016  096  104 … 992

9     各个数位上数字的和能被9整除

10     末位上的数字是 0

11     奇数位上的数字和，与偶数位数的数字和，它们之差，能被11整除。还有：

末三位上的数，与末三位以前的数，之差，能被11整除。即“前位减后三位=11的倍数”

12     先判4，再判3

13     尾前数 减 尾数乘9，其结果被13整除。还有：

       末三位上的数，与末三位以前的数，之差，能被13整除。即“前位减后三位=13的倍数”

14    先判2，再判7

15     先判5，再判3

16     末三位数能被16整除 0016  0032  0096 … 9984

17     尾前数 减 尾数乘 5，其结果被17整除

18     先判2，再判9

19     尾前数 加 尾数乘  2，其结果被19整除

21     尾前数 减 尾数乘  2，其结果被21整除

23     尾前数 减 尾数乘16，其结果被23整除

尾前数 加 尾数乘  7，其结果被23整除

25     末两位数能被25整除 00  25  50  75

27     从尾起，向左三位为一段、每段相加，得和数，能被27整除

28     先判4，再判7

37     从尾起，向左三位为一段、每段相加，得和数，能被37整除

73     从尾起，向左四位为一段、每段相加，得和数，能被73整除

125     末三位数能被125整除 000  125  250  375 …  875

137     从尾起，向左四位为一段、每段相加，得和数，能被137整除

 

以9为尾的数：

09  尾前数 加 尾数乘1，其结果被  9整除

19  尾前数 加 尾数乘2，其结果被19整除

29  尾前数 加 尾数乘3，其结果被29整除

39  尾前数 加 尾数乘4，其结果被39整除

49  尾前数 加 尾数乘5，其结果被49整除

59  尾前数 加 尾数乘6，其结果被59整除

69  尾前数 加 尾数乘7，其结果被69整除

79  尾前数 加 尾数乘8，其结果被79整除

89  尾前数 加 尾数乘9，其结果被89整除

99  从尾起，向左二位为一段、每段相加，得和数，能被99整除

 

以1为尾的数：

11  尾前数 减 尾数乘1，其结果被11整除

21  尾前数 减 尾数乘2，其结果被21整除

31  尾前数 减 尾数乘3，其结果被31整除

41  尾前数 减 尾数乘4，其结果被41整除 

51  尾前数 减 尾数乘5，其结果被51整除

61  尾前数 减 尾数乘6，其结果被61整除

71  尾前数 减 尾数乘7，其结果被71整除

81  尾前数 减 尾数乘8，其结果被81整除

91  尾前数 减 尾数乘9，其结果被91整除

综合而言，判别整除的方法有5类 ：

1  尾数判别法：判别能被2、4、8、5、25 整除。

2  数字和、差判别法：判别能被3、9、11整除。

3  《 尾前数 减 尾乘k 》或《尾前数 加 尾乘G 》的通用判别法：判别能被7、11、13、17、19、 23、29、31 … 等所有质数整除。

 

不同质数有不同的k与G，见下表：

 

P     7    11    13    17   19    23   29    31    37   41    43   47   53   59   61 

－K     2     1      9      5   17    16   26      3    11    4     30   14    37   53     6

   ＋G                                     2      7     3                                                   6

 

P      67    71     73    79    83    89    97    101  

－K      20     7     51    71    58    80    29      10 

＋G                     22      8     25     9

 

例一  55369÷17能整除吗？采用《 尾前数 减 尾乘k 》法，K=5，有：

55369  →  5536－9×5=5491  →  549－1×5=544   →  54－4×5=34，

  →  34÷17=2   已整除  →  17∣34，所以17∣55369 。

例二  28382÷23能整除吗？采用《 尾前数 加 尾乘G 》法，G=7，有：

28382  → 2838＋2×7=2852  →  285＋2×7=299  →  29＋9×7=92

→  9＋2×7=23   →  23∣23  →  所以23∣28382

 

 

4        分两段相减判断法：当一个大数超过三位时，便从尾起，向左三位一分、或四位一分，将数字分为两段，再以大段减小段，得余数。再判断其余数能否被7、11、13 (三位一段 )、或73、137  ( 四位一段 ) 整除。

 

                                                             一   深层原因

因为  7×11×13 = 1001       73×137 = 10001      11×9091 = 100001  

二   分两段相减判断法及实例

 例一  2336754，能否分别被7、11、13整除。

1  2336754三位一分，相减得余 →  2336－754=1582 → 再三位一分 → 1  582 →  582－1=581

2  判断： 581÷7=83      整除    所以2336754能被7整除

581÷11=52.81 不整除   所以2336754不能被11整除

581÷13=44.69 不整除   所以2336754不能被13整除

例二：  46637583能被73整除吗？能被137整除吗？

由于73×137＝10001，所以要四位一分，分段相减判断法是：

1、  46637583  → 分7583、4663 两段  →  7583－4663 = 2920

2、  2920÷73 = 40      已整除， 即 73∣46637583

3、  2920÷137=21.31   不整除， 即137ト46637583

 

 

三  分两段相减判断法的原理。以7×11×13=1001为例

整数ABCDEF可分柝：

ABCDEF=ABC×1000＋DEF= ABC×1000＋DEF＋ABC－ABC=ABC×1001＋DEF－ABC

由于(ABC×1001)中含有因数7、11、13，所以(ABC×1001)必定能被7、11、13整除，就不必去试除了，只剩下(DEF－ABC)去试除，如果被7整除了，也就是ABC×1001＋DEF－ABC能被7整除。ABCDEF能被7整除。其余11、13亦相同。看数值分析：

例一中 2336754=233×1000＋754=233×1000＋754＋233－233=233233＋(754－233)

233233÷1001=233233÷(7×11×13)=233整除了，剩下，只要判别 (754－233) 能否被7、11、13整数就可以了。

至于整除73、137的原理与上相仿，因为73×137=10001，所以要四位一分。

又因为11×9091=100001，所以整除9091时，要五位一分。如此而已。

 

5  分多段相加判断法：将一个大数，从尾起，向左二位一段，或三位一段 、或四位一段、或五位一段的分、分为多段，再多段一起相加，得和数，再判断其和数能否被99(二位一段)、27 、37(三位一段)、101(四位一段)、41、271(五位一段)整除。如果能被整除，则该大数也能被整除。

               一   深层原因

因为  9×11= 99     27×37 = 999     11×101 = 9999   41×271=99999 

                           二   分多段相加判断法及实例

 例一：  332517537能被9整除吗？能被11整除吗？能被99整除吗？

1         分段：判99要二位一段。332517537，从尾起向左分作3  32  51  75  37 ，

2  各段相加，得和数，3+32+51+75+37=198  超过二位，再分位 →  1   98   →  1+98=99

3  判断： 99÷9=11  整除   所以332517537能被9整除

99÷11=9  整除   所以332517537能被11整除

99÷99=1  整除   所以332517537能被99整除

 

例二：  1013931能被27整除吗？能被37整除吗？

由于27×37 = 999，所以要三位一分：

1  1013931分作  1  013   931

2  1＋13＋931=945 

3  945÷27=35  整除。即27∣1013931

4  945÷37=25.54  有余数，不整除，即 37ト1013931

 

三  分多段相加判断法的原理。以27×37=999三位一段为例。

整数ABCDEF可分柝：

ABCDEF=ABC×1000＋DEF= ABC×1000＋DEF－ABC＋ABC=ABC×999＋(ABC＋DEF)

由于(ABC×999)中含有因数27、37，所以(ABC×999)必定能被27、37整除，就不必去试除了，只剩下(DEF＋ABC)需要去试除。如果被27整除了，也就是ABCDEF能被27整除。对37亦相同。

  看数值分析：

例二中1013931 =1013×1000+931=1013×999+1013+931=1013×999+1944

1013×999不必判了，要判1944，这里要两次分位。而1944=1×1000+944=999+1+944=999+945

999不必判了，最后只要判945能否整数27、37就可以了，也变得简单多了。( 待 续 )