初等數(shù)論期末復習

1、數(shù)論教案 1整數(shù)的整除帶余除法1整數(shù)的整除設a,b是整數(shù),且bw0,如果有整數(shù)q,使得a=bq,則稱b整除a,記為b|a,也稱b是a的因數(shù),a是b的倍數(shù).如果沒有整數(shù)q,使得a=bq,則稱b不能整除a,記為b?a.例如2|4, 4|-12, -5|15; 2?3, -3?22.在中小學數(shù)學里，整除概念中的整數(shù)是正整數(shù)，今天講的整除中的整數(shù)可正可負.判斷是否b|a當a,b的數(shù)值較大時，可借助計算器判別.如果b除a的商數(shù)是整數(shù)，說明b|a;如果b除a的商不是整數(shù)，說明b?a.例 1 判斷下列各題是否 b|a(1) 7|127? (2) 11|129? (3) 46|9529? (4) 29|593

2、9?整除的簡單性質(zhì)(1)如果 c|b,b|a,那么 c|a;(2)如果d|a,d|b,那么對任意整數(shù) m,n,都有d|ma+nb.如果a1, a2 , | , an都是m的倍數(shù)，q1, q2 , J , qn是任意整數(shù)，那么 q31q2a2 qnan 是 m 的倍數(shù).(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個連續(xù)整數(shù)的乘積，一定可被2整除.練習 證明任意3個連續(xù)整數(shù)的乘積，一定可被3整除.2.帶余除法設a,b是整數(shù)，且b0,那么有唯一一對整數(shù)

3、q,r使得a=bq+r,0 r b. (1)這里q稱為b除a的商,r稱為b除a的余數(shù).例如-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的余數(shù)也可以是負的.例如-5=3 X(-1)-2=3 X (-2)+1.求b除a的余數(shù)，也稱為模運算(取余):mod.可用計算器進行.具體操作：輸入a-按mod(取余)鍵-輸入b-按二鍵得出余數(shù).如果b除a的余數(shù)=0,則b|a;如果b除a的余數(shù)w 0,則b?a.例3利用計算器求余數(shù)：1 1) 7 除 127;(2)11 除-129

4、;(3)46 除-9529;(4)-29 除 5939奇數(shù)、偶數(shù)及性質(zhì)能被2整除的整數(shù)稱為偶數(shù).如,0,4,10,-6,-8都是偶數(shù).不能被2整除的整數(shù)稱為奇數(shù).如,-5,-3,1,7,11都是奇數(shù).偶數(shù)的形式為2n(n是整數(shù))；奇數(shù)的形式為2n-1(n是整數(shù)).奇數(shù)、偶數(shù)的性質(zhì)：偶數(shù)土偶數(shù)=偶數(shù)，奇數(shù)土奇數(shù)=偶數(shù)，奇數(shù)土偶數(shù)=數(shù)，偶數(shù)x偶數(shù)=偶數(shù)，偶數(shù)x奇數(shù)=偶數(shù),奇數(shù)x奇數(shù)=數(shù).例如 2+4,2-4,3+1,3-1,3+4,6+5設a,b是任意兩個整數(shù),則a+b與a-b同奇同偶.例如 3+5,3-5,6+3,6-3,22例4設a,b,n是任意3個整數(shù)，而且a b 2n,證明n是偶數(shù). _2

5、例5設a是任一奇數(shù)，試證明81a 1.例6設n是正整數(shù)，證明形如3n-1整數(shù)不是完全平方數(shù).證明 對任意整a,設a=3q或a=3q 1,于是_22222a =9q 或 a =9 q 6q+1=3(3 q 2q)+1.2即a w3n-1,故3n-1不是完全平方數(shù).練習設n是正整數(shù)，證明形如4n-1、4n+2的整數(shù)都不是完全平方數(shù).習題:P3-4:1t,2t.2公因數(shù)、最大公因數(shù)2 .最大公因數(shù)、輾轉(zhuǎn)相除法中小學里的公因數(shù)、最大公因數(shù)的概念：幾個數(shù)的公有因數(shù)叫做這幾個數(shù)的公因數(shù).公因數(shù)中最大的整數(shù)稱為這幾個數(shù)的最大公因數(shù) .(1)幾個數(shù)：不能確定；(2)因數(shù)、公因數(shù)：都是正整數(shù)；最大公因數(shù)：沒有專

