数论基础 

第五章 数论基础

5.1 基本要求

1. 掌握整除、因数、倍数等概念，记住并会应用整除的性质。

2. 掌握最高公因数的概念，能够使用辗转相除法求两个数的最高公因数并表示为

它们的倍数和。会利用数的数码特征判别某些整除性。

3. 掌握互质的概念和质数的性质。掌握质数、合数的概念以及算术基本定理、欧几里德定

理。

4. 掌握合同的概念以及合同的基本性质。

5. 掌握剩余系、剩余类的概念。了解一次合同方程在什么条件下有解、什么条件下无解、

什么时候有唯一解（一个剩余类）、什么时候有多解（多个剩余类），并对有解的情况掌 握求解方法。

6. 掌握秦九韶定理(及其推广)、合同方程组的一般解法。

7. 掌握简化剩余系、Euler函数、Euler函数的可乘性、欧拉定理、费尔马定理。

8. 掌握二次同余的概念、二次同余方程的判定和求解、勒让德符号、欧拉判别法则。 9. 了解合同在计算机编码中的应用。

5.2 主要解题方法

5.2.1 关于整除的问题

这部分习题主要是应用整除的性质。整除的性质教材中列举得已经很详细，比如，若在一等式中，除某项外，其余各项都是a的倍数，则此项也是a的倍数，等7条。

下面一些例题中还常用到质数的一个性质如教材中定理5.2.5所述：若质数p整除a1a2…an，则p整除a1，a2，…，an之一。

关于使用辗转相除法求两个数a，b的最高公因数并表示为它们的倍数和，在教材中已有实例和习题，不再举例，需要使用的主要公式如下：

S0=0，S1=1，T0=1，T1=q1。

以及

Sk = qkSk-1+Sk-2 ， Tk = qkTk-1+Tk-2。

若使用辗转相除法到某一步有rn-1=qn+1rn，则rn即最高公因数d，且

d=(-1)n-1Sna+(-1)nTnb。

例5.2.1 对于同样的整数x和y，表达式

2x+3y，9x+5y

同时能被17整除。

证明：设

u=2x+3y，v=9x+5y。 （1）

往证对于能使17|u的整数x和y，也能使17|v，反之亦然。

由（1）式可得：

3v-5u=17x，

故，

3v=5u+17x， （2） 5u=3v-17x。 （3）

由（2）式知，如果整数x，y能使17|u，则由教材中整除性质2有：17|5u，又因为17|17x，所以由整除性质5有：17|3v。而17是质数，由定理5.2.5知，17必整除3和v之一，显然，17不整除3，故必有17|v。

同理，由（3）式知，如果整数x，y能使17|v，则由教材中整除性质2有：17|3v，又因为17|17x，所以由整除性质5有：17|5u。而17是质数，由定理5.2.5知，17必整除5和u之一，显然，17不整除5，故必有17|u。

例5.2.2 证明：对于一切整数n，n?2n?12均不是121的倍数。 证明：使用反证法。

假设存在整数n，使得n?2n?12是121的倍数。故，有整数k，使

22n2?2n?12=121k。

即

(n?1)2+11=11×11k。

于是，有

。 （a） (n?1)2=11（11k-1）

又由11|11（11k-1）及整除性质5，知：

11|(n?1)2。

由于11是质数，由定理5.2.5知，11|(n+1)。于是，112|(n?1)2，又由（a）式及整除的性质5知，112|11（11k-1）。故，11|（11k-1），从而有11|-1，这显然是不可能的，因此原假设不对，对于一切整数n，n?2n?12均不是121的倍数。

例5.2.3 设a，b是整数，试证明：如果a?ab?b能被9整除，那么a，b均能被3整除。

证明：将a?ab?b写作：

22222a2?ab?b2=(a?b)2?3ab。 （*）

根据假设9|a?ab?b，而3|9，故由整除性质1知，3|a?ab?b。又因3|3ab，故由（*）式及整除性质5知，3|(a?b)。由于3是质数，由定理5.2.5知，

3|（a-b）。

2因此，9|(a?b)，而由假设9|a?ab?b，故再由（*）式及整除性质5知，9|3ab，即，

22222223|ab。

3是质数，根据定理5.2.5知，

3|a或3|b。

而当3|a或3|b有一个成立时，又由3|（a-b）知，必有另一个也成立。因此，a，b均能被3整除。

说明：整数a和b的每一个被3 除时，其余数只能是0，1，2中的一个，如果我们取其余数的所有可能九种组合，也能得到例5.2.3的证明。

