初等数论一-夏子厚

1、初等数论(一) Number Theory（Chap1）,初始版：信阳职业技术学院 夏子厚 修改：贾祥雪,为什么学数论,有用 在研究函数，尤其是周期函数的时候经常性要用到。 大学学习抽象代数及其后续课程的基础 计算机专业的必修课！尤其应用到算法和密码两大领域 好玩，简单，美 自主招生、竞赛中考数论,为什么要这样学？,为什么不能直接讲一堆题目，从一个个题目中学习方法和技巧？ 为什么那么多字母，没几个具体数字？ 为什么很多东西还需要证明? 为什么证明看上去那么纠结，让人觉得多此一举? 为什么学习的顺序和小学不一样?,如何能学好数论,最好对数字的一些特征比较敏感，如质数、合数、约数、倍数、完全平方数

2、、完全立方数、公约数、公倍数等等。 不要因为能解具体数的题目而不学抽象的通用方法。要学会符号语言。 要会逻辑清晰地使用符号语言进行论证 最重要的是，要理清知识之间的联系和来龙去脉，构建知识网络。 初等数论有多种构建知识网络的方法，在学完后建议自己尝试用不同的方法进行构建,初等数论课程内容,第一章 整除性质 第一节 整除与带余除法 第二节 最大公因数 第三节 最小公倍数 第四节 辗转相除法 第五节 算术基本定理 第六节 函数X、X的性质及其应用,初等数论课程内容,第二章 不定方程 第一节 二元一次不定方程 第二节 多元一次不定方程 第三节 勾股数x2 y2 = z2,初等数论课程内容,第三章 同

3、余性质 第一节 同余的概念及其基本性质 第二节 完全剩余系 第三节 欧拉函数与简化剩余系 第四节 欧拉定理与费马定理,初等数论课程内容,第四章 同余方程 第一节 一次同余方程 第二节 孙子定理（中国剩余定理） 第三节 质数模的同余方程 第四节 二次同余方程与平方剩余 第五节 勒让德符号与二次互反律 第六节 雅可比符号,第一章 整数性质,教学目的和要求 （1）深刻理解整除、最大公因数、最小公倍数、质数的概念，正确理解带余数除法和算术基本定理的意义及作用。 （2）掌握并能直接运用辗转相除法求最大公因数。 （3）熟练掌握整除、质数、最大公因数和最小公倍数的基本性质，理解并掌握函数x、x的概念和基本性

4、质，会求n!的标准分解式（n较小）。,第一节 整除与带余数除法,定义1 设a，b是整数，b 0，如果存在整数q，使得 a = bq 成立，则称b整除a或a被b整除，此时a是b的倍数，b是a的因数（约数或除数），并且记作：ba；如果不存在整数q使得a = bq成立，则称b不能整除a或a不被b整除，记作：b a。,第一节 整除与带余数除法,定理1 下面的结论成立： (1) ab，bc ac；（传递性） (2) ma，mb m(ab) (3) mai，i = 1, 2, , n ma1q1 a2q2 anqn， 此处qiZ（i = 1, 2, , n）。,第一节 整除与带余数除法,注： ab ab；

5、 ba bcac，此处c是任意的非零整数； ba，a 0 |b| |a|； ba且|a| |b| a = 0。 an- bn=(a-b) M1, nZ an+bn=(a+b)M2, n为奇数, M1 , M2Z,第一节 整除与带余数除法,定理2(带余数除法) 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得 a = bq r，0 r b。 (1) 此外，ba的充要条件是r=0,第一节 整除与带余数除法,证明： 存在性 作整数序列： ，-3b，-2b，-b，0，b，2b，3b，. 则a必在上述序列的某两项之间，即存在整数q，使得： qb a (q+1) b 成立，令a-qb=r，则a

