初等数论期末复习

1、数论教案 1整数的整除带余除法1整数的整除设a,b是整数,且bw0,如果有整数q,使得a=bq,则称b整除a,记为b|a,也称b是a的因数,a是b的倍数.如果没有整数q,使得a=bq,则称b不能整除a,记为b?a.例如2|4, 4|-12, -5|15; 2?3, -3?22.在中小学数学里，整除概念中的整数是正整数，今天讲的整除中的整数可正可负.判断是否b|a当a,b的数值较大时，可借助计算器判别.如果b除a的商数是整数，说明b|a;如果b除a的商不是整数，说明b?a.例 1 判断下列各题是否 b|a(1) 7|127? (2) 11|129? (3) 46|9529? (4) 29|593

2、9?整除的简单性质(1)如果 c|b,b|a,那么 c|a;(2)如果d|a,d|b,那么对任意整数 m,n,都有d|ma+nb.如果a1, a2 , | , an都是m的倍数，q1, q2 , J , qn是任意整数，那么 q31q2a2 qnan 是 m 的倍数.(4)如果 c|a,d|b, 那么 cd|ab。例如：2|4,2|(-6), 那么 2|4+(-6),2|4-(-6). 2|4,3|(-6),那么 2 X 3|4 X (-6).例2证明任意2个连续整数的乘积，一定可被2整除.练习 证明任意3个连续整数的乘积，一定可被3整除.2.带余除法设a,b是整数，且b0,那么有唯一一对整数

3、q,r使得a=bq+r,0 r b. (1)这里q称为b除a的商,r称为b除a的余数.例如-5=3 义(-2)+1 5=3 义 1+2-5=(-3) 义 2+15=(-3) X (-1)+2 15=(-5) X(-3), -24=(-2) X 12.事实上，以b除a的余数也可以是负的.例如-5=3 X(-1)-2=3 X (-2)+1.求b除a的余数，也称为模运算(取余):mod.可用计算器进行.具体操作：输入a-按mod(取余)键-输入b-按二键得出余数.如果b除a的余数=0,则b|a;如果b除a的余数w 0,则b?a.例3利用计算器求余数：1 1) 7 除 127;(2)11 除-129

4、;(3)46 除-9529;(4)-29 除 5939奇数、偶数及性质能被2整除的整数称为偶数.如,0,4,10,-6,-8都是偶数.不能被2整除的整数称为奇数.如,-5,-3,1,7,11都是奇数.偶数的形式为2n(n是整数)；奇数的形式为2n-1(n是整数).奇数、偶数的性质：偶数土偶数=偶数，奇数土奇数=偶数，奇数土偶数=数，偶数x偶数=偶数，偶数x奇数=偶数,奇数x奇数=数.例如 2+4,2-4,3+1,3-1,3+4,6+5设a,b是任意两个整数,则a+b与a-b同奇同偶.例如 3+5,3-5,6+3,6-3,22例4设a,b,n是任意3个整数，而且a b 2n,证明n是偶数. _2

5、例5设a是任一奇数，试证明81a 1.例6设n是正整数，证明形如3n-1整数不是完全平方数.证明 对任意整a,设a=3q或a=3q 1,于是_22222a =9q 或 a =9 q 6q+1=3(3 q 2q)+1.2即a w3n-1,故3n-1不是完全平方数.练习设n是正整数，证明形如4n-1、4n+2的整数都不是完全平方数.习题:P3-4:1t,2t.2公因数、最大公因数2 .最大公因数、辗转相除法中小学里的公因数、最大公因数的概念：几个数的公有因数叫做这几个数的公因数.公因数中最大的整数称为这几个数的最大公因数 .(1)几个数：不能确定；(2)因数、公因数：都是正整数；最大公因数：没有专