6、門的符號.定義設al向JIlaKd都是整數(shù),d W0,如果d ai ,i=1,2, ,稱d是a1, a2 J|, an的公因數(shù)，a1,a2, ( 11 ,an的公因數(shù)中最大的整數(shù)稱為最大公因數(shù).記為aaJIbaJ.如果(ai,a2)H|自儲,則 稱 al, a2,|M,an 互質(zhì)。例 1 (-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.在中小學數(shù)學里，求正整數(shù)a,b的最大公因數(shù)主要有這個樣幾種方法：(1)觀察法；(2)將a,b的所有公因數(shù)都求出來，再從中挑最大的；(3)用短除法.輾轉(zhuǎn)相除法：設a,b是正整數(shù)，而且有 (*)(a,b) 7。例2用輾轉(zhuǎn)相除法求(123,7

7、8), 練習：用輾轉(zhuǎn)相除法求(66,54).下面說明輾轉(zhuǎn)相除法的正確性.先證明性質(zhì)1設整數(shù)a,b,c不全為0,而且有整數(shù)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.(短除法的根據(jù))例 3 求(84,90),(120,36).(84,90)=3(28,30)=6(14,15)=6.(120,36)=12(10,3)=12.性質(zhì) 3 (a,b)=(|a|,|b

8、|).性質(zhì) 4 (a,b,c)=(a,b),c). 例 4 求(-84,120),(-120,-72),(24,-60,-96).3n 1例5設n是任意整數(shù)，證明-是既約分數(shù).5n 2證明 設 d=(3n+1,5n+2), WJ d|3(5n+2)-5(3n+1), 即 d|1,d=1 ,所以3n+1與5n+2互質(zhì).作業(yè)1.利用輾轉(zhuǎn)相除法求(84,90). 2.求(120,36).3n 13.設n是整數(shù)，證明 是既約分數(shù)。7 n 2 3整除的進一步性質(zhì)及最小公倍數(shù)1 .整除的進一步性質(zhì)推論1設a,b不全為零，那么有s,t Z使得as+bt=(a,b).證明將(*)中每式中的余數(shù)解出得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用輾轉(zhuǎn)相除法求(120,54),并求整數(shù)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.練習用輾轉(zhuǎn)相除法求(84,45),并求整數(shù)u,

10、v使得84u+45v=(84,45).設a,b都是正整數(shù)，問a,b的公因數(shù)與最大公因數(shù)有什么關系例2求(12,18)及12與18的所有正的公因數(shù)；通過這個例子，請同學們觀察最大公因數(shù)與公因數(shù)有何關系能否提出自己的猜想能否證明自己的猜想性質(zhì)1設d是a,b的最大公因數(shù)，那么,a,b的任一公因數(shù)都是d的因數(shù).證明 如果d=(a,b),由性質(zhì)2有u,v C Z使得au+bv=d.設s是a,b的任一公因數(shù)，則s|au,s|bv, 且s|au+bv,即s|d.a b性質(zhì) 2 如果 d=(a,b),則(-，二T )=1.d d性質(zhì)3如果(a,c)=1,且c|ab,則c|b.性質(zhì) 4 如果(a,c)=1,則(

11、ab,c)=(b,c).性質(zhì) 5 如果(a,b)=1,且 a|c,b|c, 則 ab|c.例3證明 三個連續(xù)整數(shù)的積一定可被 6整除.2最小公倍數(shù)定義如果m是al,% J中每個數(shù)的倍數(shù)，則稱m是整數(shù)a1,a2,|,an 的一個公倍數(shù). al,a2,|,an alZHan來表示.例如2,4,-3=12,15,12,20=60,6,10,15=30.的公倍中最小正整數(shù)稱為 al,a2,111 ,an 的最小公倍數(shù).用定理3 ai,a2,|,a1=|a1|,|a2|,|an |.定理4設a,b是兩個正整數(shù),則(i)a,b的任一公倍數(shù)是a,b的倍數(shù);ab(ii)a,b= (a b).而且若(a,b)=

12、1,則a,b=ab.證明(i)設m是a,b的任一公倍數(shù)，而且m=ta,b+r,0 ra,babb ,因m,a,b都是a,b的公倍數(shù),由r=m-ta,b 知r也是a,b的公倍數(shù),若0r2)個正整數(shù)，且兩兩互素，則例 2 求123,456,-789例 3 求正整數(shù) a,b,滿足:a+b=120,(a,b)=24,a,b=144.abc例 14 設 a,b,c 是正整數(shù)，則a,b,c=b bc ca)作業(yè):P14:1.2 .求(84,45),并求整數(shù) u,v 使得 84u+45v=(84,45)4質(zhì)數(shù) 算術基本定理1.質(zhì)數(shù)定義設整數(shù)a1,如果a除了 1和a外再無其它正因數(shù)，則稱a為質(zhì)數(shù)，也稱為素數(shù).