6、=bq+r，且0 r b。,第一节 整除与带余数除法,唯一性 假设有两对整数q ，r 与q ，r 都使得式(1)成立，即 a = q b r = q b r ，0 r , r b， 则 (q q )b = r r ，0 |r r | b， (2) 因此由b | |r r |知r r = 0，r = r 再由式(2)得出q = q 从而q和r是唯一的。,第一节 整除与带余数除法,定义2 称式(1)中的q是a被b除的商，r是a被b除的余数。 我们设b=15，则： 当a=255时，a=17b+0, r=015, 而q=17; 当a=417时，a=27b+12,r=1215,而q=27; 当a=-81

7、时，a=-6b+9, r=915, 而q=-6。,第一节 整除与带余数除法,由定理2可知，对于给定的正整数b，可以按照被b除的余数将所有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究（我们将在第三章同余性质里讨论）。,第一节 整除与带余数除法,例1 任意给出的五个整数中，必有三个数之和被3整除。 证明 设这五个数是ai，i = 1, 2, 3, 4, 5， 记 ai = 3qi ri，0 ri 3，i = 1, 2, 3, 4, 5。,第一节 整除与带余数除法,分别考虑以下两种情形： () 若在r1, r2, , r5中数0，1，2

8、都出现，不妨设r1 = 0，r2 = 1，r3 = 2，此时a1 a2 a3 = 3(q1 q2 q3) 3可以被3整除； () 若在r1, r2, , r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1 = r2 = r3 = r（r = 0，1或2），此时a1 a2 a3 = 3(q1 q2 q3) 3r可以被3整除。 综合() 、()可知，所证结论成立。,你能将上例推广？,第一节 整除与带余数除法,例2 若 ax0+by0 是形如ax+by （x,yZ，a，b是两个不全为零的整数）的数中的最小正数，则 ax0+by0ax+by 。,第一节 整除与带余数除法,证

9、明：由于a,b不全为0，所以在整数集合 S =ax+by x,yZ 中存在正整数，因而有形如ax+by的最小正数ax0+by0 。 对任意的 x,yZ ，由带余除法有 ax+by=（ax0+by0）q+r , 0r ax0+by0 。 则 r =(x-x0q)a+(y-y0q)b S ， 由ax0+by0 是S中的最小整数知 r =0。 故ax0+by0ax+by 。,第一节 整除与带余数除法,注：（1）设a1, a2, , an为不全为零的整数，以y0表示集合 A = y|y =a1x1 a2x2 anxn，xiZ，1 i n 中的最小正数，则对于任何yA，y0y；特别地，y0ai，1 i

10、n。（证明留给学生自己） （2）此类题目的证明方法具有一般性，通常是针对所给的“最小正数”的概念进行反证法。,第一节 整除与带余数除法,思考与练习1.1 1、证明：mai ma1q1 a2q2 anqn， qiZ。i = 1, 2, , n 2、证明：6n(n+1)(2n+1) nN。 3、设a1, a2, , an为不全为零的整数，以y0表示集合A = y|y =a1x1 anxn，xiZ，1 i n 中的最小正数，则对于任何yA，y0y；特别地，y0ai，1 i n。,第二节 最大公因数,定义1 设a1, a2, , an是n（n2）个整数，若整数d是它们之中每一个的因数，则d就叫做a1,

11、 a2, , an的一个公因数；其中最大的一个公因数叫做a1, a2, , an的最大公因数。记为(a1, a2, , an)。 由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，且是正整数。,第二节 最大公因数,定理1 若a1, a2, , an为任意n个不全为零的整数。则： (1) a1, a2, , an与|a1|, |a2|, , |an|的公因数相同； (2) (a1, a2, , an) = (|a1|, |a2|, , |an|)。 （证明了（1）也就证明了（2） 由定理1可知，在讨论(a1, a2, , an)时，不妨假设a1, a2, , an是正整数，以后我们就

12、维持这一假设。,第二节 最大公因数,若(a1, a2, , an) = 1， 则称a1, a2, , an是互质的； 若(ai, a j) = 1，1 i, j n，i j， 则称a1, a2, , an是两两互质的。 显然，a1, a2, , an两两互质可以推出(a1, a2, , an) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2。,第二节 最大公因数,我们容易得到如下结论： 定理2 若b是任一整数，则： (1) 0与b的公因数就是b的因数，反之，b的因数也就是0与b的公因数； (2) （0，b）=b 。,第二节 最大公因数,定理3 若a，b，c是任意三

