2015年1月7日 星期三

[數論] 一次同餘式 (Congruence of the First Degree)

零、參考資料
張文忠,基礎數論:原理及題解,中央圖書,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,則一次同餘式 axb(modm) (英文唸作"ax is congruent to b modulo m")有解的充分必要條件是 db

定理二 (a,m)=ddb,則同餘式 axb(modm) 恰有 d 個解。

定理一給了我們判別解是否存在的方法;定理二則是說明解的個數。


二、一次同餘方程式求解方法
下面介紹三種常見的求解方法。
1. 逐項代入法
2. 公式法
3. 二元一次不定方程法

1. 逐項代入法
<例1> 求解 5x7(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×37(mod8), 得到解 x3(mod)

逐項代入法是一種很直觀的作法。既然模 8 的結果只有八種,我們就把這八種結果一一檢視。當模數小的時候,逐項代入法不失為一種好方法,但是當模數很大,逐項代入顯然缺乏效率。

2. 公式法
當 (a,m)=1則一次同餘式 axb(modm) 的解為 xbaφ(m)1(modm)
上述公式只有在 (a,m)=1 時才能使用。證明的關鍵是使用 Euler's Theorem。

<例1> 求解 5x7(mod8)
<解1-2> 因為 (5,8)=1,所以有唯一解。套用公式得到 x75φ(8)17541753(mod8),得到解 x3(mod8)

有些同餘式無法直接套用公式。此時須先將原同餘式稍作修改,使其符合 (a,m)=1,再套用公式。

<例2> 求解 8x10(mod22)
<解2> 因為 (8,22)=2,且 210,所以此同餘式有兩個解,但無法套用上述求解公式。
將同餘式全部同除以 2,得到 4x5 (mod 11),因為 (4,11)=1,套用求解公式,得到 x4(mod11)。注意答案不可以直接寫 x4(mod11)。我們必須先將簡化後的同餘式的解寫成 x=4+11t(mod22),將 t=0,1 代入。最後得到兩個解 x4(mod22)x15(mod22)

3. 二元一次不定方程法
將同餘式轉換成二元一次不定方程,利用不定方程的解法求出原本同餘式的解。
<例1> 求解 5x7(mod8)
<解1-3> 原同餘式等價於 5x+8y=7,其中 y 是整數。得到解 (x,y)=(3,1),即 x3(mod8)


三、一次同餘方程組
先前介紹的都是一次同餘式。當我們面對到一次同餘方程組,即多條同餘式聯立求解,該如何解題呢?

對於一次同餘方程組 {a1xb1(modm1)a2xb2(modm2)...anxbn(modmn)

解題思路是,先判斷方程組是否有解;如果有解,則解的個數為何?最後才實際去求解。

1. 解的存在性
如果對每條同餘方程式 aibi (mod mi),i=1,2,...,n,都符合 (ai,mi)bi 的條件(定理一),則此同餘方程組有解。

2. 解的個數
若同餘方程組有解,因為每一組 (ai,mi) 不盡相同,因此無法直接使用定理二判斷解的個數。

3. 實際求解(附上例題說明)
<例3>
{2x2(mod6)3x2(mod7)2x4(mod8)

我們先檢查此方程組是否有解。因為 (2,6)=22(3,7)=12(2,8)=24,所以此方程組有解。

<解3>
先從第一條式子看起。2x2(mod6) 兩邊同除以 2,得到 x1(mod3),因此 x=3a+1,其中 a 是整數。

x=3a+1 代到第二條同餘式。3x=3(3a+1)=9a+32a+32(mod7),整理得到 2a6(mod7),即 a3(mod7),因此 a=7b+3b 是整數。將 a=7b+3 代回 x=3a+1,得到 x=3(7b+3)+1=21b+10

我們先將第三條同餘式同除以 2,得到 x2(mod4)。將 x=21b+10 代入,得到 21b+102(mod4)。整理後得到 b0(mod4),即 b=4c,其中 c 是整數。將 b=4c 代回 x=21b+10,得到 x=21(4c)+10=84c+10,或是寫為 x10(mod84),此即同餘方程組的解。

解3的作法是一種通用的解法。當同餘組內的式子越多,所需的求解步驟也隨之增加。我們希望能找出一種「公式」,或是能夠簡化問題的方法。


四、中國剩餘定理(Chinese Remainder Theorem, CRT)
若一次同餘方程組有如下形式 {xb1(modm1)xb2(modm2)...xbn(modmn)

其中 (mi,mj)=11i<jn,即 m1,m2,...,mn 兩兩互質,則此同餘式必有唯一解模 m1m2mn

<例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

沒有留言:

張貼留言