初等數論2

1、主要內容　　同余的定義、性質、剩余類和完全剩余系、歐拉函數、簡化剩余系、歐拉定理、費爾馬小定理,第二章 同余,2024年3月18日7時33分,1、同余的概念:,定義2. 1,若a 和b 除以m 所得余數不同，則稱a，b 對模m 不同余，記作 a b (mod m).,設m為正整數，稱為模。若用m去除兩個整數 a 和 b 所得的余數相同，則稱a 和b 對模 m 同余, 記作

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

3、 b ≡ c (mod m), 則 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月18日7時33分,我喜歡數學,E,性質(5) 若a ≡b (mo

4、d m)，c ≡d (mod m) ， 則 ac ≡ bd (mod m) .同余式可以相乘。推論　若a ≡b (mod m)， 則 a k ≡ b k (mod m), k 為任意整數.同余式的數乘。,,推廣,2024年3月18日7時33分,,性質(6),性質(7),若a =a1d, b =b1d, (m, d) =1, a ≡b (mod m)，則 a1 ≡ b1 (mod

5、 m) .,性質(8),d為a，b及m的任一正公約數，則,若a ≡b (mod m)，k 為正整數 ， 則 ka ≡ kb (mod km) .,2024年3月18日7時33分,性質(9),若 a ≡b (mod m1), a ≡b (mod m2), m=[ m1, m2 ], 則 a ≡ b (mod m) .,性質(10) 設d ≥1， d | m，若a ≡b (mod m) ，

6、 則 a ≡ b (mod d ) .,E,New,若a ≡b (mod m)，則 (a，m) = (b，m).,性質(11),2024年3月18日7時33分,棄九法,正整數四則運算(含乘方) 的快速驗算方法,例7 用棄九法驗算 28947×34578 =1001865676 是否正確.,棄九法只是運算結果正確的必要條件，而非充分條件 ! 因此只能判誤.,解,若通過計算，a、b的和與積分別是s與p. 而r1

7、、r2、r3、r4 分別是a、b、s、p被 9 除所得的余數, 由同余的加減乘性質可知，如果r1 +r2與r3、 r1 · r2與r4關于模 9 不同余，那么計算一定錯了.,2024年3月18日7時33分,二、剩余類與剩余系,定理2.2.1 設m為正整數，則全部整數可分成m個集合,記作[0]，[1]，…，[m－1]，其中[r] (0 ≤ r ≤m－1)是由一切形如 mq + r (q∈Z) 的整數所組成的，并且具有下列性質：

8、(1)每一整數必包含在而且僅在上述的一個集合中.(2)兩個整數同在一個集合中的充分必要條件為這兩個整數對模 m 同余。,2024年3月18日7時33分,定義2. 2 設m為正整數，則全部整數分成的 m個集合[0]，[1]，…，[m－1]稱為模m的剩余類,一個剩余類中任一數叫做它的同類的數的剩余。,2024年3月18日7時33分,定理2.2.2　設m為正整數，則 （1）在任意取定的 m + 1 個整數中，必有兩個數對模 m

9、同余。 （2）存在 m 個數兩兩對模m不同余。,完全剩余系,定義2. 3 設 m 為正整數，則從模 m 的每個剩余類中各取一個數所作成的集合，稱為模 m 的一個完全剩余系.,2024年3月18日7時33分,定理2.2.4 若 a1, a2，…, am 是模m的完全剩余系，,且(a, m) =1, b 為任意整數，則 aa1 +b, aa2 +b, …, aam +b 也是模 m 的一個完全剩余系。,定理2.2.3　設m 為

10、正整數，整數集合{ a1, a2 , … , am}是模 m 的完全剩余系的充分必要條件是：ai aj (mod m) ( i≠ j ).,,下面例1給出模m的另外完全剩余系——絕對最小完,全剩余系.,2024年3月18日7時33分,例2 驗證：{－11, －4, 18, 20, 32 }是模 5 的一個完全剩余系。,證：只要證兩兩不同余即可, 也就是它們各屬于不同的剩余類. 從而只要證明它們各與最小非負完全剩余系中

11、的某一個數同余即可.,－11與4, －4與1, 18與3, 20與0, 32與2分別對模5同余，所以結論成立。,2024年3月18日7時33分,定義 2.4,E,時，,m為質數當且僅當,設 m 是正整數，用? (m)表示不大于 m 且與 m 互質的自然數的個數．稱 ? (m)為歐拉函數．,三、 歐拉函數和簡化剩余系,2024年3月18日7時33分,定義 2.5,定理2.2.6　設 m 是正整數，則模m的一個剩余類是與模 m互質的剩余類的

