初等数论复习

1、 作业要求：作业要求： 作业要及时完成，及时提交。作业要及时完成，及时提交。 作业（网络作业、期中作业）要计入总分。作业（网络作业、期中作业）要计入总分。 学习过程中的问题，可通过网上答疑系统提出。学习过程中的问题，可通过网上答疑系统提出。 考试说明：考试说明： 试题类型：填空题试题类型：填空题(40%)(40%)、计算题和证明题、计算题和证明题(60%)(60%)。 考试范围考试范围1-41-4章：其中第章：其中第1 1、2 2章各占章各占30%30%，第，第3 3、4 4章各占章各占2020（以光盘为准）。（以光盘为准）。 试题难度不超出习题、例题、模拟试卷。试题难度不超出习题、例题、模拟

2、试卷。第一章第一章 整数的整除性论整数的整除性论第二章第二章 同余理论同余理论第三章第三章 不定方程不定方程第四章第四章 同余式同余式第一章第一章 整数的整除性理论整数的整除性理论 本章主要从整数的整除性概念出发，本章主要从整数的整除性概念出发，介绍带余除法、辗转相除。然后以其为工介绍带余除法、辗转相除。然后以其为工具建立最大公因数和最小公倍数理论，最具建立最大公因数和最小公倍数理论，最后介绍算术基本定理，高斯函数等。后介绍算术基本定理，高斯函数等。 a|ab若b|a ，a0 则 若 b|a 且 a|b， 则 |a| = |b| 若 c | b , b | a , 则 c | a b|a 的充

3、要条件是 cb | ca 若 c|a, c|b, 则对于,m nc manb有niii=1(1,2, )k aikinm有 一般地若 m|ai（i=1 , 2 , ，n）,则一、一、 整除的概念与性质整除的概念与性质定理：,0a bb且，则, q r使得a=bq+r（0r0，c|a,c|b，则，则a,ba b,=c cc定理定理4 4：设：设a,ba,b是不全为零的整数。是不全为零的整数。(i)(i)若若 m0m0，则，则 (am,bm) = m(a,b)(am,bm) = m(a,b)(iii)(iii)若若 (a,b)= 1(a,b)= 1，t t是任意整数，是任意整数， 则则 (at,b

4、)=(t,b)(at,b)=(t,b)定理定理4 4：设：设a,ba,b是任给的两个正整数，则是任给的两个正整数，则(i) a , b(i) a , b的所有公倍数都是的所有公倍数都是a,ba,b的倍数。的倍数。(ii)a,b(a,b)=ab(ii)a,b(a,b)=ab推论：若推论：若(a,b)=1,(a,b)=1,则则a,b=aba,b=abm mm,=aba,b定理定理5 5：设正整数：设正整数m m是是a, ba, b的一个公倍数，则的一个公倍数，则证明：设证明：设 (a-b , a+b)= d 则则 d | a-b, d | a+b d | a-b+a+b , d | a-b-(a+

5、b) 即即 d | 2a , d | 2b d | (2a , 2b) d | 2(a , b) (a , b) = 1 d | 2 d=1 或或 d=2 例：如果例：如果(a , b)=1，则，则 (a-b ,a+b) = 1 或或 2三、整数的唯一分解定理三、整数的唯一分解定理 ( (算术基本定理算术基本定理) ) 其中其中定理：对于任一大于定理：对于任一大于1 1的整数的整数a a，除因数的顺序，除因数的顺序 外都能唯一分解成：外都能唯一分解成：12k12ka=p pp1(, ,1,2, , )iijippij i jkp为 素 数且且(1)d(1)d是是a a的正因数的充分必要条件是的

6、正因数的充分必要条件是1k1kd=pp(0 i i i i i = 1, 2, , k)(2) a a 的正因数的个数为的正因数的个数为T(a)=( 1 1+1)( 2 2+1)( k k+1)ki=1 ( i i +1)12k+1+1+112k12kp-1 p-1p-1S(a)=p -1p -1p -1(3) a a的一切正因数之和的一切正因数之和T(a)T(a)为为a a的一切正因数的个数。的一切正因数的个数。 1T a2p(a)=a(4) a a 的一切正因数之积为的一切正因数之积为定理：若定理：若x x是正实数，是正实数，nn+ +，则不大于，则不大于x x，且为，且为xnn n的倍数

7、的自然数的个数是的倍数的自然数的个数是四、高斯函数四、高斯函数 xx r=1np定理：在定理：在n!n!的标准分解式中素因数的标准分解式中素因数p p的指数是的指数是2rnnn+ppp p(n!)即即 200! 的标准式中素因数的标准式中素因数7的指数为的指数为32。例：求例：求200！标准分解式中素因数！标准分解式中素因数7的指数。的指数。r23200200200200=+7777 r=1解：解：7(200!)= 28 + 4 + 0 = 32第二章第二章 同余理论同余理论本章主要介绍同余的概念及其基本性质，本章主要介绍同余的概念及其基本性质，完全剩余系和互素剩余系，以及著名的欧拉完全剩余系

