[數論] 一次同餘式 (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$，則一次同餘式 $ax\equiv b\; \mathrm{(mod\; m)}$ (英文唸作"$ax$ is congruent to $b$ modulo $m$")有解的充分必要條件是 $d\mid b$。

定理二 若 $(a,m)=d$，$d\mid b$，則同餘式 $ax\equiv b\; \mathrm{(mod\; m)}$ 恰有 $d$ 個解。

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


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

1. 逐項代入法
<例1> 求解 $5x\equiv 7\; \mathrm{(mod\; 8)}$
<解1-1> 先判別此同餘式是否有解。
因為 $(5,8)=1$，所以此同餘式有唯一解。模 $8$ 的完全剩餘系是 $\left \{ 0,1,2,3,4,5,6,7 \right \}=\left \{ 0,5,10,15,20,25,30,35 \right \}$。檢視這八個數，發現 $15$ 符合我們同餘式的條件，故 $15=5\times 3\equiv 7\; \mathrm{(mod\; 8)}$， 得到解 $x\equiv 3\; \mathrm{(mod\; )}$。

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

2. 公式法
當 $(a,m)=1$，則一次同餘式 $ax\equiv b\; \mathrm{(mod\; m)}$ 的解為 $$x\equiv b\cdot a^{\varphi (m)-1}\; \; \mathrm{(mod\; m)}$$上述公式只有在 $(a,m)=1$ 時才能使用。證明的關鍵是使用 Euler's Theorem。

<例1> 求解 $5x\equiv 7\; \mathrm{(mod\; 8)}$
<解1-2> 因為 $(5,8)=1$，所以有唯一解。套用公式得到 $x\equiv 7\cdot 5^{\varphi (8)-1}\equiv 7\cdot 5^{4-1}\equiv 7\cdot 5^3\; \mathrm{(mod\; 8)}$，得到解 $x\equiv 3\; \mathrm{(mod\; 8)}$。

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

<例2> 求解 $8x\equiv 10\; \mathrm{(mod\; 22)}$
<解2> 因為 $(8,22)=2$，且 $2\mid 10$，所以此同餘式有兩個解，但無法套用上述求解公式。
將同餘式全部同除以 $2$，得到 $4x\equiv 5$ (mod $11$)，因為 $(4,11)=1$，套用求解公式，得到 $x\equiv 4\; \mathrm{(mod\; 11)}$。注意答案不可以直接寫 $x\equiv 4\; \mathrm{(mod\; 11)}$。我們必須先將簡化後的同餘式的解寫成 $x=4+11t\; \mathrm{(mod\; 22)}$，將 $t=0,1$ 代入。最後得到兩個解 $x\equiv 4\; \mathrm{(mod\; 22)}$ 及 $x\equiv 15\; \mathrm{(mod\; 22)}$。

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


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

對於一次同餘方程組 \[ \left\{\begin{matrix}
a_1x\equiv b_1\; \mathrm{(mod\; m_1)}
\\ a_2x\equiv b_2\; \mathrm{(mod\; m_2)}
\\...
\\ a_nx\equiv b_n\; \mathrm{(mod\; m_n)}

\end{matrix}\right. \]
解題思路是，先判斷方程組是否有解；如果有解，則解的個數為何？最後才實際去求解。

1. 解的存在性
如果對每條同餘方程式 $a_i\equiv b_i$ (mod $m_i$)，$i=1,2,...,n$，都符合 $(a_i,m_i)\mid b_i$ 的條件（定理一），則此同餘方程組有解。

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

3. 實際求解（附上例題說明）
<例3>
\[ \left\{\begin{matrix}
2x\equiv 2\; \mathrm{(mod\; 6)}
\\ 3x\equiv 2\; \mathrm{(mod\; 7)}
\\ 2x\equiv 4\; \mathrm{(mod\; 8)}
\end{matrix}\right. \]
我們先檢查此方程組是否有解。因為 $(2,6)=2\mid 2$、$(3,7)=1\mid 2$、$(2,8)=2\mid 4$，所以此方程組有解。

<解3>
先從第一條式子看起。$2x\equiv 2\; \mathrm{(mod\; 6)}$ 兩邊同除以 $2$，得到 $x\equiv 1\; \mathrm{(mod\; 3)}$，因此 $x=3a+1$，其中 $a$ 是整數。

將 $x=3a+1$ 代到第二條同餘式。$3x=3(3a+1)=9a+3\equiv 2a+3 \equiv 2\; \mathrm{(mod\; 7)}$，整理得到 $2a\equiv 6\; \mathrm{(mod\; 7)}$，即 $a\equiv 3\; \mathrm{(mod\; 7)}$，因此 $a=7b+3$，$b$ 是整數。將 $a=7b+3$ 代回 $x=3a+1$，得到 $x=3(7b+3)+1=21b+10$。

我們先將第三條同餘式同除以 $2$，得到 $x\equiv 2\; \mathrm{(mod\; 4)}$。將 $x=21b+10$ 代入，得到 $21b+10\equiv 2\; \mathrm{(mod\; 4)}$。整理後得到 $b\equiv 0\; \mathrm{(mod\; 4)}$，即 $b=4c$，其中 $c$ 是整數。將 $b=4c$ 代回 $x=21b+10$，得到 $x=21(4c)+10=84c+10$，或是寫為 $x\equiv 10\; \mathrm{(mod\; 84)}$，此即同餘方程組的解。

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


四、中國剩餘定理（Chinese Remainder Theorem, CRT）
若一次同餘方程組有如下形式 \[ \left\{\begin{matrix}
x\equiv b_1\; \mathrm{(mod\; m_1)}
\\ x\equiv b_2\; \mathrm{(mod\; m_2)}
\\...
\\ x\equiv b_n\; \mathrm{(mod\; m_n)}
\end{matrix}\right. \]
其中 $(m_i,m_j)=1$，$1\leq i<j\leq n$，即 $m_1,m_2,..., m_n$ 兩兩互質，則此同餘式必有唯一解模 $m_1m_2\cdots m_n$。

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