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

1、,,第二章 同余,2024年3月19日2時57分,1、同余的概念:,定義2. 1,若a 和b 除以m 所得余數(shù)不同，則稱a，b 對模m 不同余，記作 a b (mod m).,設(shè)m為正整數(shù)，稱為模。若用m去除兩個整數(shù) a 和 b 所得的余數(shù)相同，則稱a 和b 對模 m 同余, 記作 a ≡b (mod m). （1）

2、 讀作a 同余于b 模m。,一、同余的概念及基本性質(zhì),2024年3月19日2時57分,2、同余的性質(zhì)：,E,(1) 反身性： a ≡ a (mod m).(2) 對稱性：若 a ≡ b (mod m)， 則 b ≡ a (mod m). (3) 傳遞性：若 a ≡ b (mod m), b ≡ c (mod m),

3、 則 a ≡ c (mod m).,(4) 若a ≡b (mod m)，c ≡d (mod m) ， 則 a + c ≡ b + d (mod m) , a－c ≡ b－d (mod m).同余式可以相加減。,2024年3月19日2時57分,我喜歡數(shù)學(xué),E,性質(zhì)(5) 若a ≡b (mod m)，c ≡d (mod m) ， 則 ac ≡ bd (m

4、od m) .同余式可以相乘。推論　若a ≡b (mod m)， 則 a k ≡ b k (mod m), k 為任意整數(shù).同余式的數(shù)乘。,,推廣,2024年3月19日2時57分,,性質(zhì)(6),性質(zhì)(7),若a =a1d, b =b1d, (m, d) =1, a ≡b (mod m)，則 a1 ≡ b1 (mod m) .,性質(zhì)(8),d為a，b及m的任一正公約數(shù)，則,若a ≡b (mod m)，k

5、 為正整數(shù) ， 則 ka ≡ kb (mod km) .,2024年3月19日2時57分,性質(zhì)(9),若 a ≡b (mod m1), a ≡b (mod m2), m=[ m1, m2 ], 則 a ≡ b (mod m) .,性質(zhì)(10) 設(shè)d ≥1， d | m，若a ≡b (mod m) ， 則 a ≡ b (mod d ) .,E,New,若a ≡b (mod

6、m)，則 (a，m) = (b，m).,性質(zhì)(11),2024年3月19日2時57分,棄九法,正整數(shù)四則運算(含乘方) 的快速驗算方法,例7 用棄九法驗算 28947×34578 =1001865676 是否正確.,棄九法只是運算結(jié)果正確的必要條件，而非充分條件 ! 因此只能判誤.,解,若通過計算，a、b的和與積分別是s與p. 而r1、r2、r3、r4 分別是a、b、s、p被 9 除所得的余數(shù), 由同余的加減乘性質(zhì)可知，如

7、果r1 +r2與r3、 r1 · r2與r4關(guān)于模 9 不同余，那么計算一定錯了.,2024年3月19日2時57分,利用同余解答整除問題,例1 求7406寫成十進制數(shù)時的個位數(shù)。,數(shù) a 能被 m 整除等價于a ≡0 (mod m).,72 ≡49 ≡－ 1(mod 10),,或 74 ≡ 1(mod 10), 7406 ≡ 7404 · 72≡9 (mod 10).,(72 )203 ≡－1 ≡9 (m

8、od 10),,2024年3月19日2時57分,二、剩余類與剩余系,定理2.2.1 設(shè)m為正整數(shù)，則全部整數(shù)可分成m個集合,記作[0]，[1]，…，[m－1]，其中[r] (0 ≤ r ≤m－1)是由一切形如 mq + r (q∈Z) 的整數(shù)所組成的，并且具有下列性質(zhì)：(1)每一整數(shù)必包含在而且僅在上述的一個集合中.(2)兩個整數(shù)同在一個集合中的充分必要條件為這兩個整數(shù)對模 m 同余。,2024年3月19日2時57分,定義2.

9、2 設(shè)m為正整數(shù)，則全部整數(shù)分成的 m個集合[0]，[1]，…，[m－1]稱為模m的剩余類,一個剩余類中任一數(shù)叫做它的同類的數(shù)的剩余。,2024年3月19日2時57分,定理2.2.2　設(shè)m為正整數(shù)，則 （1）在任意取定的 m + 1 個整數(shù)中，必有兩個數(shù)對模 m 同余。 （2）存在 m 個數(shù)兩兩對模m不同余。,完全剩余系,定義2. 3 設(shè) m 為正整數(shù)，則從模 m 的每個剩余類中各取一個數(shù)所作成的集合，稱為模 m 的