13、个不全为零的整数，且a =bqc，其中q是非零整数，则 a，b与b，c有相同的公因数， 因而 (a, b) = (b, c)。 证明留给学生自己。,第二节 最大公因数,定理4 对于任意的n个整数a1, a2, , an，记 (a1, a2) = d2，(d2, a3) = d3，(dn 2, an 1) = dn 1 (dn 1, an) = dn，则：dn = (a1, a2, , an)。 证明（1）dn是a1, a2, , an的一个公因数； （2） dn是a1, a2, , an的公约数中的最大者。 （即：对于a1, a2, , an的任何公因数d， ddn ）,第二节 最大公因数,证

14、明：dn = (dn 1, an) dnan，dndn 1， dn 1 = (dn 2, an 1) dn 1an 1，dn 1dn 2， dnan，dnan 1，dndn 2， dn 2 = (dn 3, an 2) dn 2an 2，dn 2dn 3 dnan，dnan 1，dnan 2，dndn 3， d2 = (a1, a2) dnan，dnan 1，dna2，dna1 即dn是a1, a2, , an的一个公因数。,第二节 最大公因数,另一方面，对于a1, a2, , an的任何公因数d，由d2, , dn的定义，依次得出 da1，da2 dd2， dd2，da3 dd3， ddn

15、1，dan ddn， 因此 dn是a1, a2, , an的公约数中的最大者。 故 dn = (a1, a2, , an)。,第二节 最大公因数,例1 设a1, a2, , an为不全为零的整数，以y0表示集合 A = y|y = =a1x1 anxn，xiZ，1 i n 中的最小正数，则y0=（a1, a2, , an）。,第二节 最大公因数,证明：由于y0是集合A中的最小正数，故 设d是a1, a2, , an的任意一个公因数，则d ，所以dy0。又由本章第1节例2的注（1）知，y0ai，1 i n，因此y0也是a1, a2, , an的一个公因数。故y0一定是a1, a2, , an所有

16、公因数中的最大正数。由此即得：y0=（a1, a2, , an）。,第二节 最大公因数,注：由于（a1, a2, , an）是集合 A = y|y =a1x1 anxn，xiZ，1 i n 中的最小正数，由此题的证明过程直接得到如下结论： 设不全为零的整数a1, a2, , an的最大公因数是（a1, a2, , an），则存在整数，使得： a1t1 antn =（a1, a2, , an）。,第二节 最大公因数,由上我们容易得到： 定理5 （裴蜀（Bzout,1730-1783）恒等式）设a，b是任意两个不全为零的整数，则存在s，tZ，使得 as bt = (a, b),第二节 最大公因数,

17、推论5.1 (a, b)1的充要条件是：存在s，tZ，使得 as bt = 1。 此题可以推广为： 推论5.2 (a1, a2, , an) = 1的充要条件是：存在整数x1, x2, , xn，使得 a1x1 a2x2 anxn = 1。,第二节 最大公因数,定理6 若a，b，c是任意的三个整数，且(a, c)1，则 (1) ab，c与b，c有相同的公因数； (2) （ab，c）（b，c） 上面假定了b，c至少有一个不为零。 （证明了（1）也就证明了（2）.,第二节 最大公因数,证明：（1）由题设及推论5.1，存在s，tZ，使得 as ct = 1。 两边乘以b，即得：(ab)s c(bt)

18、 = b。 设d是ab与c的任一公因数，由上式得： db，因而d是b，c的一个公因数。反之b，c的任一公因数显然是ab与c的一个公因数。故第一部分获证。 （2）因为b，c不全为零，所以（b,c）是存在的，于是由（1）知（ab，c）存在，且 （ab，c）（b，c）,第二节 最大公因数,推论6.1 若(a, c) = 1，cab，则cb 推论6.2 若 (a, bi) = 1，1 i n， 则 (a, b1b2bn) = 1 推论6.3 若 (ai, bj) = 1，1 i n，1 j m， 则 (a1a2an , b1b2bm) = 1,第二节 最大公因数,注：几个常用的结论。若（a，b）=1

