初等數(shù)論2

1、主要內(nèi)容　　同余的定義、性質(zhì)、剩余類和完全剩余系、歐拉函數(shù)、簡化剩余系、歐拉定理、費(fèi)爾馬小定理,第二章 同余,2024年3月18日7時33分,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 同余, 記作

2、 a ≡b (mod m). （1） 讀作a 同余于b 模m。,一、同余的概念及基本性質(zhì),2024年3月18日7時33分,2、同余的性質(zhì)：,(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分,我喜歡數(shù)學(xué),E,性質(zhì)(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 為任意整數(shù).同余式的數(shù)乘。,,推廣,2024年3月18日7時33分,,性質(zhì)(6),性質(zhì)(7),若a =a1d, b =b1d, (m, d) =1, a ≡b (mod m)，則 a1 ≡ b1 (mod

5、 m) .,性質(zhì)(8),d為a，b及m的任一正公約數(shù)，則,若a ≡b (mod m)，k 為正整數(shù) ， 則 ka ≡ kb (mod km) .,2024年3月18日7時33分,性質(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) ，

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

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

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

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

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

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

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

13、 ii ) 各數(shù)關(guān)于模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), 整數(shù)集合{ a1, a2,

14、 …, ak }與 { b1, b2，…, bh }分別是模 m1, m2 的簡化剩余系，則整數(shù)集合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 的標(biāo)準(zhǔn)分解式是,則,歐拉函數(shù)的計(jì)算公式,推論 若 則,2024年3月18日7時33分,歐拉函數(shù)? (m) 的計(jì)算,將,代入定理１中的公式，就有,特別地，對于質(zhì)數(shù) p，有,四　歐拉定理,定理 2.3.1 ( 歐拉定理) 若為大于1的整數(shù)， a為整數(shù)且( a ，m) = 1, 則,2024年3月18日7時33分,定理 2.3.2 （費(fèi)馬小定理）,若 p 為素?cái)?shù)， a為任意整數(shù)，則

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

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

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

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

20、程ax ≡ b ( mod m )恰有一個解 .,一、歐拉定理法解一次同余方程,定理 3.1.2 若 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,

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

22、形， 由ac≡bc(mod m)，(c, m)＝d，可得 a≡b(mod 　); 特例：(c, m)＝1, 由ac≡bc(mod m) 得 a≡b(mod m)．變形(4)：同余式兩端同時乘以與模m互質(zhì)的因數(shù)c，即“倍乘變形”：ac≡bc(mod m)．,二．同余變形法（系數(shù)消去法）,同余方程組,本節(jié)討論一次同余方程組（解的存在性、求解方法與公式），因 ax+b≡0 或 ax≡b (mod m) 可以通過求解轉(zhuǎn)化為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),,恰有一整數(shù)解:,若n≥2 , m1 , m2 , …, mn 是兩兩互質(zhì)的n個正整數(shù)，令 m= m1 m2 …