10、一個完全剩余系.,2024年3月19日2時57分,定理2.2.4 若 a1, a2，…, am 是模m的完全剩余系，,且(a, m) =1, b 為任意整數(shù)，則 aa1 +b, aa2 +b, …, aam +b 也是模 m 的一個完全剩余系。,定理2.2.3　設(shè)m 為正整數(shù)，整數(shù)集合{ a1, a2 , … , am}是模 m 的完全剩余系的充分必要條件是：ai aj (mod m) ( i≠ j ).,,下面例1

11、給出模m的另外完全剩余系——絕對最小完,全剩余系.,2024年3月19日2時57分,例3 驗證：{－11, －4, 18, 20, 32 }是模 5 的一個完全剩余系。,證：只要證兩兩不同余即可, 也就是它們各屬于不同的剩余類. 從而只要證明它們各與最小非負完全剩余系中的某一個數(shù)同余即可.,－11與4, －4與1, 18與3, 20與0, 32與2分別對模5同余，所以結(jié)論成立。,2024年3月19日2時57分,定義 2.4,時，,m

12、為質(zhì)數(shù)當且僅當,設(shè) m 是正整數(shù)，用? (m)表示不大于 m 且與 m 互質(zhì)的自然數(shù)的個數(shù)．稱 ? (m)為歐拉函數(shù)．,三、 歐拉函數(shù)和簡化剩余系,2024年3月19日2時57分,定義 2.5,定理2.2.6　設(shè) m 是正整數(shù)，則模m的一個剩余類是與模 m互質(zhì)的剩余類的充分必要條件為：這個模m的剩余類中有一數(shù)與m互質(zhì)。,設(shè) m 是正整數(shù)，若一個模m的剩余類中的數(shù)與m互質(zhì)，則稱這個模m的剩余類為與模m互質(zhì)的剩余類。在與模 m互質(zhì)的所有剩余

13、類中，從每一類各取一數(shù)所作成的集合叫做模 m 的一個簡化剩余系.,2024年3月19日2時57分,簡化剩余系的充要條件,定理2.2 7 整數(shù)集合　　　　　　　為模m的簡化剩余系的充要條件是： ( i ) (ai, m) =1 ( 1≤i ≤? (m) ); ( ii ) 各數(shù)關(guān)于模m兩兩不同余．,2024年3月19日2時57分,定理 2.2.10,若 m 的標準分解式是,則,歐拉函數(shù)的計算公式,推論 若

14、 則,定理 2.2.8 若( a，m ) = 1 , x 通過模 m 的簡化剩余系，則 ax 也通過模 m 的簡化剩余系。,即{x1, x2, … xk}是模m的一個簡化剩余系，則{ax1, ax2, …, axk}也是模m的簡化剩余系。這里k = ? (m)。,2024年3月19日2時57分,歐拉函數(shù)? (m) 的計算,將,代入定理１中的公式，就有,特別地，對于質(zhì)數(shù) p，有,例 4　計算? (588000)

15、 解：因 588000＝25 · 3 · 53 ·7，故由公式　可得,? (588000) ＝(25 －24) (3－1) (53－ 52) (72 － 7)=19200.,2024年3月19日2時57分,四　歐拉定理,,定理 2.3.1 ( 歐拉定理) 若為大于1的整數(shù)， a為整數(shù)且( a ，m) = 1, 則,應(yīng)用實例,例5 求112001除以60的余數(shù).解:又(11, 60)=1,由歐拉定理得