例5.2.4 任给五个整数，试证明：必能从其中选出三个，使得它们之和能被3 整除。 证明：任意整数必可写作下列形式之一：

3k，3k+1，3k+2，

其中k是整数。

如果给定的五个整数中有三个分别属于上述三种形式，那么显然这三个整数的和必可被3整除。

如果给定的五个整数只属于上述三种形式之一种或两种，那么必有三个整数属于同一种

形式，这三个整数之和便可被3整除。

因此，从给定的五个整数中，必可选出三个，使得它们之和能被3 整除。

例5.2.5 任给n个整数，试证明：必能从其中选出k个，使得它们之和能被n 整除。 证明：设a1，a2，…，an是给定的n个整数。作和： s1= a1， s2= a1+ a2， s3= a1+ a2+ a3， ?

sn= a1+ a2+?+ an .

下面将这n个和si分类，所有被n除余数相同的算作同一类。

由于一个整数被n除，其余数只能是下列形式之一：

0，1，2，?，n-1，

所以，如果si（i=1，2，?，n）属于不同的类，那么其中一定有某个sk可被n整除；否则，如果这n个和数si中，有两个sp和sq属于同一类，不妨设p

n|sp-sq

且

sp-sq= ap+1+ ap+2+?+ ap+k ，

因此，

n| ap+1+ ap+2+?+ ap+k。

说明：在例5.2.4，例5.2.5中，我们实际上使用了用模m合同关系将数进行分类的思想。

例5.2.6 试证明如下结论：

（1）当n是偶数时，数3n+1能被2 整除； （2）当n是奇数时，数3n+1能被2 2 整除；

（3）不管n是偶数还是奇数，3n+1不能被2的任何更高次幂整除。 证明：首先证明：任何奇数的平方被8除时余1。 对于任意一个奇数，都形如2k+1（k?0），而

（2k+1）2 = 4k（k+1）+1，

因为2| k（k+1），故8|4k（k+1），因此，用8去除上式余数为1。

（1）当n是偶数时，设n=2m，则

3n+1=32m+1=(3m) 2+1。

因为3m是奇数，所以由上面结论知，(3m) 2被8除时余1，不妨设

(3m) 2=8a+1，

于是，

3n+1=(3m) 2+1=8a+2=2(4a+1)， ①

因此，3n+1能被2 整除。

（2）当n是奇数时，设n=2m+1，则

3n+1=32m+1+1=3(3m) 2+1。

与（1）同理可设(3m) 2=8a+1，于是

3n+1=3(3m) 2+1=3（8a+1）+1=4(6a+1)， ②

因此，3n+1能被2 2 整除。

（3）由①式和②式可知，4a+1和6a+1都是奇数，不能被2整除，所以不管n是偶数

还是奇数，3n+1不能被2的任何更高次幂整除。

说明：（1）利用本题的结论，容易证明下面结论：对于任意大于1的整数m，3m+1不可能被2m整除。

（2）如果利用合同的概念，本题的证明会更简单些，读者可作为练习。

5.2.2 关于质数的问题

上面已经接触到几个关于质数的习题。这部分习题还要常用到算术基本定理及其推论。另外，要记住质数与互质有一定的联系：质数p和a互质，必要而且只要p | a。在5.2.1中\\

我们也常使用从教材中定理5.2.5“若质数p整除a1a2…an，则p整除a1，a2，…，an之一”可直接得到的一个结论：若质数p整除qn，则p整除q。

例5.2.7 设n是大于1的整数，试证明：如果n不能被不大于n的立方根的所有质数整除，则n或者是质数，或者是两个质数的乘积。

证明：n不能是三个或三个以上的乘积即可。由算术基本定理知，可设n是k个质因数的乘积：

n=p1…pk，

往证k=1或2。

使用反证法，假设k?3，则由题设知，n的质因数均大于3n，故有：

n=p1…pk

?p1p2 p3

>（3n）（3n）（3n）

=n。

因此产生了矛盾，原假设不对，只能是k=1或2，即n或者是质数，或者是两个质数的乘积。

例5.2.8 设 n是任意正整数，试证明：n可唯一表示为

n=k2m，

其中k2是平方数，m或者是1或者是不同的质数的乘积。

证明：（1）首先证明可表性。

当n=1时，1= 121，即k2=1，m=1。命题成立。 当n>1时，由算术基本定理的推论2知，可设

n=p11p22?pss，

其中p1，…，ps是不同的质数。用2去除每个li，设商为qi，余数为ri，即

li=2qi+ri，

其中，i=1，2，…，s，ri=0或1。 则

n=p11p22?pss

=(p11p22?pss)p11p22?pss，

