[數論] 關於二次剩餘的整理

可參考下面兩篇
[數論] 二次剩餘 (Quadratic Residues)
http://gotonsb-numbertheory.blogspot.tw/2014/04/quadratic-residues.html

[數論] Legengre symbol 和 二次互反律
http://gotonsb-numbertheory.blogspot.tw/2014/05/legengre-symbol.html

隔了一年回去看以前寫的東西，還蠻亂的。這篇是把上兩篇的內容再整理一次，並搭配題目練習。


首先，一個二次同餘式一般形如 $$a_2x^2+a_1x+a_0\equiv 0\; (\textrm{mod}\; m)$$ 其中 $x^2$ 係數 $a\neq 0$。這是高次同餘式中最簡單的情形(因為最高次是兩次)。對於合數模的高次同餘式，我們可以把合數模化為質數模去計算。在這裡，我們的模數皆為奇質數($p>2$, $p$ is a prime number.)。

透過配方法，$a_2x^2+a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$ 可改寫成 $$z^2\equiv a\; (\textrm{mod}\; p)$$ 上式是二次同餘式的最簡表示式。以下我們主要研究形如 $$x^2\equiv a\; (\textrm{mod}\; m),\; \;  (a,m)=1$$ 的同餘式。

---

二次剩餘
[定義] 設 $m>1$，如果 $x^2\equiv a\; (\textrm{mod}\; m)$ 有解，則稱 $a$ 是模 $m$ 的二次剩餘($a$ is a quadratic residue mod $m$.)；反之，則稱 $a$ 為模 $m$ 的二次非剩餘($a$ is a quadratic nonresidue mod $m$)。

---

定理2
若 $p$ 是一個奇質數(odd prime，除了 2 以外的質數)，則在 ${1,2,…,p−1}$ 中，模 $p$ 的二次剩餘與二次非剩餘的數量會相等，即各 $\frac{p-1}{2}$ 個。為什麼？一是模 $i$ 與模 $(p-i)$ 的結果是一樣的，所以我們僅須代入 $\frac{p-1}{2}$ 次；二是這 $\frac{p-1}{2}$ 個數兩兩對模 $p$ 不同餘，所以二次剩餘即有 $\frac{p-1}{2} 個$ 。

根據定理2，我們可以求出模 $p$ 的二次剩餘；不過我們更感興趣的，是如果給你一個數 $a$，能否判別 $a$ 是不是模 $p$ 的二次剩餘。當然，我們可以根據定理2，將模 $p$ 的完全剩餘系的一半依序代入同餘式，找出全部的二次剩餘，再回頭看 $a$ 是否在其中。但如果 $p$ 很大，我們要代入的次數就會增加。

---