19、则 （an，bm）=1； (ab,ab)=1； (a+b,a-b)=1或2。,第二节 最大公因数,例2 设a，b，c，n是正整数，ab = cn ， (a, b) = 1，则存在正整数u，v，使得 a = un，b = vn，c = uv，(u, v) = 1。,第二节 最大公因数,证明：因为(a, b) = 1，所以(b, an-1)=1，于是 同理可得 ，令 ， 则 a = un，b = vn，c = uv，且 故结论成立。,第二节 最大公因数,注：此题说明，若互质的两个正整数之积是一个整数的n次幂，则这两个正整数都是整数的n次幂。 此结论可以推广为：若两两互质的s个正整数之积是一个整数的

20、n次幂，则这s个正整数都是整数的n次幂。这个性质表现了整数互质的重要性，其应用较广泛。,第二节 最大公因数,思考与练习1.2 1、证明本节定理3。 2、设m、n为正整数，m为奇数，证明： （2m-1，2n+1）=1。 3、设n是正整数，求 的最大公约数。,第三节 最小公倍数,定义1 设a1, a2, , an是n（n2）个整数，若整数d是这n个数的倍数，则d就叫做a1, a2, , an的一个公倍数；又在a1, a2, , an的一切公倍数中的最小正数叫做a1, a2, , an的最小公倍数。记作：a1, a2, , an。 由于任何正数都不是0的倍数，故讨论整数的最小公倍数时，假定它们都不是

21、0.,第三节 最小公倍数,定理1 a1, a2, , ak = |a1|, |a2| , |ak| 证明：设m1 = a1, a2, , ak， m2 = |a1|, |a2|, , |ak| ， 则由aim1 推出 |ai|m1， 即 m2m1 同理可得m1m2，故m1 = m2,第三节 最小公倍数,定理2 设a,b是任意两个正整数，则： (1) a,b的所有公倍数就是a, b的倍数； (2) a, b = ， 特别地，若(a, b) = 1，则a, bab 这里不再给予证明。其中（2）后面有证明。,第三节 最小公倍数,注：这个定理说明： 最小公倍数和最大公约数之间有着一个很重要的关系； 两

22、个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的因数。即：若m是整数a1, a2的任一公倍数，则a1, a2m 。 同样地，若m是整数a1, a2, , an的任一公倍数，则a1, a2, , anm 。,第三节 最小公倍数,推论2.1 设m，a，b是正整数，则 ma, mb = ma, b。 证明： ma, mb = = ma, b。,第三节 最小公倍数,推论2.2 整数a1, a2, , an两两互质，即：(ai, aj) = 1，1 i, j n，i j 的充要条件是： a1, a2, , an = a1a2an 这里不再给予证明。,第三节 最小公倍数,推论2.2有许多应用。例

23、如，如果m1, m2, , mn是两两互质的整数，那么，要证明m = m1m2mn整除某个整数Q，只需证明对于每个i，1 i n，都有miQ。这一点在实际计算中是很有用的。,第三节 最小公倍数,定理3 对于任意的n个正整数a1, a2, , an，记：a1, a2 = m2，m2, a3 = m3， mn2, an1 = mn1，mn1, an = mn， 则 a1, a2, , an = mn 注：mn是a1, a2, , an的一个公倍数。 mn是a1, a2, , an最小的正的公倍数。,第三节 最小公倍数,例1 设k是正奇数，证明： 1 2 91k 2k 9k。 证明：设s = 1k