8、和互素剩余系，以及著名的欧拉定理、费马定理和威尔逊定理。定理、费马定理和威尔逊定理。一一、同余概念和基本性质同余概念和基本性质定理定理1 1：整数：整数a,ba,b关于模关于模m m同余的充要条件是同余的充要条件是m|a-bm|a-b定理定理2 2：若：若 a a1 1bb1 1(modm)(modm)，a a2 2bb2 2(modm)(modm) 则则 (1) a(1) a1 1+a+a2 2bb1 1+b+b2 2(modm)(modm) (2) a (2) a1 1-a-a2 2bb1 1-b-b2 2(modm)(modm) (3) a (3) a1 1a a2 2bb1 1b b2

9、 2(modm)(modm)推论：若推论：若a ak kbbk k(modm) k=1,2,(modm) k=1,2,n,n11modnnkkkkabm则则 (1)11modnnkkkkabm(2)推论：若推论：若ab(modm)ab(modm)，则，则a an nbbn n(modm) n(modm) n+ +定理：若定理：若acbc(modm)acbc(modm)且且(c(c，m)=1,m)=1, 则则ab(modm)ab(modm)定理定理: :若若m m1 100，m m1 1|m|m且且ab(modm)ab(modm)则则ab(modmab(modm1 1) )定理：若定理：若c0c