6、门的符号.定义设al向JIlaKd都是整数,d W0,如果d ai ,i=1,2, ,称d是a1, a2 J|, an的公因数，a1,a2, ( 11 ,an的公因数中最大的整数称为最大公因数.记为aaJIbaJ.如果(ai,a2)H|自储,则 称 al, a2,|M,an 互质。例 1 (-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.在中小学数学里，求正整数a,b的最大公因数主要有这个样几种方法：(1)观察法；(2)将a,b的所有公因数都求出来，再从中挑最大的；(3)用短除法.辗转相除法：设a,b是正整数，而且有 (*)(a,b) 7。例2用辗转相除法求(123,7

7、8), 练习：用辗转相除法求(66,54).下面说明辗转相除法的正确性.先证明性质1设整数a,b,c不全为0,而且有整数q使得a=bq+c则(a,b)=(b,c).证明 由a,b,c不全为0知,(a,b)、(b,c)都存在.因(a,b)|a,(a,b)|b,c=a-bq, 得(a,b)|c,又得(a,b) (b,c);反之，由(b,c)|b,(b,c)|c,a=bq+c,得(b,c)|a,(b,c)0.(短除法的根据)例 3 求(84,90),(120,36).(84,90)=3(28,30)=6(14,15)=6.(120,36)=12(10,3)=12.性质 3 (a,b)=(|a|,|b

8、|).性质 4 (a,b,c)=(a,b),c). 例 4 求(-84,120),(-120,-72),(24,-60,-96).3n 1例5设n是任意整数，证明-是既约分数.5n 2证明 设 d=(3n+1,5n+2), WJ d|3(5n+2)-5(3n+1), 即 d|1,d=1 ,所以3n+1与5n+2互质.作业1.利用辗转相除法求(84,90). 2.求(120,36).3n 13.设n是整数，证明 是既约分数。7 n 2 3整除的进一步性质及最小公倍数1 .整除的进一步性质推论1设a,b不全为零，那么有s,t Z使得as+bt=(a,b).证明将(*)中每式中的余数解出得nrn 2

9、% 4口，7 1% 3 7 2% 1 ,r2b 卬2 , a bq ,再将rn 1 , rn 2 , J J J , r2 , r1 的表达式依次代入到nrn 2 rn 1qn中就得 au+bv=n =(a,b)=d,u,v Z.例1用辗转相除法求(120,54),并求整数u,v使得120u+54v=(120,54).解120=2X 54+12,54=12 X 4+6,12=6 X 2,.(120,54)=6.12=120-2X54,6=54-12 X 4=54-(120-2 X 54) X 4=120X (-4)+54 X9. u=-4,v=9.练习用辗转相除法求(84,45),并求整数u,

10、v使得84u+45v=(84,45).设a,b都是正整数，问a,b的公因数与最大公因数有什么关系例2求(12,18)及12与18的所有正的公因数；通过这个例子，请同学们观察最大公因数与公因数有何关系能否提出自己的猜想能否证明自己的猜想性质1设d是a,b的最大公因数，那么,a,b的任一公因数都是d的因数.证明 如果d=(a,b),由性质2有u,v C Z使得au+bv=d.设s是a,b的任一公因数，则s|au,s|bv, 且s|au+bv,即s|d.a b性质 2 如果 d=(a,b),则(-，二T )=1.d d性质3如果(a,c)=1,且c|ab,则c|b.性质 4 如果(a,c)=1,则(

11、ab,c)=(b,c).性质 5 如果(a,b)=1,且 a|c,b|c, 则 ab|c.例3证明 三个连续整数的积一定可被 6整除.2最小公倍数定义如果m是al,% J中每个数的倍数，则称m是整数a1,a2,|,an 的一个公倍数. al,a2,|,an alZHan来表示.例如2,4,-3=12,15,12,20=60,6,10,15=30.的公倍中最小正整数称为 al,a2,111 ,an 的最小公倍数.用定理3 ai,a2,|,a1=|a1|,|a2|,|an |.定理4设a,b是两个正整数,则(i)a,b的任一公倍数是a,b的倍数;ab(ii)a,b= (a b).而且若(a,b)=

12、1,则a,b=ab.证明(i)设m是a,b的任一公倍数，而且m=ta,b+r,0 ra,babb ,因m,a,b都是a,b的公倍数,由r=m-ta,b 知r也是a,b的公倍数,若0r2)个正整数，且两两互素，则例 2 求123,456,-789例 3 求正整数 a,b,满足:a+b=120,(a,b)=24,a,b=144.abc例 14 设 a,b,c 是正整数，则a,b,c=b bc ca)作业:P14:1.2 .求(84,45),并求整数 u,v 使得 84u+45v=(84,45)4质数 算术基本定理1.质数定义设整数a1,如果a除了 1和a外再无其它正因数，则称a为质数，也称为素数.

13、否则，称a为合数.2,3,5,7,11都是质数，4,6,8,9,10都是合数.1-100 内有素数25个,1-1000内有素数168个,1-10000内有素数1229,10万内有素数9592个,100万之内78498个.定理1设整数a1,则a除1外的最小正因数q是素数，而且当a是合数时，q J证明 假定q是合数，设q=bc,1b,cq.因b|q,q|a,得b|a,但1bqq,即q & Ja素数判定定理设整数a1,不超过va所有素数为R，|，M,如果R?a,i=1,k,则a为素数.例1以下正整数哪个是素数哪个是合数231,89,103,169.p|(p-1)!+1.素数判别威尔逊定理：设整数p1

