張文忠,基礎數論:原理及題解,中央圖書,2002年出版,ISBN:978-957-637-493
Strayer, J.K. (1994). Elementary Number Theory. Boston: PWS Publishing Company.
Math 115, Summer 2012. James McIvor. Schedule of Lectures
https://math.berkeley.edu/~mcivor/math115su12/lectures/lecture4.pdf
一、一次同餘方程式解的存在性&解的個數
定理一 若 (a,m)=d,則一次同餘式 ax≡b(modm) (英文唸作"ax is congruent to b modulo m")有解的充分必要條件是 d∣b。
定理二 若 (a,m)=d,d∣b,則同餘式 ax≡b(modm) 恰有 d 個解。
定理一給了我們判別解是否存在的方法;定理二則是說明解的個數。
二、一次同餘方程式求解方法
下面介紹三種常見的求解方法。
1. 逐項代入法
2. 公式法
3. 二元一次不定方程法
1. 逐項代入法
<例1> 求解 5x≡7(mod8)
<解1-1> 先判別此同餘式是否有解。
因為 (5,8)=1,所以此同餘式有唯一解。模 8 的完全剩餘系是 {0,1,2,3,4,5,6,7}={0,5,10,15,20,25,30,35}。檢視這八個數,發現 15 符合我們同餘式的條件,故 15=5×3≡7(mod8), 得到解 x≡3(mod)。
逐項代入法是一種很直觀的作法。既然模 8 的結果只有八種,我們就把這八種結果一一檢視。當模數小的時候,逐項代入法不失為一種好方法,但是當模數很大,逐項代入顯然缺乏效率。
2. 公式法
當 (a,m)=1,則一次同餘式 ax≡b(modm) 的解為 x≡b⋅aφ(m)−1(modm)
上述公式只有在 (a,m)=1 時才能使用。證明的關鍵是使用 Euler's Theorem。
<例1> 求解 5x≡7(mod8)
<解1-2> 因為 (5,8)=1,所以有唯一解。套用公式得到 x≡7⋅5φ(8)−1≡7⋅54−1≡7⋅53(mod8),得到解 x≡3(mod8)。
有些同餘式無法直接套用公式。此時須先將原同餘式稍作修改,使其符合 (a,m)=1,再套用公式。
<例2> 求解 8x≡10(mod22)
<解2> 因為 (8,22)=2,且 2∣10,所以此同餘式有兩個解,但無法套用上述求解公式。
將同餘式全部同除以 2,得到 4x≡5 (mod 11),因為 (4,11)=1,套用求解公式,得到 x≡4(mod11)。注意答案不可以直接寫 x≡4(mod11)。我們必須先將簡化後的同餘式的解寫成 x=4+11t(mod22),將 t=0,1 代入。最後得到兩個解 x≡4(mod22) 及 x≡15(mod22)。
3. 二元一次不定方程法
將同餘式轉換成二元一次不定方程,利用不定方程的解法求出原本同餘式的解。
<例1> 求解 5x≡7(mod8)
<解1-3> 原同餘式等價於 5x+8y=7,其中 y 是整數。得到解 (x,y)=(3,1),即 x≡3(mod8)。
三、一次同餘方程組
先前介紹的都是一次同餘式。當我們面對到一次同餘方程組,即多條同餘式聯立求解,該如何解題呢?
對於一次同餘方程組 {a1x≡b1(modm1)a2x≡b2(modm2)...anx≡bn(modmn)
解題思路是,先判斷方程組是否有解;如果有解,則解的個數為何?最後才實際去求解。
1. 解的存在性
如果對每條同餘方程式 ai≡bi (mod mi),i=1,2,...,n,都符合 (ai,mi)∣bi 的條件(定理一),則此同餘方程組有解。
2. 解的個數
若同餘方程組有解,因為每一組 (ai,mi) 不盡相同,因此無法直接使用定理二判斷解的個數。
3. 實際求解(附上例題說明)
<例3>
{2x≡2(mod6)3x≡2(mod7)2x≡4(mod8)
我們先檢查此方程組是否有解。因為 (2,6)=2∣2、(3,7)=1∣2、(2,8)=2∣4,所以此方程組有解。
<解3>
先從第一條式子看起。2x≡2(mod6) 兩邊同除以 2,得到 x≡1(mod3),因此 x=3a+1,其中 a 是整數。
將 x=3a+1 代到第二條同餘式。3x=3(3a+1)=9a+3≡2a+3≡2(mod7),整理得到 2a≡6(mod7),即 a≡3(mod7),因此 a=7b+3,b 是整數。將 a=7b+3 代回 x=3a+1,得到 x=3(7b+3)+1=21b+10。
我們先將第三條同餘式同除以 2,得到 x≡2(mod4)。將 x=21b+10 代入,得到 21b+10≡2(mod4)。整理後得到 b≡0(mod4),即 b=4c,其中 c 是整數。將 b=4c 代回 x=21b+10,得到 x=21(4c)+10=84c+10,或是寫為 x≡10(mod84),此即同餘方程組的解。
解3的作法是一種通用的解法。當同餘組內的式子越多,所需的求解步驟也隨之增加。我們希望能找出一種「公式」,或是能夠簡化問題的方法。
四、中國剩餘定理(Chinese Remainder Theorem, CRT)
若一次同餘方程組有如下形式 {x≡b1(modm1)x≡b2(modm2)...x≡bn(modmn)
其中 (mi,mj)=1,1≤i<j≤n,即 m1,m2,...,mn 兩兩互質,則此同餘式必有唯一解模 m1m2⋯mn。
<例1> 參考下面影片說明
五、一些同餘運算性質補充
In the following, a, b, c, d are arbitrary integers, m a positive integer.
(1) (Symmetry) If a ≡ b mod m, then b ≡ a mod m.
(2) (Transitivity) If a ≡ b mod m and b ≡ c mod m, then a ≡ c mod m.
(3) (Reflexivity) a ≡ a mod m.
(4) (Subtraction Rule) If a ≡ b mod m, then a − b ≡ 0 mod m.
(5) (Addition Rule) If a ≡ b mod m and c ≡ d mod m, then a + c ≡ b + d mod m.
(6) (Multiplication Rule) If a ≡ b mod m and c ≡ d mod m, then ac ≡ bd mod m.
(7) (Reduction of Modulus Rule) If a ≡ b mod m and d|m, d > 1, then a ≡ b mod d.
(8) (Scalar Multiplication Rule) If a ≡ b mod m and c > 0, then ac ≡ bc mod mc.
(9) (Polynomial Substitution Rule) If a ≡ b mod m and f(x) is a polynomial with integer coefficients, then f(a) ≡ f(b) mod m
沒有留言:
張貼留言