qqq2rrrllllll

≡

?ak?0n[]3[3k?10?a3k?1?26?a3k?2（mod 37）

k?0[3kk?0[n?1]3[n?2]3因此，如果

?ak?0n[]3，那么37|N。 ?10?a3k?1?26?a3k?2≡0（mod 37）

k?0k?0n?1]3n?2]3利用上例的结论可以判断一个数能否被2，3，4，5，6，7，8，9，11，13，37整除。比如，对于N=1316830，由于a0=0≡0（mod 2），故2|N；a0=0≡0（mod 5），故5|N；由于（0+6+1）+10（3+1）+26（8+3）=333，对于333，3+10×3+26×3=111，对于111，1+10×1+26×1=37≡0（mod 37），因此，111≡0（mod 37），因此，333≡0（mod 37），故37|N。

一个整数如果倒过去读仍是该数，则称为回文数，如66，1661，935686539。利用上例的结论可以证明：每个四位数回文数均能被11整除。设abba为任一四位回文数，则由于a-b+b-a=0≡0（mod 11），因此11整除该四位回文数。同样可以证明每个六位回文数可被11整除，进一步，每个偶数位回文数均可被11整除。

例5.2.16 设p为质数，记

N=1+2+3+…+(p-1)，

试证明：(p-1)! ≡(p-1) (mod N)。

证明：由于 p是质数，由Wilson定理（见教材习题5.3的第4题）知，(p-1)! ? -1(mod p)。于是存在整数m，使得

(p-1)!=mp-1，

故(p-1)!=mp-1=（m-1）p+(p-1)，所以

（m-1）p=(p-1)!-（p-1）=(p-1)((p-2)!-1)。

由上式及p|（m-1）p知，p|(p-1)((p-2)!-1)。显然p | p-1，否则若p|p-1，而由p|p，及整除的\\

性质5知，p|-1，这与p是质数矛盾。由教材中定理5.2.5知，若p是质数，p | p-1，且\\p|(p-1)((p-2)!-1)，则p| ((p-2)!-1)。不妨设

((p-2)!-1)=np，

于是

（m-1）p=（p-1）np，

p是质数，故p≠0，上式两边消去p得：

m-1=n(p-1)。

因此，

(p-1)! = mp-1

= （n(p-1)+1）p -1 =n(p-1)p+p-1

=2n×

p(p?1)+ p-1 2=2n×[1+2+3+…+(p-1)]+ p-1 =2nN+ p-1.

故(p-1)! ≡(p-1) (mod N)。

5.2.4 求解一次合同方程的方法

定理5.3.1告诉我们若a和m互质，b任意，则模m恰有一个数x使ax?b(mod m)。该定理证明存在性的过程即告诉了我们一种求解方法：因为a和m互质，故有s，t使as+mt=1，于是asb+mtb=b，若取模m，则有asb?b(mod m)。取x=sb，则sb所在的剩余类中的数皆是解。因此，方法一就是先使用辗转相除方法将互质的a与m的最大公因数1表示为a和m的倍数和的形式：1=as+mt，然后取x=sb，即可。

例5.2.17 解合同式103x?57(mod 211)。 解：由于103与211互质，我们先将103与211的最大公因数1表示为它们的倍数和的形式。使用辗转相除方法逐次得商及余数并计算Sk，Tk如下表所示：

k rk qk Sk Tk

因此，

1=（-1）3×41×211+（-1）4×84×103。

由此知，S=（-1）4×84，所以

x=sb=84×57=4788=21×23-65?-65(mod 211)。

另外一种方法就是利用合同的性质，使x的系数变成1，即得到解。 对于上例解合同式103x?57(mod 211)。由于

211=103×2+5，

由合同的性质7有

2×103x?2×57(mod 211)。

因为

211x?0(mod 211)，

所以由合同的性质5知，

211x-2×103x?0-2×57(mod 211)。

即5x?-114(mod 211) ?97(mod 211)。 由于

211=42×5+1

由合同的性质7有

42×5 x?42×97 ?211×19+65 ?65(mod 211)。

由合同的性质5知，

211x-42×5 x?0-65(mod 211)。

即x?-65(mod 211)。

对于一些例子，使用这种方法是比较快的。比如，解合同式4x?1(mod 15)。因为

1?16(mod 15)，

所以

4x?1 ?16 ?4×4(mod 15)，

因为4与15互质，由合同的性质10知，合同式两边可以消去4，得到

0 1 0 1 5 2 1 2 2 3 20 20 41 3 2 1 21 43 4 1 1 41 84 5 0 3 x?4(mod 15)。