24、2k 9k，则由 2s = (1k 9k) (2k 8k) (9k 1k) = 10q1 2s = (0k 9k) (1k 8k) (9k 0k) = 9q2 得102s和92s，于是有 902s， 从而 1 2 9 = 45s 。,第三节 最小公倍数,例2 设a，b是正整数，证明： (a b)a, b = ab, a b。 证明：要证(a b)a, b = ab, a b。由定理2知：只需证 即须证(b, a b) = (a, b)，此式显然成立。,第三节 最小公倍数,例3 设a，b，c是正整数，证明： a, b, c(ab, bc, ca) = abc 。 注：利用最大公因数和最小公倍数的

25、关系可以解决类似的问题。如证明等式：,第三节 最小公倍数,解 a, b, c = a, b, c = (2) (ab, bc, ca) = (ab, (bc, ca) = (ab, c(a, b) = (3) 联合式(2)与式(3)得到所需结论。,第三节 最小公倍数,思考与练习1.3 1、求正整数a，b，使得a b = 120， (a, b) = 24，a, b = 144。 2、设a，b是正整数，证明：若 a，b=(a，b)，则 a=b。 3、证明：,第四节 辗转相除法,定义1 下面的一组带余数除法，称为辗转相除法。西方也叫欧几里得除法。设a和b是正整数，依次做带余数除法： a = bq1

26、r1， 0 r1 r2 ， 所以式(1)中只包含有限个等式。,第四节 辗转相除法,如（1）：a=1859, b=1573 1859=11573+286 1573=5286+143 286=2143+0 如（2）：a=169,b=121 169=1121+48 121=248+25 48=125+23 25=123+2 23=112+1 2=21+0,第四节 辗转相除法,定理1 若a，bZ，则 （a，b）= rn 证明：从 (1) 式可见，rn = (rn 1, rn) = (rn 2, rn 1) = = (r1, r2) = (b, r1) = (a, b)。 推论1.1 a，b的公因数与（

27、a，b）的因数相同。,第四节 辗转相除法,例1 求（1859，1573） 解：（1859，1573）=（1859，1573）=（286，1573）=（286，143）=143 例2 求（169，121） 解：（169，121）=（48，121） = （48，25） =（23，25）=1,第四节 辗转相除法,例3 证明：若n是正整数，则 是既约分数。 解 由定理1得到 (21n 4, 14n 3) = (7n 1, 14n 3) = (7n 1, 1) = 1。,第四节 辗转相除法,定理2 设a，b是任意两个不全为零的整数， （）若m是任一正整数，则 （am，bm）=（a，b）m （）若是a，b

28、的任一公因数，则 （ ， ）= 特别地, = 1。,第四节 辗转相除法,证明：当a,b有一个为零时，定理显然都成立。今设ab0。由前两节知， （am,bm）=(|a|m, |b|m), （a，b）m=（|a|，|b|）m。 从而不妨设a0，b0。在辗转相除法（1）式中两边同乘以m，即得：,第四节 辗转相除法,am =（bm）q1 r1m， 0 r1 m bm， bm =（r1m）q2 r2m， 0 r2 m r1 m， rn 2 m=（rn 1m）qn rnm， 0 rn m rn-1m ， rn 1 m=（rnm）qn + 1 rn+1m， rn+1m=0。 由定理1得，（am,bm）= r

29、nm=（a，b）m,第四节 辗转相除法,推论2.1 (ma1, ma2, , man) = |m|(a1, a2, , an)。m0 推论2.2 记 = (a1, a2, , an)，则 = 1,第四节 辗转相除法,例4 记Mn = 2n 1，证明：对于正整数a，b，有(Ma , Mb) = M(a, b) 证明：作辗转相除： a = bq1 r1， 0 r1 b， b = r1q2 r2， 0 r2 r1， rn 2 = rn 1qn rn，0 rn rn 1， rn 1 = rnqn 1 rn 1，rn 1 = 0。 由第一个式得,第四节 辗转相除法,2a 1 = 即 等，于是 注：把此题

30、中的2用任一大于1的自然数g代替，结论都成立。,第四节 辗转相除法,思考与练习1.4 1 、 使用 (1) 式中的记号，设 P0 = 1，P1 = q1，Pk = qkPk 1 Pk 2，k 2， Q0 = 0，Q1 = 1，Qk = qkQk 1 Qk 2，k 2， 则 aQk bPk = (1)k 1rk，k = 1, 2, , n 。 2、用辗转相除法求(125, 17)，以及s，t，使得 125s 17t = (125, 17)。,第五节 算术基本定理,定义1 一个大于1的整数，如果它的正因数只有1及它本身，就叫做质数；否则就叫做合数。 以后在本书中若无特别说明，质数总是指正质数。 定

31、理1 设a是任一大于1的整数，则a的除1外最小正因数q是一质数，并且当a是合数时，q 。,第五节 算术基本定理,证明 若q不是质数，由定义，q除1外还有一正因数q1，因而，1q1q，但qa，所以 q1a，这与q是a的除1外最小正因数矛盾，故q是质数。 当a是合数时，有a = a1q，且a1 1，否则a是质数 因q是a的除1外最小正因数，所以q a1， q2 q a1a。故q 。 注：由定理1易得：若大于1的整数a不能被任何适合q 的质数q整除，则a必为质数。,第五节 算术基本定理,我们容易得到如下结论： 定理2 若p是一质数，a是任一整数，则（p,a）=1或pa 。 推论2.1 设a1, a2

32、, , an是n个整数，p是一质数，若pa1a2an，则存在1kn,使得pak。,第五节 算术基本定理,定理3(算术基本定理) 任何大于1的整数都可以表示成若干个质数的乘积。即任何大于1的整数 ap1p2 pn ，p1 p2 pn， 其中p1, p2, , pn是质数，并且若 aq1q2 qm ，q1 q2 qm ， 其中q1, q2, , qm是质数，则m=n，qipi i=1,2,n。（这里不再给予证明）,第五节 算术基本定理,推论3.1 任何大于1的整数a能够唯一地表示成 a= ， 其中p1, p2, , pk是质数，p1 p2 pk，1, 2, , k是正整数。 使用推论3.1中的记号

33、，称 a = 是a的标准分解式，其中pi（1 i k）是质数，p1 p2 pk， i（1 i k）是正整数。,第五节 算术基本定理,推论3.2 设任何大于1的整数 a= ， i0（1 i k）则a的正因数d可以表示成 d = ，iZ，0 i i，1 i k；的形式，而且当d可以表示成上述形式时，d是a的正因数。,第五节 算术基本定理,注：用d(a)表示a的所有正因数的个数，则 用(a)表示a的所有正因数的和，则 用(a)表示a的所有正因数的积，则(a)=,第五节 算术基本定理,推论3.3 设正整数a与b的标准分解式是 ， 其中p1, p2, , pk 是互不相同的质数，i，i（1 i k）都是

34、非负整数，则 (a, b) = i = mini, i，1 i k， a, b = i = maxi, i，1 i k。,第五节 算术基本定理,例1 写出51480的标准分解式。 解 我们有 51480 = 225740 = 2212870 = 236435 = 2351287 = 2353429 = 23532143 = 233251113。,第五节 算术基本定理,例2 设a，b是正整数，证明： (a, b)a, b = ab 证明： 设 其中p1, p2, , pk是互不相同的质数，i，i（1 i k）都是非负整数。于是有 由此知(a, b)a, b = =ab,第五节 算术基本定理,定理

35、4 质数有无限多个。 证明：假设只有k个质数，设它们是p1, p2, , pk 。记 N = p1p2pk 1。 由定理1可知，N有质因数p，我们要说明p pi ，1 i k，从而得出矛盾。 事实上，若有某个i，1 i k，使得p = pi ，则由 pN = p1p2pk 1 推出p1，这是不可能的。因此在p1, p2, , pk之外又有一个质数p，这与假设是矛盾的。 所以质数不可能是有限个。,第五节 算术基本定理,思考与练习1.5 1、如果2m+1是质数，则m=2n(n是正整数)。 2、若a 1，a n 1是质数， 则a = 2，并且n 是质数。 3、设a，b，c是整数，证明： (a, b, c) = (a, b), (a, c)。,第