16、1116 ≡1(mod 60),,故　1116×125≡1 (mod 60), 112001 ≡11 (mod 60).,一次同余方程,定義 3. 1,例如同余方程　x3 + 2x－12≡0 (mod5)．,定義3.2 如果整數(shù) a 滿足 f (a)≡0 (mod m) , 那么我們把 x ≡ a ( mod m）叫做同余方程 (1)的一個解.,第三章 同余方程,解同余方程或解同余式,即，逐一將 0, 1, …，m－1

17、 代入 (1) 中進行驗算就可以求得同余方程 (1)的解．,上述定義說明, 同余方程 (1)的一個解是 m 的一個剩余類． m 的剩余類只有m個，因此,同余方程 (1)的解的個數(shù)最多為 m ．我們只需要在模 m 的一組完全剩余系中來確定同余方程 (1)的解．,例 1 用直接驗算法解同余方程：　　(1) 11x≡5 (mod6) ； (2) x3 + 2x－12≡0 (mod7)．,0, 1, …, 5逐一代入(

18、1) 得解 x≡1 (mod6),0, 1, …, 6逐一代入(2) 求解,定義: 如果 a , b 都是整數(shù)， m 是一個正整數(shù)，那么當 a ≡ 0 ( mod m）時，我們把 ax ≡ b ( mod m ) 叫做模m的一次同余方程（或同余式） .,,定理 3.1.1 若設(shè)m為正整數(shù), a , b為整數(shù), (a，m)=1，則一次同余方程ax ≡ b ( mod m )恰有一個解 .,一、歐拉定理法解一次同余方程,定理 3.1.2

19、 若 m 為正整數(shù), a , b為整數(shù), (a，m)=1，則一次同余方程ax ≡ b ( mod m )的唯一解為,一次同余方程有解的判定,定理3.1.3 設(shè)m為正整數(shù)， a, b是整數(shù)， (a, m)=d，則同余方程 ax≡b (mod m) 有解的充分必要條件為 d | b.,定理3. 1. 4 設(shè)m為正整數(shù), a為整數(shù), (a, m)=d，,d | b，則同余方程 ax ≡ b (mod m) 恰有 d 個解．,一次同余方

20、程有解的解法,根據(jù)同余性質(zhì)，施行適當?shù)淖冃吻蠼鈇≡b(modm):變形(1)：加上或減去模的倍數(shù)，推廣的加減變形， 即 a≡b+mk (mod m);變形(2)：移項變形， 由 a≡b+c(mod m) 可得 a－c≡b(mod m);變形(3)：約去同余式兩端的公約數(shù)，約簡變形， 由ac≡bc(mod m)，(c, m)＝d，可得 a≡b(mod 　); 特例：(

21、c, m)＝1, 由ac≡bc(mod m) 得 a≡b(mod m)．變形(4)：同余式兩端同時乘以與模m互質(zhì)的因數(shù)c，即“倍乘變形”：ac≡bc(mod m)．,二．同余變形法（系數(shù)消去法）,例 求解同余方程：9x ≡ 6 (mod 15)．,原同余方程的3個解為:,解: (9, 15)=3，且3 | 6，可判斷方程恰有3個解。 先求解3x≡2 (mod 5), 3x≡2+10 (m

22、od 5), x≡4 (mod 5),,x ≡ 4 (mod 15), x ≡ 9 (mod 15),x ≡ 14 (mod 15)．,或解: 3x≡－3 (mod 5), 　x≡－1 ≡ 4 (mod 5),,3．組合數(shù)法,定理 3. 1. 5 若p為質(zhì)數(shù),且0 < a < p, 則,為同余方程ax≡ b (mod p) 的唯一解.,例3 解下列同余方程：7x≡8(mo

23、d 11);,解: 由11是質(zhì)數(shù), 且7<11, 因而 由公式得,同余方程組,本節(jié)討論一次同余方程組（解的存在性、求解方法與公式），因 ax+b≡0 或 ax≡b (mod m) 可以通過求解轉(zhuǎn)化為x≡c (mod m) , 故我們只討論,其中求解問題。,⑴,定理§3.2.2 (孫子定理或中國剩余定理) :,這里Mi′是同余式 MiMi ′≡1 (mod mi ) 的解, i = 1 ,2 , …, n.,x

24、 ≡ M1 M1′ b1 + M2 M2′ b2 + …+ MnMn′bn (mod m) (2),,恰有一整數(shù)解:,若n≥2 , m1 , m2 , …, mn 是兩兩互質(zhì)的n個正整數(shù)，令 m= m1 m2 …mn = m1 M1 = m2 M2 =…= mnMn ，則同余方程組,例 韓信點兵．,有兵一隊，若列成五行縱隊，則末行一人，成六行縱隊，則末行五人．成七行縱隊，則末行四人，成十一行縱隊，則末行十人，求兵數(shù).,解　設(shè)

25、x 是所求兵數(shù)，則依題意，得,此同余方程組模兩兩互質(zhì)，顯然有解，且可運用孫子定理求解，過程也比較簡捷 。,它們兩兩互素，b1 =1, b2 =5, b3 =4, b4 =10. 因此有 M = 5×6×7×11= 2310, M1 = M /m1 = 462, M2 = M /m2 = 385, M3 = M /m3 = 330,

26、 M4 = M /m4 = 210.,這里 m1=5 , m2=6, m3=7, m1=11,,解下列同余式,得,即 x = 2111+2310 t ( t = 0, 1, 2, … ).,第四章 不定方程,不定方程是指未知數(shù)個數(shù)多于方程的個數(shù)，且未知數(shù)受到某種條件限制（例如要求整數(shù)解，非負整數(shù)解等）的方程。,整系數(shù)方程 ax + by＝c 叫做二元一次不定方程，這里a，b，c

27、都是整數(shù)，且ab≠0．,二元一次不定方程,定理4.1.1,二元一次不定方程 ax + by＝c 有解的充分必要條件是d | c , 這里d=(a，b) ．,定理3.1.3 設(shè)m為正整數(shù)， a, b是整數(shù)， 同余方程 ax≡b (mod m) 有解的充分必要條件為 d | b，這里 d = (a, m) .,二元一次不定方程有解的判定,例 判斷下列方程有無整數(shù)解．,(1) 12x－11y＝7； (2) 2x+6y－8=0；,解

28、,(1) 因為(12，11)＝1，所以原方程有整數(shù)解；,(2) 由原方程得2x+6y＝8，由于(2,6)＝2，2 | 8,所以原方程有整數(shù)解；,例1 求不定方程 22x+30y=14的一個解．,11x≡ 7 (mod 15) ，,所以，原方程的一個解是 x ＝ 2，y ＝ － 1．,解：方法一 先解等價的同余方程∵ (22, 30)=2, 2 | 14, 不定方程有解, 化為 11x+15y = 7 后與原方程同解,

29、 先解等價的同余方程：,將 x ＝ 2 代入 11x+15y = 7 ，得 y ＝ － 1，,11x≡ 7+15 (mod 15) ， x≡ 2 (mod 15).,二元一次不定方程特解的求法,方法一 轉(zhuǎn)化為等價的同余方程,方法二 輾轉(zhuǎn)相除法,定理4.1.1的充分性證明是構(gòu)造性證明，給出了求方程 ax + by＝c 的一個特解的方法：輾轉(zhuǎn)相除法.若方程有解，則可化為 a’x + b’y＝ c’, (a’, b’) =

30、1，必存在整數(shù)M，N，使 a’M + b’N ＝1 (☆ ）　　　這里的M、N經(jīng)輾轉(zhuǎn)相除法求出;　然后在(☆)式兩邊同時乘以c’，得 a’c’M + b’c’N ＝ c’.,因此不定方程ax + by＝c的一個整數(shù)解就是x0＝c’M， y0＝c’N．,例 解不定方程 22x+30y=14.,15=11×1＋4, 11=4×2+3, 　4=3×1+1. 回代：1 = 4－3×1= 4－

31、(11－4×2)×1 　 =4×3－11=(15－11×1) ×3－11 　 = 15 ×3+11×(－4)，,得原方程的一個解： x0＝－4×7＝－28，y0 ＝3×7＝21．,∴　 7 = 11×(－4×7) +15 ×(3×7).,解: ∵ (22, 30)=

32、2, 2 | 14, 不定方程有解, 化為 11x+15y=7, 先解11x+15y=1,輾轉(zhuǎn)相除:,方法三 整數(shù)分離法,解 因為(21，57)＝3，3｜639，所以原不定方程有整數(shù)解．在方程兩邊同時除以3，得　7x+19y＝213.,用輾轉(zhuǎn)相除法求方程(1)的一個整數(shù)解的方法不夠簡便；對于某些二元一次不定方程來說，運用整數(shù)分離法求解比較簡捷．,例 3 判斷不定方程21x+57y＝639是否有整數(shù)解，如果有，請求出它的一

33、個整數(shù)解．,注意到x為整數(shù), 通過觀察與估算知 y = 2 時上面的分式為－1, x有整數(shù)解, 由此得,為方程的解.,若不能觀察到以上結(jié)果,可設(shè),用較小的系數(shù)7去除上式, 于是有：,繼續(xù)用上面的方法, 用較小的系數(shù)5去除上式, 得,可觀察到u=－1時y有整數(shù)解.,從而仍然能得出上述的一組解.,不定方程的通解,定理4.1.2 如果(a, b)=1, 且x＝ x0，y＝ y0是不定方程ax + by＝c（1）的一個解，那么它的一切解都

34、可表示為,這里 t 為任意整數(shù)。,通解公式的特點：,公式(2)稱為二元一次不定方程(1)的通解公式.其特點是: (1) 公式中 x，y 的表達式的第一項 x0 ，y0 是方程 (1) 的一個解 (稱為特解)； (2) 公式中 x，y 的表達式的第二項為任意整數(shù) t 乘以不定方程 (1) 的系數(shù)或系數(shù)的相反數(shù)．且只要符號保持相反就可以．,定理4.1.2告訴我們什么?,(t為任意整數(shù)).,對于二元一次不定方程(1)，只須

35、用適當方法(觀察法，同余法，輾轉(zhuǎn)相除法或整數(shù)分離法) 找到它的一組整數(shù)解x= x0，y=y0,那么就可以找到方程(1)的一切整數(shù)解(通解),不定方程的非負整數(shù)解(或正整數(shù)解)的求法,實際應(yīng)用中常常求不定方程的非負整數(shù)解(或正整數(shù)解) 顯然，在二元一次不定方程通解公式(2)中通過對 t 的取值范圍作適當?shù)南拗疲锤鶕?jù)題目要求，令 x≥0 且 y≥0，或 x＞0且y＞0 列出由通解公式所組成的不等式組. 如果上面關(guān)于t的不等式組有