14、,那么p是素数的充分必要条件是例2利用威尔逊定理判别3,5,7,11都是素数.当p较大时,(p-1)!+1 的数值非常大，在实际运用时不可行。定理2设P是素数,a为任一整数，则或P|a,或(P,a)=1.证明 因(P,a)|P,P为素数，所以(P,a尸P,或(P,a)=1.即P|a,或(P,a)=1.2.整数的唯一分解定理定理3任彳a1的整数都有标准分解式：a二p11P22|pkk (3)这里pl, p2,111，pk为不同素数,整数0,i=1,k.推论 1 若正整数 a1 的标分解式为a= p1 1 p22 | pkk ，则a的正因数d为d=p11P22 |,0 ii ,i=1,k.而且a有

15、不同的正因数(11)(12)|(i k)个.推论 2设a=P11P22|Pkk,b= Pi1P22|Pkk, i 0, i0,i=1,，k.(1)(a,b)=Pl1P22|Pkk,a,b=Pl1P22| Pkk ,其中 i min( i, i), i(2)a,b共有正公因数(11)(1(3)a,b共有公因数 2(11)(1max( i, i),i=1,k.2)|l(1k)个；2)| (1 Q 个.例3求725760,154200的标准分解式，并求它们的最大公因数和最小公倍数832解因 725760=2 X5X 11X41, 154200= 2 X 3X 5 X257,所以(725760,154

16、200)= 2 X 5, 725760,154200= 28 X3X 52 x 11X41X257.例4求下列各组数的最大公因数及其公因数的个数： (1)123,78 ; (2)120,54.练习:求下列各组数的最大公因数及其公因数的个数 (1)125,70 ; (2)140,56.22例8设P,q都是大于3的素数，证明24| P q3质数的多少和质数的求法定理4素数有无穷多个.证明 反证法，设质数只有k个:Pl,P2,lll,Pk,令 MP1P2III Pk 1M1,于是 M有素数因数 p.因 pi?M,i=1,2, ,k,p|M,所以 pw pi ,i=1,2,k.这就是说，pl, P2,

17、IH, pk,p是k+1个不同素数.这与假设矛盾.1-n之间的所有素数怎样求出来1 2 3 4 5 6 7 8 9 1011 12131415161718192021 22232425262728293031 32333435363738394041 42434445464748495051 52535455565758596061 62636465666768697071 72737475767778798081 82838485868788899091 9293949596979899100按以下步骤进行：(1)删去1,剩下的后面的第一个数是 2, 2是素数；(2)删去2后面被2整除的数(

18、从4开始),2后面剩下的第一个数3是素数;删去3后面的被3整除的数(从9开始),3后面剩下的第一个数5是素数； 删去5后面的被5整除的数(从25开始),5后面剩下的第一个数7是素数;现在表中剩下的就全为素数了 ：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97.对较小范围内的素数以上求法方便，对较大范围内的素数，需要编程求素数了 .现在运行程序，求较大范围内的素数.找两个同学来求.作业:1.判别1577是否为素数 2P19:5t ;3.求725760,154200的标准分解式，并求它们的最大公因数和最小

19、公倍数，并求它们的所有公因数的个数 5函数x,x及其应用1.函数x,x 的定义定义1设x是实数，以冈 表示不超过x的最大整数，称它为x的整数部分，又称x = x 冈 为x的小数部分例 1 3.5=3,-3.5=-4,-0.1=-1,0.1=0,=3，-=-4.性质设x与y是实数，则(1)x y x y；(2)若 m是整数，m x=m x；(3)若 0 x0,则a=bA +ba. b b设 a=bq r,0 rb 得 q ，故J =q,7,所以 a=b； +b3b b b b b b b(5)设a与b是正整数，则1-a中能被b整除的整数有b个。证明能被b整除的正整数是b,2b,3b,aa，因此，

20、若数1,2, ,a中能被b整除的整数有k个，则kb a(k+1)b k 7 2 是整数.Th1不定方程(1)有整数解充分必要条件是,(a1，a2，lll，an) |N.例1求9x+24y-5z=1000的一切整数解.解 因(9,24,-5)=1,所以不定方程有整数解，因(9,24)=3,可设9x+24y=3u,于是 3x+8y=u, 3u-5z=100的通解为 x=u-8s,y=-u+3s,s Z,的通解为 u=5t,z=-20+3t,t Z.故原不定方程的通解为 x=5t-8s,y=-5t+3s,z=-20+3t,s,t Z.例2把17/60写成分母两两互质的三个既约分数之和17 x y z

21、解 因60=3X4X5，设603 4 5 ,整理得20x+15y+12z=17.因(20,15,12=1,不定故方程有整数解，设20x+15y=5u,则 4x+3y=u,5u+12z=17.的通解为 x=u-3s,y=-u+4s,s C Z,的通解为 u=1-12t,z=1+5t,t CZ. 故原不定方程的通解为 x=1-12t-3s,y=-1+12t+4s,z=1+5t,s,t Z.171 12t 3s所以，603112t 4s 15t45 .当 t=s=0 时,x=-y=z=1,此时有1711 160 345 .作业:1求3x+6y-5z=15的一切整数解. 3勾股数2221 .不定方程x

22、 y z222不定方程x y z的一组整数解(x,y,z)称为一组勾股数.例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股数.222定理不定方程x y z ,(1)满足 x0,y0,z0,(x,y)=1,2 |x(2)21 221 2一切正整数解可由下式表出：x=2ab,y= a b ,z= a b(3) a=3,b=2,x=12,y=5,z=13; a=4,b=3,x=24,y=7,z=25; a=5,b=4,x=40,y=9,z=41.其中 ab0,(a,b)=1,a,b一奇一偶. a=2,b=1,x=4,y=3,z=5; a=4,b=1,x=8,y

23、=15,z=17; a=5,b=2,x=20,y=21,z=29;2.其它不定方程例3求不定方程的全部整数解 xy=6, xy-x+y-4=0.解 x= 1 且 y= 6,或 x= 6,且 y= 1,或 x= 2,且 y= 3,或 x= 3,且 y= 2。原方程可变为(x+1)(y-1)-3=0,即(x+1)(y-1)=3.所以有x+1 = 1且y-1= 3,或x+1 = 3,且y-1= 1.故得不定方程的全部整数解为x=0,y=4;x=-2,y=-2;x=2,y=2,x=-4,y=0.222作业:1.写出不定方程x y z的满足x0,y0,z0,(x,y)=1,2 |x 的2组正整数解2.求

24、不定方程xy-x-y-4=0的全部整数解.第三章同余 1同余的概念及其性质1.同余及性质定义设m是正整数,称m为模.a,b Z,如果a,b被m除所得的余数相同,则称a,b对模m同余，记为amb(modm).如果a,b被m除所得的余数不同,则称a,b对模m不同余，记为a?b(modm).例如 4 三7(mod3),6 三 11(mod5),4?5(mod3),6?8(mod5).定理1整数a,b对模m同余的充分必要条件是，m|a-b,即a=b+mt,t Z.证明 必要性，若 am b(modm).可设 a=msa=r,b=mua=r,s,u Z,贝U a-b=m(s-u)=mt, T=s-u C

25、 Z.所以 m|a-b,且 a=b+mt.充分性，设 a=ms+r1 ,b=mu+r2 ,a-b=m(s-u)+ r1 - r2.因 m|a-b,所以 m| r1- r2,但| r1 - r211,(a,m)=1,则 a 1(mod m).证明取模m的一个简化剩余系b1,b2, ,bs,(s(m),由于(a, m)=1,由 3定理3知，abab2, ,abs也是模m的一个简化剩余系,于是(ab)(ab2) I |(ats) bb2 nh(modm)即 a (m)b1b2 111bs b1b2 1nbs(mod m)因 卜同 j=1,2，(m),所以(m, b,b2,b(m)=1，从而 a (m

26、)1(m0d m).证毕。P 1 P推论(费尔玛定理)设P是素数，则a 1(modP),而且aCZ, aa(modP).PP 1证明若 p |a,则 a a 0(modP),若(a, m)=1 ,则 a 1(modP),所以P a a(mod P) .P 1 q 1例1设p,q是不同的素数,证明q p 1(modpq).P 1 q 1.证明 因p,q是不同的素数，所以(p,q)=1,由费尔玛定理知，q p 1(modp),P 1 q 1P 1 q 1q p 1 (modq).由同余的性质得，q p 1 (modpq).例2设pw2,5为素数,整数a的十进制数由p-1位，而且每一位上的数字都是9

27、,证明p |a.P 1,证明因p*2,5为素数，所以(10,p)=1,由费尔玛止理得,a=99 - -9=101 =0(modp),即 p |a.例3若变量x取整数时，多项式P(x)= b0 b1x III bnxn的值总为整数，则称P(x)113TT7(x x) 为整值多项式.证明，2730是整值多项式.证明2730=2 X 3X 5X 7X 13，当x取整数值时，由费尔玛定理，13c-13x x 0(mod13)，即 13| x x.x13 x (x7 x)(x6 1) 0(mod7),即 7| x13 x.13z 58413xx(xx)(xx1)0(mod5),即 5|x x.13, 3

28、、， 10864213xx(xx)(xxxx x 1) 0(mod3),即 3|x x.x13x(x2x)(x11IIIx1) 0(mod2),即 2| x13x.一一一13因2,3，两两互质，由整除的性质知，2 X3X5X7X13| x x,即2730|1 1 13、13- (xx)一x x.故2730是整值多项式.例4今天是星期一，问从今天起再过1010天是星期几2233解 10 3(mod7), 1032(mod7), 1032|3 61 (mod7),所以106 1 (mod7) o 又因 10 -2(mod6), 102 222(mod6),故10102 4 (mod6)010101

29、0设10 6k 4 , k为正整数，于是10106k 41010 103 4 (mod7),这就是说，从今天起再过10天是星期五(1+4)。2011 2011例5求201 1 2011 被8除的余数作业:P64:1.例32.分数与循环小数定义 如果无限小数0. a1a2lllanlll ( an 0,1 , ,9)从任何一位数后不全为0,且能找到两个整数s0,t 0,使得as ias i kt,i=1,2,，t,k=0,1,2,(*)则称它为循环小数，并简记为0. a1a2lllasas 1lllast.对满足(*)的最小正整数t,称asiii/st为循环节，称t为循环节的长度.若最小的s=o

30、,那小数就叫做纯循环小数，否则叫做混循环 小数。a定理2有理数b ,0ab,(a,b)=1,能表成纯循环小数的充分必要条件是，(b,10)=1.a推论 有理数b ,0ab,(a,b)=1,是纯有限小数的充分必要条件是(b,10) *1.aa证明 必要性：若有理数b能表成纯循环小数，则由0b1及定义知ab =0. a1a2 Mka1IMatlll=0. a1a2lat+10 tpaa/llaaillat III.于是10tbaa2 at +0.a1a2 |ata1|at|=q+b.所以 a(10t 1)bq, H(a,b)=1,所以 b110t 1,设 10t 1=qb,则10t qb =1,故

31、(b,10)=1.充分性：如果(b,10)=1,由定理1知有一正整数 t使彳# 10t 1 (modb),0t (b),又有 10% a (modb),设 10 a qb a ,则qb(10t 1)a 0,q (10t 1)a 10tbt 1令 q=a110a210t 2at,显然a1，a21at不全为9,也不全为0.而且q10t0.a1a2 |at,又由 10ta qba _q_a 得 b 10t17a = 3mat10t b反复利用a -小t各即得b =0. a1a2IOata1IMatlll=0.a1111at.定理 3 有理数 b ,0ab,(a,b)=1,不全为0, (b1,10)=

32、1,bi 1,则b能表成纯循环小数.其中不循环部分的位数是max(,)四章同余方程 1基本的概念及一次同余方程1.同余方程的概念定义设f(x)=a0 a1xIII anx：这里 aiZ ,i=0,1,n.m是正整数，则称f(x)=a0 a1x HI anxn 0(modm).为同余式，或模m的同余方程.若an，0(modm),n称为同余方程(1)的次数.若a Z而且f(a)三0(modm),则称xma(modm历同余方程(1)的解.-2例1 f(x)= x x 3m0(mod5)是模5的2次同余方程，由于f(1)=5 =0(mod5),因此xm1(mod5)是同余方程的一个解.另外x x= m

33、1t x0, m1 m/dt=0, 1, 2,，(mod5)也是同余方程的一个解.2一次同余方程一次同余方程的一般形式:ax= b(modm),a/0(modm)(2)例如 2x =3(mod5), 4x 三 8(mod7), 3x 三9(mod11),定理1同余方程(2)有解的充分必要条件是，(a,m)|b.而且当(2)有解时,(2)对模m来说有(a,m)个解.证明(2)有解的充分必要条件是ax-my=b有整数解，充分必要条件是(a,m)|b.设d=(a,m),如果(2)有解，则满足(2)的一切整数可以写成x=m1t x。，m1 tm/d , t=0, 1, 2,，但对模m来说，这些整数可以写成x= m1t x0 (modm),t=0,1,2,d-1. 而它们关于模m两两不同余.例2解一次同余方程 2x+6m0 (mod4),x=解 因(2,4)6,由定理1,同余方程有(2,4)=2个整数解.设2x-4y=-6,则x-2y=-3,由此可得x=-1+2t,t Z,所以同余方程的结为 -1+2t(