10、0，则，则ab(modm)ab(modm)acbc(modmc)acbc(modmc)定理：若定理：若ab(modmab(modmi i) (i=1) (i=1，2 2，, n), n)， 则则ab(modmab(modm1 1，,m,mn n)定理定理: : 若若acbc(modm)acbc(modm)且且(c(c，m)=dm)=d，md则则a a b(mod)解：解：47-2(mod7)47-2(mod7) 47 475050(-2)(-2)5050(mod7) 2(mod7) 25050(mod7) (mod7) 2 23 316+216+2(mod7)(mod7) (2 (23 3)

11、)16162 22 2(mod7) 8(mod7) 816162 22 2(mod7)(mod7) 1 12 22 2(mod7) 4(mod7)(mod7) 4(mod7) 7 7除除47475050的余数为的余数为4 4。例：求例：求7 7除除47475050的余数。的余数。定理：定理：k k个整数个整数a a1 1，a a2 2，a ak k形成模形成模m m的完全剩的完全剩 余系的充要条件是：余系的充要条件是： (1)k=m (2)ai aj(modm) ( i j )定理定理：若：若(a，m)=1,b，则当则当x x通过模通过模m m的完的完 全剩余系时，则全剩余系时，则ax+bax

12、+b也通过模也通过模m m的完全剩余系。的完全剩余系。二二、 完全剩余类和完全剩余系完全剩余类和完全剩余系解：解：0 0，2 2，2 22 2=4=4，2 23 3=8=8，2 24 45(mod11)5(mod11) 2 25 5225(mod11)10(mod11) 5(mod11)10(mod11) 2 26 610102(mod11)9(mod11)2(mod11)9(mod11) 2 27 77(mod11) 27(mod11) 28 83(mod11)3(mod11) 2 29 96(mod11)6(mod11) 2 21010662(mod11) 1(mod11)2(mod11)

13、 1(mod11) 是是 0 0，1 1，2 2，, 10 , 10 的一个排列。的一个排列。 0,20,21 1，2 22 2，2 23 3，,2,210 10 能构成模能构成模1111的的 一组完全剩余系。一组完全剩余系。 例：问例：问0,20,2，2 22 2，2 21010是否构成模是否构成模1111的完全剩余系？的完全剩余系？三、互素剩余类和互素剩余系。三、互素剩余类和互素剩余系。 定理：定理：k k个整数个整数a a1 1，a a2 2，a ak k构成模构成模m m的互素的互素 剩余系的充要条件是剩余系的充要条件是 (1) k=(m) (2) ai aj (modm)(i j)

14、(3) (ai, m)=1 (i=1，2，,( m)定理：若定理：若 (a,m)=1(a,m)=1，x x通过模通过模m m的互素剩余系，的互素剩余系，则则axax也通过模也通过模m m的互素剩余系。的互素剩余系。四、四、 欧拉定理、费马定理和威尔逊定理欧拉定理、费马定理和威尔逊定理 定理定理:(:(欧拉定理欧拉定理) )若若 (a,m)=1(a,m)=1，则，则a a(m) (m) 1(modm)1(modm)推论推论:(:(费马定理费马定理) )若若p p为素数为素数,(a,(a，p)=1,p)=1, 则则a ap-1p-11(modp)1(modp)推论：若推论：若p p为素数为素数，a

15、 ， 则则 a ap p a(modp) 定理：定理：( (威尔逊定理威尔逊定理) )整数整数p p是素数的充要条件是素数的充要条件 是是(p-1)! -1(modp)(p-1)! -1(modp)例：假定例：假定a是任意整数，求是任意整数，求证证211(mod3)aa或或210(mod3)aa分析：对于任意的任意整数分析：对于任意的任意整数a，用模，用模3分类。分类。( )()1(mod)nmmnmn,m n(, )1m n 为正整数，为正整数，例：设例：设证明证明( n )( m )mn(mod n) 1(m,n), 1( n )m(mod n) 1证明证明：( m )n(mod m )

16、1同理同理1( n )( m )mn(mod m )( n )( m )mn(mod nm ) 1第三章第三章 不定方程不定方程 不定方程是指未知数的个数多于方程的个数，而且未知量又受某种限制(如正整数或整数解)的方程或方程组。 这一章主要讨论一次不定方程整数解存在的条件，解的结构及解法，还讨论特殊的二次不定方程的解结构及解法。一、二元一次不定方程二元一次不定方程 定理：不定方程定理：不定方程ax+by=cax+by=c有整数解的充要条件是有整数解的充要条件是 d|cd|c，其中，其中 d=(a,b)d=(a,b)，并且当，并且当x=xx=x0 0 , y=y, y=y0 0是它是它的一个解时

17、，则它的一切解可以表成的一个解时，则它的一切解可以表成00bx=x -tday=y +td(t=0，1，2，)二、多元一次不定方程二、多元一次不定方程 定理：定理：n n元一次不定方程元一次不定方程a a1 1x x1 1+ + +a +an nx xn n=b =b 有整数解的充要条件是有整数解的充要条件是 (a(a1 1，a a2 2，, a, an n) | b) | b然后消去然后消去t t2 2，t t3 3，t tn-1n-1即即 可可。3312,(,),(,)nnna addaddad122设（ , ）=na aaad12n-1n则（ , , ）=1 122nnnd ba xa

18、xa xb当时，则可转化为求解可转化为求解: :1 1222 22 2333 322111111nnnnnnnnnna xa xd td ta xd tdtaxdtdta xb三、勾股数三、勾股数定理定理1 1：不定方程：不定方程 uv=wuv=w2 2，(u,v)=1 (u,v)=1 的一切正整数的一切正整数 解可以表成解可以表成 u=au=a2 2，v=bv=b2 2，w=abw=ab， 其中其中 a0a0，b0b0，(a,b)=1(a,b)=1定理定理2 2：不定方程：不定方程x x2 2+y+y2 2=z=z2 2满足满足x0 x0，y0y0，z0z0， (x,y)=1(x,y)=1，

19、2|x2|x的一切整数解可表为的一切整数解可表为 x=2abx=2ab，y=ay=a2 2-b-b2 2，z=az=a2 2+b+b2 2 其中其中ab0ab0，(a,b)=1(a,b)=1，a,ba,b一奇一偶。一奇一偶。定理定理3 3：不定方程：不定方程x x2 2+2y+2y2 2=z=z2 2满足满足(x,y)=1(x,y)=1的一切正的一切正 整数解可以表为整数解可以表为x=|ax=|a2 2-2b-2b2 2| |， y=2aby=2ab，z=az=a2 2+2b+2b2 2， 其中其中a0a0，b0b0，2 a，(a,b)=1第四章第四章 同余式同余式 本章主要研究一次同余式，一

20、次同余式组本章主要研究一次同余式，一次同余式组解存在的条件，解的数量及其求解的方法，最解存在的条件，解的数量及其求解的方法，最后讨论高次同余式解存在的条件，解的数量及后讨论高次同余式解存在的条件，解的数量及其解法。其解法。一、一元一次同余式一、一元一次同余式 定理：一元一次同余式定理：一元一次同余式(mod)axbm 有解的有解的充要条件是充要条件是( ,)a m b且有解时，且有解时，它的解的数目是它的解的数目是( ,)da m 若若(mod)axbm 有解，有解，111,( ,)( ,)( ,)abmabma ma ma m则则 化为化为111(mod)a xbm 求解求解. . 其中其中

21、从而求出同余式的解从而求出同余式的解解不定方程解不定方程111a xm yb例例1：解同余式：解同余式58x87(mod47)解：解： (47x+11x)(47+40)(mod47) 原余分式可化为原余分式可化为11x40(mod47) (11，47)=1 原同余式有解且仅有一解原同余式有解且仅有一解 解不定方程解不定方程 11x+47y=40 y0=6 ,x0=25是它的一个解是它的一个解 x25(mod47)是原同余式的解是原同余式的解解：解： (33(33，141)=3 141)=3 且且 3|1203|120 原同余式有且仅有三个解原同余式有且仅有三个解 原同余式化为原同余式化为 11

22、x11x40(mod47)40(mod47)求解。求解。 由由 例例1 1知，知，x x25(mod47)25(mod47) 是是 11x11x40(mod47)40(mod47)的一个解的一个解 例例2 2：解同余式：解同余式 33x33x120 (mod141)120 (mod141) 33x 33x120(mod141)120(mod141)的一切解为的一切解为 x x25(mod141)25(mod141)14125(mod141)72(mod141)3x 141 225(mod141)119(mod141)3x,即即33x33x120(mod141)120(mod141)的一切解为的一切解为 x x2525，7272，119 (mod141)119 (mod141) 二、二、 一元一次同余式组一元一次同余式组 11 122 2modnn nxM MbM M bMM bM 1 mod1,2,iiiM Mmin 其中其中 有且仅有解有且仅有解 1122modmodmodnnxbmxbmxbm