13、否則，稱a為合數(shù).2,3,5,7,11都是質(zhì)數(shù)，4,6,8,9,10都是合數(shù).1-100 內(nèi)有素數(shù)25個,1-1000內(nèi)有素數(shù)168個,1-10000內(nèi)有素數(shù)1229,10萬內(nèi)有素數(shù)9592個,100萬之內(nèi)78498個.定理1設整數(shù)a1,則a除1外的最小正因數(shù)q是素數(shù)，而且當a是合數(shù)時，q J證明 假定q是合數(shù)，設q=bc,1b,cq.因b|q,q|a,得b|a,但1bqq,即q & Ja素數(shù)判定定理設整數(shù)a1,不超過va所有素數(shù)為R，|，M,如果R?a,i=1,k,則a為素數(shù).例1以下正整數(shù)哪個是素數(shù)哪個是合數(shù)231,89,103,169.p|(p-1)!+1.素數(shù)判別威爾遜定理：設整數(shù)p1

14、,那么p是素數(shù)的充分必要條件是例2利用威爾遜定理判別3,5,7,11都是素數(shù).當p較大時,(p-1)!+1 的數(shù)值非常大，在實際運用時不可行。定理2設P是素數(shù),a為任一整數(shù)，則或P|a,或(P,a)=1.證明 因(P,a)|P,P為素數(shù)，所以(P,a尸P,或(P,a)=1.即P|a,或(P,a)=1.2.整數(shù)的唯一分解定理定理3任彳a1的整數(shù)都有標準分解式：a二p11P22|pkk (3)這里pl, p2,111，pk為不同素數(shù),整數(shù)0,i=1,k.推論 1 若正整數(shù) a1 的標分解式為a= p1 1 p22 | pkk ，則a的正因數(shù)d為d=p11P22 |,0 ii ,i=1,k.而且a有

15、不同的正因數(shù)(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共有正公因數(shù)(11)(1(3)a,b共有公因數(shù) 2(11)(1max( i, i),i=1,k.2)|l(1k)個；2)| (1 Q 個.例3求725760,154200的標準分解式，并求它們的最大公因數(shù)和最小公倍數(shù)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求下列各組數(shù)的最大公因數(shù)及其公因數(shù)的個數(shù)： (1)123,78 ; (2)120,54.練習:求下列各組數(shù)的最大公因數(shù)及其公因數(shù)的個數(shù) (1)125,70 ; (2)140,56.22例8設P,q都是大于3的素數(shù)，證明24| P q3質(zhì)數(shù)的多少和質(zhì)數(shù)的求法定理4素數(shù)有無窮多個.證明 反證法，設質(zhì)數(shù)只有k個:Pl,P2,lll,Pk,令 MP1P2III Pk 1M1,于是 M有素數(shù)因數(shù) p.因 pi?M,i=1,2, ,k,p|M,所以 pw pi ,i=1,2,k.這就是說，pl, P2,

17、IH, pk,p是k+1個不同素數(shù).這與假設矛盾.1-n之間的所有素數(shù)怎樣求出來1 2 3 4 5 6 7 8 9 1011 12131415161718192021 22232425262728293031 32333435363738394041 42434445464748495051 52535455565758596061 62636465666768697071 72737475767778798081 82838485868788899091 9293949596979899100按以下步驟進行：(1)刪去1,剩下的后面的第一個數(shù)是 2, 2是素數(shù)；(2)刪去2后面被2整除的數(shù)(

18、從4開始),2后面剩下的第一個數(shù)3是素數(shù);刪去3后面的被3整除的數(shù)(從9開始),3后面剩下的第一個數(shù)5是素數(shù)； 刪去5后面的被5整除的數(shù)(從25開始),5后面剩下的第一個數(shù)7是素數(shù);現(xiàn)在表中剩下的就全為素數(shù)了 ：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.對較小范圍內(nèi)的素數(shù)以上求法方便，對較大范圍內(nèi)的素數(shù)，需要編程求素數(shù)了 .現(xiàn)在運行程序，求較大范圍內(nèi)的素數(shù).找兩個同學來求.作業(yè):1.判別1577是否為素數(shù) 2P19:5t ;3.求725760,154200的標準分解式，并求它們的最大公因數(shù)和最小

19、公倍數(shù)，并求它們的所有公因數(shù)的個數(shù) 5函數(shù)x,x及其應用1.函數(shù)x,x 的定義定義1設x是實數(shù)，以岡 表示不超過x的最大整數(shù)，稱它為x的整數(shù)部分，又稱x = x 岡 為x的小數(shù)部分例 1 3.5=3,-3.5=-4,-0.1=-1,0.1=0,=3，-=-4.性質(zhì)設x與y是實數(shù)，則(1)x y x y；(2)若 m是整數(shù)，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是正整數(shù)，則1-a中能被b整除的整數(shù)有b個。證明能被b整除的正整數(shù)是b,2b,3b,aa，因此，

20、若數(shù)1,2, ,a中能被b整除的整數(shù)有k個，則kb a(k+1)b k 7 2 是整數(shù).Th1不定方程(1)有整數(shù)解充分必要條件是,(a1，a2，lll，an) |N.例1求9x+24y-5z=1000的一切整數(shù)解.解 因(9,24,-5)=1,所以不定方程有整數(shù)解，因(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寫成分母兩兩互質(zhì)的三個既約分數(shù)之和17 x y z

21、解 因60=3X4X5，設603 4 5 ,整理得20x+15y+12z=17.因(20,15,12=1,不定故方程有整數(shù)解，設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 .作業(yè):1求3x+6y-5z=15的一切整數(shù)解. 3勾股數(shù)2221 .不定方程x

22、 y z222不定方程x y z的一組整數(shù)解(x,y,z)稱為一組勾股數(shù).例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股數(shù).222定理不定方程x y z ,(1)滿足 x0,y0,z0,(x,y)=1,2 |x(2)21 221 2一切正整數(shù)解可由下式表出：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求不定方程的全部整數(shù)解 xy=6, xy-x+y-4=0.解 x= 1 且 y= 6,或 x= 6,且 y= 1,或 x= 2,且 y= 3,或 x= 3,且 y= 2。原方程可變?yōu)?x+1)(y-1)-3=0,即(x+1)(y-1)=3.所以有x+1 = 1且y-1= 3,或x+1 = 3,且y-1= 1.故得不定方程的全部整數(shù)解為x=0,y=4;x=-2,y=-2;x=2,y=2,x=-4,y=0.222作業(yè):1.寫出不定方程x y z的滿足x0,y0,z0,(x,y)=1,2 |x 的2組正整數(shù)解2.求

24、不定方程xy-x-y-4=0的全部整數(shù)解.第三章同余 1同余的概念及其性質(zhì)1.同余及性質(zhì)定義設m是正整數(shù),稱m為模.a,b Z,如果a,b被m除所得的余數(shù)相同,則稱a,b對模m同余，記為amb(modm).如果a,b被m除所得的余數(shù)不同,則稱a,b對模m不同余，記為a?b(modm).例如 4 三7(mod3),6 三 11(mod5),4?5(mod3),6?8(mod5).定理1整數(shù)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是素數(shù)，則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是不同的素數(shù),證明q p 1(modpq).P 1 q 1.證明 因p,q是不同的素數(shù)，所以(p,q)=1,由費爾瑪定理知，q p 1(modp),P 1 q 1P 1 q 1q p 1 (modq).由同余的性質(zhì)得，q p 1 (modpq).例2設pw2,5為素數(shù),整數(shù)a的十進制數(shù)由p-1位，而且每一位上的數(shù)字都是9

27、,證明p |a.P 1,證明因p*2,5為素數(shù)，所以(10,p)=1,由費爾瑪止理得,a=99 - -9=101 =0(modp),即 p |a.例3若變量x取整數(shù)時，多項式P(x)= b0 b1x III bnxn的值總為整數(shù)，則稱P(x)113TT7(x x) 為整值多項式.證明，2730是整值多項式.證明2730=2 X 3X 5X 7X 13，當x取整數(shù)值時，由費爾瑪定理，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，兩兩互質(zhì)，由整除的性質(zhì)知，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為正整數(shù)，于是10106k 41010 103 4 (mod7),這就是說，從今天起再過10天是星期五(1+4)。2011 2011例5求201 1 2011 被8除的余數(shù)作業(yè):P64:1.例32.分數(shù)與循環(huán)小數(shù)定義 如果無限小數(shù)0. a1a2lllanlll ( an 0,1 , ,9)從任何一位數(shù)后不全為0,且能找到兩個整數(shù)s0,t 0,使得as ias i kt,i=1,2,，t,k=0,1,2,(*)則稱它為循環(huán)小數(shù)，并簡記為0. a1a2lllasas 1lllast.對滿足(*)的最小正整數(shù)t,稱asiii/st為循環(huán)節(jié)，稱t為循環(huán)節(jié)的長度.若最小的s=o

30、,那小數(shù)就叫做純循環(huán)小數(shù)，否則叫做混循環(huán) 小數(shù)。a定理2有理數(shù)b ,0ab,(a,b)=1,能表成純循環(huán)小數(shù)的充分必要條件是，(b,10)=1.a推論 有理數(shù)b ,0ab,(a,b)=1,是純有限小數(shù)的充分必要條件是(b,10) *1.aa證明 必要性：若有理數(shù)b能表成純循環(huán)小數(shù)，則由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知有一正整數(shù) 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 有理數(shù) b ,0ab,(a,b)=1,不全為0, (b1,10)=

32、1,bi 1,則b能表成純循環(huán)小數(shù).其中不循環(huán)部分的位數(shù)是max(,)四章同余方程 1基本的概念及一次同余方程1.同余方程的概念定義設f(x)=a0 a1xIII anx：這里 aiZ ,i=0,1,n.m是正整數(shù)，則稱f(x)=a0 a1x HI anxn 0(modm).為同余式，或模m的同余方程.若an，0(modm),n稱為同余方程(1)的次數(shù).若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有整數(shù)解，充分必要條件是(a,m)|b.設d=(a,m),如果(2)有解，則滿足(2)的一切整數(shù)可以寫成x=m1t x。，m1 tm/d , t=0, 1, 2,，但對模m來說，這些整數(shù)可以寫成x= m1t x0 (modm),t=0,1,2,d-1. 而它們關于模m兩兩不同余.例2解一次同余方程 2x+6m0 (mod4),x=解 因(2,4)6,由定理1,同余方程有(2,4)=2個整數(shù)解.設2x-4y=-6,則x-2y=-3,由此可得x=-1+2t,t Z,所以同余方程的結為 -1+2t(