定理3 歐拉判別條件(Euler's Criterion)
(1) $a$ 是模 $p$ 的二次剩餘 $\Leftrightarrow$ $a^{\frac{p-1}{2}}\equiv 1\; (\textrm{mod}\; p)$。
(2) $a$ 是模 $p$ 的二次非剩餘 $\Leftrightarrow$ $a^{\frac{p-1}{2}}\equiv -1\; (\textrm{mod}\; p)$。

定理3給了一個判別 $a$ 是否為模 $p$ 的二次剩餘，亦即判別同餘方程 $x^2\equiv a\; (\textrm{mod}\; p)$ 是否有解。

例2 判別 $x^2\equiv 3\; (\textrm{mod}\; 7)$ 是否有解。
解：因為 $3^{\frac{7-1}{2}}\equiv 3^3\equiv 27\equiv -1\; (\textrm{mod}\; 7)$，根據歐拉判別條件，$3$ 不是模 $7$ 的二次剩餘，故原同餘式無解。

---

定義2 Legendre symbol
若 $a$ 是整數，$p$ 是奇質數，則 $a$ 對模 $p$ 的Legendre symbol(the Legendre symbol of $a$ modulo $p$) $$\left ( \frac{a}{p} \right ) = \left\{\begin{array}{32}                  0, & \mbox{if $n\equiv 0$ (mod $p$)} \\                  1, & \mbox{if $a$ is a quadratic residue modulo $p$} \\                  -1,      & \mbox{otherwise.}                 \end{array} \right.$$ 根據歐拉判別條件，若 $(a,p)=1$，則 $$\left ( \frac{a}{p} \right )\equiv a^{\frac{p-1}{2}}\; (\textrm{mod}\; p)$$

Legendre symbol 計算特性
1. $\left ( \frac{a^2}{p} \right )=1$
2. 若 $a_1\equiv a_2\; (\textrm{mod}\; 9)$，則有 $\left ( \frac{a_1}{p} \right )=\left ( \frac{a_2}{p} \right )$
3. $\left ( \frac{a}{p} \right )$ 是積性函數。

---

定理7 高斯引理(Gauss's lemma)
若 $(a,p)=1$，則 $$\left ( \frac{a}{p} \right )=(-1)^n$$ 其中 $n$ 是 $$a,2a,3a,\cdots ,\frac{p-1}{2}a$$ 對模 $p$ 之最小正剩餘中、大於 $\frac{p}{2}$ 的個數。

例3 試用高斯引理判定同餘式 $x^2\equiv 3\; (\textrm{mod}\; 17)$ 是否有解。
解：$\frac{p-1}{2}=\frac{17-1}{2}=8$，數列 $$3,6,9,12,15,18,21,24$$ 對模 $17$ 的正剩餘分別為 $$3,6,9,12,15,1,4,7$$ 其中大於 $\frac{17}{2}=8.5$ 的數有三個，因此 $$\left ( \frac{3}{17} \right )=(-1)^3=-1$$ 所以原式無解。

與歐拉判別條件類似，當 $p$ 變大時，計算起來也會變複雜。因此需要二次互反律來減輕計算量。

---

定理8 二次互反律(Law of Quadratic Reciprocity)
若 $p,q$ 都是奇質數，$p\neq q$，則 $$\left ( \frac{p}{q} \right )=\left ( \frac{q}{p} \right )(-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$$

---

定義3 Jacobi symbol
計算 Legendre symbol 時，必須先將分母 $a$ 寫成標準分解式才能繼續計算。當 $a$ 變大時，分解的計算量也會變大。關於 Jacobi symbol 的部分，請見維基百科介紹。

[數論] Hensel's lifting lemma

零、參考資料
1. 泰勒展開式 http://math.nsysu.edu.tw/ezfiles/87/1087/img/495/1002.pdf
2. Hensel's Lemma, Reduction of Modulus(Lecture 10)
https://math.berkeley.edu/~mcivor/math115su12/schedule.html
3. Polynominal Congruences
http://www2.latech.edu/~schroder/slides/number_theory/14_polynomial_congruences.pdf

How to get from solutions mod $p$ to solutions mod $p^j$ when $p$ and $j$ is large?

一、Hensel's lifting lemma 精隨
「...it(Hensel's lemma) says that if we have a solution mod $p$, we get a unique solution mod $p^2$ ; if we have a solution mod $p^2$ , we get a solution mod $p^3$ , etc....」

「...如果一個模 $p$ 的同餘方程式有一個根，則可以用這個根去找到該方程式在模 $p^2$ 時的根。...」

例如，當我們要解 $f(x)\equiv 0\; (\textrm{mod}\; 2^4)$ 時，如果把 $2^4$ 的完全剩餘系的元素一一代入，總共要代 $2^4=16$ 次才能得知該同餘式的解。

Hensel's lifting lemma，或簡稱 Hensel's lemma，給了我們一種解此種同餘方程式的方法。他的基本概念是，先解 $f(x)\equiv \; (\textrm{mod}\; p^2)$ ，再解 $f(x)\equiv \; (\textrm{mod}\; p)$，接著再解 $f(x)\equiv \; (\textrm{mod}\; p^3)\cdots$ 等等，"lifing(上升)"的概念就在於此。為什麼可以這樣做呢？我們舉一個例子。如果一個數能被 $2^3$ 整除，則這個數也一定能被 $2^2$ 及 $2$ 整除。當模數變小，求解的計算量也會變得比較輕鬆。

但是，一個數能被 $2$ 整除，不代表它一定也能被 $2^2$、甚至 $2^3$ 整除。因此從 $f(x)\equiv 0\; (\textrm{mod}\; 2)$ 求得的解，並不直接等於 $f(x)\equiv 0\; (\textrm{mod}\; 2^3)$。我們必須將從 $f(x)\equiv 0\; (\textrm{mod}\; 2)$ 求得的解一步步"篩選"，最後篩選留下滿足 $f(x)\equiv 0\; (\textrm{mod}\; 2^3)$ 的解。底下的證明，告訴我們如何進行"篩選"。

Theorem (Hensel's Lemma)
Let $f(x)$ be a polynomial with integer coefficients, $p$ be a prime, and suppose $a$ is a solution of the congruence $f(x)\equiv 0\; (\textrm{mod}\; p^j)$ such that $f'(a)\not\equiv 0\; (\textrm{mod}\; p)$. Then there exists an integer $t$ (which is unique $\; (\textrm{mod}\; p)$) such that $a + tp^j$ is a solution to the congruence $f(x)\equiv 0\; (\textrm{mod}\; p^{j+1})$.

<proof>
一個 $n$ 階多項式 $f(x)$ 在 $x=a$ 時的 Taylor series 為 $$f(x)=f(a)+\frac{f^{(1)}(a)}{1!}(x-a)^{1}+\frac{f^{(2)}(a)}{2!}(x-a)^{2}+\cdots +\frac{f^{(n)}(a)}{n!}(x-a)^{n}=\sum_{i=1}^{n}\frac{f^{(i)}(a)}{i!}(x-a)^{i}$$ 將 $x=s=a+tp^{j-1}$ 代入上式，得到 $$f(s)=f(a+tp^{j-1})=f(a)+\frac{f'(a)}{1!}[(a+tp^{j-1})-a]+\frac{f''(a)}{2!}[(a+tp^{j-1})-a]^2+\cdots +\frac{f^{(n)}(a)}{n!}[ (a+tp^{j-1})-a]^n=\sum_{k=0}^{n}\frac{f^{(k)}(a)}{k!}(tp^{j-1})^k$$ 因為 $s$ 是 $f(x)\equiv 0\; (\textrm{mod}\; p^j)$ 的解，我們有 $$\begin{array} 00 &\equiv f(s) \\ &= f(a+tp^{j-1}) \\ &= f(a)+\frac{f'(a)}{1!}[(a+tp^{j-1})-a]+\frac{f''(a)}{2!}[(a+tp^{j-1})-a]^2+\cdots +\frac{f^{(n)}(a)}{n!}[ (a+tp^{j-1})-a]^n \\ &\equiv f(a)+f'(a)\cdot tp^{j-1}\; (\textrm{mod}\; p^j) \end{array}$$ 因此 $$f'(a)\cdot tp^{j-1}\equiv -f(a)\; (\textrm{mod}\; p^j)$$ 將上式同除以 $p^{j-1}$，得到 $$f'(a)\cdot t\equiv -\frac{f(a)}{p^{j-1}}\; (\textrm{mod}\; p)$$ 我們只要找出滿足上式的 $t$ 值，就可以解方程式 $f(x)\equiv 0\; (\textrm{mod}\; p^j)$。

令 $d=\textrm{gcd}\left ( f'(a),p \right )$。我們知道，當 $d\mid \frac{f(a)}{p^{k-1}}$，同餘方程式 $f'(a)\cdot t\equiv -\frac{f(a)}{p^{j-1}}\; (\textrm{mod}\; p)$ 恰有 $d$ 個解；當 $d\nmid \frac{f(a)}{p^{k-1}}$，則此同餘方程式無解。

我們分三種情況討論：
Case 1: $f'(a)\not\equiv 0\; (\textrm{mod}\; p)$.
因為 $f'(a)\not\equiv 0\; (\textrm{mod}\; p)$，所以 $d=1$。此同餘方程式有唯一解：$t\equiv -\overline{f'(a)}\cdot \frac{f(a)}{p^{k-1}}\; (\textrm{mod}\; p)$，$\overline{f'(a)}$ 是 $f'(a)$ 模 $p$ 之乘法反元素，即 $f(a) \cdot \overline{f'(a)}\equiv 1\; (\textrm{mod}\; p)$。

Case 2: $f'(a)\equiv 0\; (\textrm{mod}\; p)$ and $f(a)\equiv 0\; (\textrm{mod}\; p^j)$.
因為 $f'(a)\equiv 0\; (\textrm{mod}\; p)$，所以 $d=p$；因為 $f(a)\equiv 0\; (\textrm{mod}\; p^j)$，所以 $p\mid \frac{f(a)}{p^{j-1}}$。我們得到 $f(a+tp^{j-1})\equiv 0\; (\textrm{mod}\; p)$ 對所有整數 $t$ 都成立。

Case 3: $f'(a)\equiv 0\; (\textrm{mod}\; p)$ and $f(a)\not\equiv 0\; (\textrm{mod}\; p^j)$.
因為 $f'(a)\equiv 0\; (\textrm{mod}\; p)$，所以 $d=p$；但是 $f(a)\not\equiv 0\; (\textrm{mod}\; p^j)$，所以 $p\nmid \frac{f(a)}{p^{j-1}}$。因此找不到 $t$ 值使同餘方程式成立，也就是無解。


Corollary
設 $a$ 是 $f(x)\equiv 0\; (\textrm{mod}\; p)$ 的解，其中 $p$ 是質數。若 $f'(x)\not \equiv 0\; (\textrm{mod}\; p)$ ，則對於每個 $j$，方程式 $f(x)\equiv 0\; (\textrm{mod}\; p^j)$ 存在唯一解 $a_j$，其中 $a_j$ 是從 $a$ 而來，公式為：$a_1=a$ 且 $a_j=a_{j-1}-f(a_{j-1})\cdot \overline{f'(a)}$，其中 $\overline{f'(a)}$ 是 $f'(a)$ 模 $p$ 之乘法反元素。

<proof>
根據 Hensel's Lemma，當 $f(x)\equiv 0\; (\textrm{mod}\; p^j)$ 且 $f'(a)\not\equiv 0\; (\textrm{mod}\; p)$ 時，有 $$a_j:=a_{j-1}+\left ( -\overline{f'(a)} \cdot \frac{f(a_{j-1})}{p^{j-1}} \right )p^{k-1}=a_{j-1}-f(a_{j-1})\cdot \overline{f'(a)}$$ 滿足方程式 $f(a_k)\equiv 0\; (\textrm{mod}\; p)$

[數論] p-adic Numbers (p進數)

參考資料
A first introduction to p-adic numbers http://www.madore.org/~david/math/padics.pdf
Complete Metric Spaces http://pioneer.netserv.chula.ac.th/~lwicharn/2301631/Complete.pdf

一段關於 $p$-adic 的說明影片，片長約17分鐘。

◎ $p$-adic digit
$p$-adic 的 $p$ 是 prime 的意思。我們稱一個介於 $0$ 到 $p-1$ 的整數為 $p$-adic digit。

◎ $p$-adic integer
一個 $p$-adic integer 是指一個由 $p$-adic digit 組成的序列(sequence) $\left ( a_i \right )_{i\in \mathbb{N}}$。可寫成 $$\cdots a_i\cdots a_2a_1a_0$$ 或寫成 $$a=\sum_{i=i_0}^{\infty }a_i\cdot p^i.$$
◎ $p$-adic number
一個 $p$-adic integer 是指一個由 $p$-adic digit 組成的序列(sequence) $\left ( a_i \right )_{i\in \mathbb{Z}}$，或寫成 $$a=\sum_{i=0}^{\infty }a_i\cdot p^i,\: \; a_i\in \left \{ 0,1,2,\cdots ,p-1 \right \}$$ 如果一個 $p$-adic number $a$，對於 $i<0$，$a_i=0$，則我們特別稱 $a$ 為 $p$-adic integer。(可以回上一段看 $p$-adic integer 的定義。)

$p$-adic integers 構成一個 ring: $\mathbb{Z}_p$；$p$-adic numbers 構成一個 field: $\mathbb{Q}_p$。

◎ $p$-adic norm ($p$-adic absolute value)
一般在沒有特地說明之下，我們稱的距離就是歐式距離(Euclidean distance)，也就是「$m$ 維空間中、兩個點之間的真實距離。」例如在數線(一維空間)上有兩點 $a$ 和 $b$，我們會說 $a$ 和 $b$ 的距離是 $\left | a-b \right |$，亦即兩數之差的絕對值。

$p$-adic 的「距離」概念建立在整數的整除性質上。給定一質數 $p$，若兩個數之差能被 $p$ 的高次冪整除，那麼這兩個數距離就「接近」。冪次越高，距離越近。

給定一個非零的有理數 $x$，我們可以把 $x$ 表示為 $$x=p^a\cdot \frac{r}{s}$$ 其中 $p$ 是質數，$p$、$r$、$s$ 三數彼此互質。則我們定義 $x$ 的 $p$-adic norm(或是 $x$ 的 $p$-adic absolute value)為 $$\left | x \right |_p=p^{-a}.$$ 我們也定義 $$\left | 0 \right |_p=0.$$ 例如給定一有理數 $x=\frac{968}{9}$ 及一質數 $p=11$，則 $\frac{968}{9}$ 的 $11$-adic norm 為 $$\left | x \right |_p=\left | \frac{968}{9} \right |_{11}=\left | 11^2\cdot \frac{8}{9} \right |_{11}=11^{-2}.$$ 有了 $p$-adic norm，我們就能定義何謂 $p$-adic 的「距離」（數學上稱距離為「度量」），也就是 $p$-adic metric($p$進度量)。

◎ $p$-adic metric
我們將兩個數 $x$ 和 $y$ 的 $p$-adic metric 寫為 $d(x,y)=\left | x-y \right |_p$。例如取 $p=7$，則 $2$ 和 $28814$ 的 $7$-acid metric 為 $$\left | 28814-2 \right |_7=\left | 28812 \right |_7=\left | 7^4\cdot 13 \right |_7=7^{-4}.$$ ◎實數的完備性(Completeness)
我們知道，有理數是不具備完備性的。例如給定一條數線，若我們限定只能標示有理數，則很遺憾地，我們永遠無法指出 $\sqrt{2}$ 的位置，理由是 $\sqrt{2}$ 是無理數。

如果一個空間中的任何柯西序列(Cauchy sequence)，都收斂在該空間之內，我們稱此空間是「完備度量空間(Complete Metric Spaces)」。關於柯西序列，這裡不多作討論，簡單來說，就是如果有一個數列，我們任取一個正數，你總是能在這個數列中找到某兩項，使其兩項之差的絕對值，永遠小於這個正數，我們稱具有此性質的數列為柯西序列。

因此對於 matric $d(x,y)=\left | x-y \right |_p$，$a=\sum_{i=i_0}^{\infty }a_ip^i$ 的部份和(partial sums)會趨近於 $a$。

[數論] 完全數 (Perfect Number)

參考資料
傅鍾鵬，數學英雄 歐拉，凡異，2005出版，ISBN：9576945682
完全數的小故事 http://euler.tn.edu.tw/allno.htm
張鎮華，完全數與莫仙尼質數 http://episte.math.ntu.edu.tw/articles/sm/sm_02_03_1/

一、何謂完全數
定義：完全數(Perfect Number)等於除了本身以外的所有正因數的和。

我們用數學符號 $\sigma (n)$ 表示 $n$ 的正因數的和。例如 $\sigma (8)=1+2+4+8=15$。因此上述的定義可寫為 $$\textrm{n is a perfect fumber if}\; \sigma (n)=2n.$$
完全數這個名詞很早就為人所熟悉。古人認為「$6$」是屬於美神維納斯的專利，它象徵著美滿的婚姻；也有人認為是因為上帝創造世界也是花了 $6$ 天的時間；$28$ 也是一個完全數，它象徵月亮繞行地球的間：恰為 $28$ 天。

公元前 $300$ 年左右，希臘數學家歐基里德(Euclid)提出「完全數」的概念。在《幾何原本》第九卷第 $36$ 個命題(可點此查看詳細內容)首次提及完全數。歐基里德發現了第一個到第四個完全數，並給出一個完全數的定理：

令整數 $n>1$。若 $2^n-1$ 是質數，則 $2^{n-1}(2^n-1)$ 是完全數。

由於根據上述定理得到得完全數皆為偶數，這些完全數我們稱作「偶完全數」。到了18世紀，歐拉(Euler)證明了逆命題亦為真。下面我們將證明該定理之充分性及必要性。

二、證明
◎充分性$(\Rightarrow )$(Euclid)：設 $2^n-1=p$ 為質數。改寫 $2^{n-1}(2^n-1)=2^{n-1}p$ $$\begin{array} \sigma \sigma \left ( 2^{n-1}p \right ) &= \left ( 1+2+2^2+\cdots +2^{n-1} \right )+\left ( p+2p+2^2p+\cdots +2^{n-1}p \right ) \\ &= \left ( \frac{2^n-1}{2-1} \right )+p\left ( \frac{2^n-1}{2-1} \right ) \\ &= \left ( p-1 \right )\left ( 2^n-1 \right ) \\ &= 2^n\left ( 2^n-1 \right ) \\ &= 2\left [ 2^{n-1}\left ( 2^n-1 \right ) \right ]\; \; \textrm{Q.E.D.} \end{array}$$
◎必要性$(\Leftarrow )$(Euler)：see here.

求偶完全數的問題，等同於尋找適當的質數 $n$，使得 $(2^n-1)$ 為質數的問題。數學上，稱形如 $2^n-1$ 的質數為「梅森質數(Mersenne Number)」。關於梅森質數的介紹，可以參考維基百科的介紹，請點此。

[數論] 高次同餘式 (Polynomial Congruences)

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
Polynomial Congruences 
http://www.cs.xu.edu/math/math302/04f/PolyCongruences.pdf
http://www2.latech.edu/~schroder/slides/number_theory/14_polynomial_congruences.pdf

在上一篇我們介紹並討論一次同餘式（組）的求解。本篇將討論關於高次同餘式的性質及求解方法。

一、高次同餘式介紹
一個典型的高次同餘式可表示為 $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; m) , \textrm{where}\; a_i\in \mathbb{Z}, i=0,1,\cdots ,n$$
若模數 $m$ 是質數，我們可以透過質數的特性去探討同餘式之解的存在性及求解；若模數 $m$ 是合數，通常的處理方法是把該模數轉為質數模數加以研究。

若 $m_1, m_2,\cdots ,m_n$ 是 $n$ 個兩兩互質的正整數，$m=m_1m_2\cdots m_n$，則同餘方程式 $$f(x)\equiv 0\; (\textrm{mod}\; m)$$ 與同餘方程組  $$f(x)\equiv 0\; (\textrm{mod}\; m_i), \; i=1,2,\cdots n$$ 具有相同解。若用 $T_i$ 表示 $f(x)\equiv 0\; (\textrm{mod}\; m_i)$ 的解的個數，$T$ 表示 $f(x)\equiv 0\; (\textrm{mod}\; m)$ 的解的個數，則 $$T=T_1T_2\cdots T_n$$ 以下僅討論模數 $m$ 為質數的情況。

對於 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0\equiv 0$(mod $p$)，其中 $p$ 是質數，且 $p\nmid a_i$，$i=0,1,\cdots ,n$，求解的基本方法有二：

1. 將模 $p$ 的完全剩餘系 $\left \{ 0,1,\cdots ,p-1 \right \}$ 的元素逐一代入同餘式
此方法毋需其他特殊技巧，當 $p$ 很小的時候相當實用。但當 $p$ 很大的時候，使用此方法就顯得缺乏效率。

2. 降低原式的複雜度
2.1 降低 $f(x)$ 中的 $x^i$ 的係數，或是降低 $f(x)$ 的次數。

<例1> 求解同餘式 $x^{10}+^7-x^3+3\equiv 0$ (mod $5$)
<解1> 因為 $(x,5)=1$，由 Euler's theorem 知 $x^{\phi (5)}\equiv x^4\equiv 1$ (mod $5$)。故原式可化簡為 $$x^{10}+x^7-x^3+3\equiv x^2+x^3-x^3+3\equiv x^2+3 \equiv 0\; (\textrm{mod}\; 5)$$ 即原式與 $x^2+3 \equiv 0\; (\textrm{mod}\; 5)$ 有相同的解。

將模 $5$ 的完全剩餘系 $\left \{ 0,1,2,3,4 \right \}$ 元素逐一代入 $x^2+3 \equiv 0\; (\textrm{mod}\; 5)$ ，發現此同餘式無解，故原同餘式也無解。

2.2 利用因式分解
假設 $f(x)=q(x)g(x)\equiv 0\; (\textrm{mod}\; p)$，即 $q(x)\equiv 0\; (\textrm{mod}\; p)$，$p(x)\equiv 0\; (\textrm{mod}\; p)$。

2.3 $f(x)\equiv 0\; (\textrm{mod}\; p)$ 必與一個次數小於 $p$ 的質數模 $p$ 的同餘式有相同的解
若 $f(x)$ 的次數 $n< p$，結論顯然成立。

若 $f(x)$ 的次數 $n\geq p$，由多項式的帶餘式除法知，存在兩個整係數多項式 $q(x)$ 與 $r(x)$，使 $$f(x)=(x^p-x)\cdot q(x)+r(x)$$ 其中 $r(x)$ 的次數小於 $p$。

為何選擇 $x^p-x$ 作為除式？由費馬小定理，易知 $x^p-x$ 可以被 $p$ 整除，所以 $$f(x)=(x^p-x)\cdot q(x)+r(x)\equiv r(x)\; (\textrm{mod}\; p)$$ 也就是說，$f(x)\equiv 0\; (\textrm{mod}\; p)$ 與 $r(x)\equiv 0\; (\textrm{mod}\; p)$ 同解。


二、Lagrange定理
定義：設 $p$ 是質數，且 $p\nmid a_n$，則模 $p$ 的 $n$ 次同餘式 $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$ 最多有 $n$ 個解。

<pf> 反證法。假設 $n$ 次同餘式 $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$ 的解超過 $n$ 個。其中 $a_n\not\equiv 0\; (\textrm{mod}\; p)$，則此式至少有 $n+1$ 個不同的解，設為 $$x\equiv \alpha _i\; (\textrm{mod}\; p)\; \; i=1,2,\cdots ,n,n+1.$$ 我們可以將原式改寫為 $$f(x)\equiv a_n(x-\alpha _1)(x-\alpha _2)\cdots (x-\alpha _n)\; (\textrm{mod}\; p).$$ 因為$f(\alpha _{n+1})\equiv 0 (\textrm{mod}\; p)$，所以 $$a_n(\alpha _{n+1}-\alpha _1)(\alpha _{n+1}-\alpha _2)\cdots (\alpha _{n+1}-\alpha _n)\equiv 0\; (\textrm{mod}\; p).$$ 由於 $p$ 是質數，且 $a_n\not\equiv 0\; (\textrm{mod}\; p)$，故存在某個 $\alpha _i$，使得 $$\alpha _{n+1}-\alpha _i\equiv 0\; (\textrm{mod}\; p)$$ 即 $$\alpha _{n+1}\equiv \alpha _i\; (\textrm{mod}\; p)$$ 這與假設矛盾。所以此方程式最多只有 $n$ 個解。

Lagrange定理僅給了一個模 $p$ 的 $n$ 次同餘式解的個數上限，並不保證解的存在性。首先，我們想知道，在什麼情況下，解的個數恰好為 $n$ 個？


三、再探解的個數
性質一：設 $p$ 為質數。若 $n\leq p$，則同餘式 $$f(x)=x^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0\equiv 0\; (\textrm{mod}\; p)$$ 有 $n$ 個解的充分必要條件是 $x^p-x$ 除以 $f(x)$ 的餘式的所有係數都是 $p$ 的倍數。

<pf> 我們可以將 $x^p-x$ 寫為 $$x^p-x=f(x)\cdot q(x)+r(x)$$ 其中 $q(x)$ 是一個 $p-n$ 次的多項式，餘式 $r(x)$ 的次數小於 $n$。

充分性$(\Rightarrow )$：若所給同餘式有 $n$ 個解，由上述 2.3 知，這 $n$ 個解也會是 $r(x)\equiv 0\; (\textrm{mod}\; p)$ 的解。但 $r(x)$ 的次數小於 $n$，根據 Lagrange 定理，$r(x)$ 的係數必定都是 $p$ 的倍數。

必要性$(\Leftarrow )$：若 $r(x)$ 的係數皆可被 $p$ 整除，因為 $x^p-x\equiv 0\; (\textrm{mod}\; p)$，所以有 $f(x)q(x)\equiv 0\; (\textrm{mod}\; p)$，有 $p$ 個不同的解 $$x\equiv 0,1,\cdots ,p-1\; (\textrm{mod}\; p)$$ 若 $f(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數 $k<n$，因為 $q(x)$ 是一個 $p-n$ 次的多項式，由 Lagrange 定理知，$q(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數 $h\leq p-n$。因此 $f(x)q(x)\equiv 0\; (\textrm{mod}\; p)$ 的解的個數等於 $k+h<n+(p-n)=p$，但前面又說明此同餘式有 $p$ 個不同的解，故所給同餘式有 $n$ 個解。


性質二：設 $p$ 為質數，$d\mid p$，則同餘式 $x^d\equiv 1\; (\textrm{mod}\; p)$ 恰有 $d$ 個解。

[數論] 一次同餘式 (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