还有一种求解合同式的方法就是利用Fermat-Euler定理（教材中定理5.4.7），见下例。 例5.2.18 解合同式7x?5(mod 10)。

解：因为7和10互质，由Fermat-Euler定理有

7?(10)?1(mod 10)，

因?(10)=4，所以74?1(mod 10)。由合同的性质7，在7x?5(mod 10)两边乘以73，有

73×7x?73×5(mod 10)，

而

73×7x=74 x ? x(mod 10)，

73×5=72×7×5?（-1）×7×5 ?5(mod 10)，

所以所给合同式的解为x ?5(mod 10)。

秦九韶定理是求解最简单的合同式组的方法，也是解高次合同式组的基础。如何使用求一术很重要，书中已经详细给出，在这里就不再赘述。

5.2.5 应用Fermat-Euler定理及Fermat小定理

前面我们介绍了Fermat-Euler定理的一个应用--利用它求解合同式。下面举例说明其它的应用。

例5.2.19 设p是一个奇质数，则

（1）1p-1+2 p-1+…+(p-1) p-1 ? -1(mod p)。 （2）1p+2 p+…+(p-1) p ? 0(mod p)。

（3）若2 m不合同于1模p，其中m是正整数，则

1m+2m+…+(p-1) m ? 0(mod p)。

证明：（1）因为p为质数，故对于任意的1?k?p-1，由Fermat小定理Ⅰ知，有

k p-1? 1(mod p)。

因此，

1p-1+2 p-1+…+(p-1) p-1 ?1+1+…+1=p-1? -1(mod p)。

（2）由Fermat小定理Ⅱ知，对于任意的1?k?p-1，有

k p? k(mod p)。

故

1p+2 p+…+(p-1) p?1+2 +…+(p-1) ?

p(p?1)

(mod p)。 2因为p是奇数，所以（p-1）/2是整数，故

p(p?1)

?0(mod p)。 2因此，1p+2 p+…+(p-1) p ?

p(p?1)

? 0(mod p)。 2（3）因为p为奇数，所以2与p互质，故又由1，2，…，（p-1）是模p的简化剩余系知，2，4，6，…，2（p-1）也是模p的简化剩余系，它的每个数必与且只与1，2，…，（p-1）中的一个数关于模p同余。故由合同的性质知，

2m+4m+…+[2(p-1)] m ?1m+2m+…+(p-1) m (mod p)。

故

（2m-1）(1m+2m+…+(p-1) m) ?0 (mod p)。

由已知，2 m不合同于1模p，故2 m-1不合同于0模p，又因为p为质数，由教材中合同的性质12知，1m+2m+…+(p-1) m?0 (mod p)。

例5.2.20 （1）求（12371170+34）28被243除的余数。 （2）求7355的个位数（最后一位数）。 （3）求7355的最后两位数。 （4）求243402的最后三位数。 解：

（1）因243=35，所以由定理5.4.6知，

?(243)=243×（1-

1）=162。 3又12371?221（mod 243）?-2（mod 243），221与243互质，于是，由Fermat-Euler定理有：

221162?1（mod 243），

即12371162?1（mod 243）。所以，

12371170?123718

?（123712）4 ?（（-22）2）4 ?（（-2））4

?16（mod 243）， 因此，

（12371170+34）28?（16+34）28?5028（mod 243）。

而502?70（mod 243），504?40（mod 243），508?142（mod 243），5016?-5（mod 243），于是，

5028?40×142×（-5）?115（mod 243）。

故（12371170+34）28被243除的余数为115。

（2）求7355的个位数，只需求7355被10除的余数。因?(10)= ?(2) ?(5)=4，7与10互质，由Fermat-Euler定理有：

74?1（mod 10），

所以

×

7355?7488+3?73?3（mod 10）。

因此，7355的个位数是3。

（3）因100=2252，所以由定理5.4.6知，

?(100)=100×（1-

11）（1-）=40。 25又，7与100互质，于是，由Fermat-Euler定理有：

740?1（mod 100），

所以

×

7355?7408+35?735（mod 100）。 ×

而74?1（mod 100），故735?748+3?73?43（mod 100），即

7355?43（mod 100）。

因此，7355的最后两位数是43。

（4）因1000=2353，所以由定理5.4.6知，

?(1000)=1000×（1-

11）（1-）=400。 25又，243与1000互质，于是，由Fermat-Euler定理有：

243400?1（mod 1000），

所以

243402?2432?49（mod 1000）。

因此，243402的最后三位数是049。

5.3 习题解答

本文来源：https://www.bwwdw.com/article/ere5.html