12、充分必要條件為：這個模m的剩余類中有一數與m互質。,設 m 是正整數，若一個模m的剩余類中的數與m互質，則稱這個模m的剩余類為與模m互質的剩余類。在與模 m互質的所有剩余類中，從每一類各取一數所作成的集合叫做模 m 的一個簡化剩余系.,2024年3月18日7時33分,簡化剩余系的充要條件,定理2.2 7 整數集合　　　　　　　為模m的簡化剩余系的充要條件是： ( i ) (ai, m) =1 ( 1≤i ≤? (m) ); (

13、 ii ) 各數關于模m兩兩不同余．,2024年3月18日7時33分,定理 2.2.8 若( a，m ) = 1 , x 通過模 m 的簡化剩余系，則 ax 也通過模 m 的簡化剩余系。,即{x1, x2, … xk}是模m的一個簡化剩余系，則{ax1, ax2, …, axk}也是模m的簡化剩余系。這里k = ? (m)。,若 (m1, m2) =1, k =? (m1), h =? (m2), 整數集合{ a1, a2,

14、 …, ak }與 { b1, b2，…, bh }分別是模 m1, m2 的簡化剩余系，則整數集合A = { m2a1 + m1b1, m2a1 +m1b2, 　…, m2a1 +m1bh, m2a2 + m1b1, m2a2 + m1b2, … , m2a2 + m1bh, …, m2ak + m1bh }是模 m1m2 的一個簡化剩余系。,定理2.2.9,2024年3月18日7時33分,定理 2.2.10,E,容斥原理的證

15、法,若 m 的標準分解式是,則,歐拉函數的計算公式,推論 若 則,2024年3月18日7時33分,歐拉函數? (m) 的計算,將,代入定理１中的公式，就有,特別地，對于質數 p，有,四　歐拉定理,定理 2.3.1 ( 歐拉定理) 若為大于1的整數， a為整數且( a ，m) = 1, 則,2024年3月18日7時33分,定理 2.3.2 （費馬小定理）,若 p 為素數， a為任意整數，則

16、 ap ≡ a ( mod p) .,當 (a , p) = 1時，費馬小定理是歐拉定理的特殊情況。此定理由費馬提出，后來由歐拉證明。,根據歐拉定理，當 (a，m) = 1時，總可以找到自然數 x =? (m) ，使ax≡1 (mod m). 但是, ? (m)并不是使 ax ≡1（mod m ）成立的自然數 x 中的最小數.,定理 2.3.3 若 m 為大于1的整數，a 為整數且(a，m)

17、 = 1 ，若自然數 h 為滿足 ax≡1 (mod m) 的所有自然數中最小的，則 h | x .,主要內容 同余方程概念及次數、解的定義，一次同余方程ax≡b(mod m)有解的充分必要條件，一次同余方程組，孫子定理。,第三章 同余方程,一次同余方程,定義 3. 1,例如同余方程　x5 + 2x－12≡0 (mod7)．,定義3.2 如果整數 a 滿足 f (a)≡0 (mod m) , 那么我們把 x ≡ a ( m

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

19、 (2) x5 + 2x－12≡0 (mod7)．,0, 1, …, 5逐一代入(1) 得解 x≡1 (mod6),0, 1, …, 6逐一代入(2) 求解,定義: 如果 a , b 都是整數， m 是一個正整數，那么當 a ≡ 0 ( mod m）時，我們把 ax ≡ b ( mod m ) 叫做模m的一次同余方程（或同余式） .,,定理 3.1.1 若設m為正整數, a , b為整數, (a，m)=1，則一次同余方

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

21、m)=d，,d | b，則同余方程 ax ≡ b (mod m) 恰有 d 個解．,一次同余方程有解的解法,根據同余性質，施行適當的變形求解a≡b(modm):變形(1)：加上或減去模的倍數，推廣的加減變形， 即 a≡b+mk (mod m);變形(2)：移項變形， 由 a≡b+c(mod m) 可得 a－c≡b(mod m);變形(3)：約去同余式兩端的公約數，約簡變

22、形， 由ac≡bc(mod m)，(c, m)＝d，可得 a≡b(mod 　); 特例：(c, m)＝1, 由ac≡bc(mod m) 得 a≡b(mod m)．變形(4)：同余式兩端同時乘以與模m互質的因數c，即“倍乘變形”：ac≡bc(mod m)．,二．同余變形法（系數消去法）,同余方程組,本節(jié)討論一次同余方程組（解的存在性、求解方法與公式），因 ax+b≡0 或 ax≡b (mod m) 可以通過求解轉化為x≡c (

23、mod m) , 故我們只討論,其中求解問題。,⑴,定理§3.2.2 (孫子定理或中國剩余定理) :,這里Mi′是同余式 MiMi ′≡1 (mod mi ) 的解, i = 1 ,2 , …, n.,x ≡ M1 M1′ b1 + M2 M2′ b2 + …+ MnMn′bn (mod m) (2),,恰有一整數解:,若n≥2 , m1 , m2 , …, mn 是兩兩互質的n個正整數，令 m= m1 m2 …