[數論] 原根 (Primitive Roots)

參考資料
張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493
李華介，基礎數論 http://math.ntnu.edu.tw/~li/ent-html/node34.html
Integers with Primitive Roots https://proofwiki.org/wiki/Integers_with_Primitive_Roots
Primitive Roots Modulo the First 1000 Numbers
http://dbfin.com/2012/04/primitive-roots-modulo-the-first-1000-numbers/

在前兩篇 (二次剩餘，Legendre Symbol) 我們只有討論二次剩餘的存在性，並沒有給出一個完整地求解方法，當然列舉法也算一種求解方法，但這不在本篇的討論範圍內。為了要求解，我們會用到「原根(Primitive roots)」的概念。

原根定義
設整數 $a$ 和 $m$ 互質。 使 $a^{\delta }\equiv 1\; (\mathbf{mod\; }m)$ 成立的最小正整數 $\delta$ 稱為 $a$ 對模 $m$ 的次數(degree)或階(order)。根據 Euler's theorem，若 整數 $a$ 和 $m$ 互質，則 $a^{\phi (m)}\equiv 1\; (\mathbf{mod\; }m)$。當 $\delta =\phi (m)$，稱 $a$ 是模 $m$ 的一個原根。

定理1：若 $a$ 對模 $m$ 的次數是 $\delta$。若 $\delta \mid n$，則 $a^{n}\equiv 1\; (\mathbf{mod}\; m),\; n>0$ 。
<pf>
這是一個充分必要條件的證明。
先證明充分性。假設 $\delta \mid n$，即 $n=k\cdot \delta ,k\in \mathbb{Z}$。因此 $a^{n}\equiv a^{k\cdot \delta }\equiv \left (a^{\delta }  \right )^{k}\equiv 1^{k}\equiv 1\; (\mathbf{mod}\; m)$。

證明必要性。若 $n$ 不是 $\delta$ 的倍數，表示存在兩整數 $q$、$r$，使得 $n=q\delta +r,\; 0<r<\delta$，則

$1\equiv a^{n}\equiv a^{q\delta +r}\equiv \left (a^{\delta}  \right )^{q}\cdot a^{r}\equiv 1\cdot a^{r}\equiv a^{r}\; (\mathbf{mod}\; m)$，

這與 $\delta$ 為最小的定義矛盾，故 $\delta \mid n$。證畢。

定理2：若 $a$ 對模 $m$ 的次數為 $\delta$，則 $1,a,a^2,\cdots ,a^{\delta -1}$ 對模 $m$ 皆不同餘。
<pf>
假設有兩整數 $k$，$l$，滿足 $a^{k}\equiv a^{l}\; (\mathbf{mod}\; m),\; 0\leq k< l<\delta$。因為 gcd$(a,m)=1$，故有 $\frac{a^{l}}{a^{k}}\equiv a^{l-k}\equiv 1\; (\mathbf{mod}\; m)$。因為 $l-k<\delta$，這與 $\delta$ 是最小的定義矛盾，故原命題成立。

在 二次剩餘 這篇，證明 Euler's Criterion 時，就用到了原根的性質。利用原根的概念，$m$ 的簡化剩餘系可以用一套規律的方式寫下。假設 $a$ 是模 $m$ 的一個原根，根據上述定理2，$\left \{ a^{0},a^{1},\cdots ,a^{\phi (m)-1} \right \}$ 其實就是模 $m$ 的簡化剩餘系。我們之後習慣用這種簡化剩餘系說明之。

$\left \{ a^{0},a^{1},\cdots ,a^{\phi (m)-1} \right \}$ 是模 $m$ 的簡化剩餘系。

定理3：若 $a$ 對模 $m$ 的次數是$r$。設有一數 $\lambda >0$，$a^{\lambda }$ 對模 $m$ 的次數是 $t$，則 $t=\frac{r}{(\lambda ,r)}$。
<pf>
根據上述定理1，我們有 $r\mid \lambda t$，即得 $\frac{r}{(\lambda ,r)}\mid \frac{\lambda }{(\lambda ,r)}\cdot t$。因為 $\left ( \frac{r}{(\lambda ,r)} ,\frac{\lambda }{(\lambda ,r)}\right )=1$，所以 $\frac{r}{(\lambda ,r)}\mid t$。

另一方面，$(a^{\lambda })^{\frac{r}{(\lambda ,r)}}\equiv a^{r\cdot \frac{\lambda }{(\lambda ,r)}}\equiv 1\; (\mathbf{mod}\; m)$，根據定理1，有 $t\mid \frac{r}{(\lambda ,r)}$。所以 $t=\frac{r}{(\lambda ,r)}$。

這個定理告訴我們，如果 $g$ 是模 $m$ 的原根，則 $g^{k}$ 是模 $m$ 原根的充分必要條件是 gcd$(k,\phi (m))=1$。這是一個非常重要的結論！例如我們找到了模 $m$ 的一個原根 $g$，只要 $g$ 的次方數 $k$ 與 $\phi (m)$ 互質，那麼 $g^k$ 也會是模 $m$ 的一個原根。換句話說，

只要找到了模 $m$ 的一個原根，我們就可以找出其他的原根。

定理4：設 $a$ 對模 $m$ 的次數是 $\delta$。若 gcd$(\lambda ,\delta )=1$，$0<\lambda \leq \delta$，則 $a^{\lambda }$ 對模 $m$ 的次數均為 $\delta$，符合條件的 $\lambda$ 有 $\phi (\delta )$ 個。

<pf>
在 $1,2,\cdots ,\delta$ 中，與 $\delta$ 互質的數有 $\phi (\delta )$ 個。當 gcd$(\lambda ,\delta )=1$，根據定理3，我們知道 $a^{\lambda }$ 對模 $m$ 的次數均為 $\delta$。證畢。

根據定理3，只要 $g$ 的次方數 $k$ 與 $\phi (m)$ 互質，那麼 $g^k$ 也會是模 $m$ 的一個原根。與 $\phi (m)$ 互質的數的個數有 $\phi (\phi (m))$。換句話說，

設模 $m$ 有原根，則它共有 $\phi (\phi (m))$ 個對於模 $m$ 不相同的原根。

定理5：若 $a$ 對模 $m$ 的次數為 $s$，$b$ 對模 $m$ 的次數為 $t$。若 gcd$(s,t)=1$，則 $ab$ 對模 $m$ 的次數為 $st$。
<pf>
設 $ab$ 對模 $m$ 的次數為 $\delta$。$(ab)^{st}=a^{st}\cdot b^{st}=[a^{s}]^{t}\cdot [b^{t}]^{s}\equiv 1\; (\mathbf{mod}\; m)$。我們得到 $\delta \mid st$。

另一方面，$1\equiv [(ab)^{\delta }]^{s}\equiv (ab)^{s\delta }\equiv a^{s\delta }\cdot b^{s\delta }\equiv a^{s\delta }\cdot (b^{s})^\delta \equiv b^{s\delta }\; (\mathbf{mod}\; m)$，我們得到 $t\mid s\delta$。因為 gcd$(s,t)=1$，所以 $t\mid s\delta$ 可改寫成 $t\mid \delta$。

同理，$1\equiv [(ab)^{t}]^{\delta }\equiv a^{t\delta }\cdot b^{t\delta }\equiv (a^{t})^\delta \cdot b^{t\delta }\equiv b^{t\delta }\; (\mathbf{mod}\; m)$，可以得到 $s\mid \delta$。因為 gcd$(s,t)=1$，所以有 $st\mid \delta$，而一開始已證明 $\delta \mid st$，故 $st=\delta$，證畢。

實際解二次同餘方程之前，其實有很多東西要講。首先，原根是否一定存在？答案是否，原根必須要符合某些條件才會存在。例如對於模 $8$，$\phi (8)=\phi \left ( 2^{3} \right )=2^{3}-2^{2}=4$，由於任何與 $8$ 互質的整數都是奇數，奇數的平方除以 $8$ 都是餘 $1$，這表示對於奇數 $x$，$x^{2}\equiv 1\; (\mathbf{mod}\; 8)$，$2< \phi (8)$，故模 $8$ 沒有原根。

討論完原根的存在性之後，接著再討論如何求出原根，最後利用原根的特性，求出二次同餘式、甚至是高次同餘式的解。

原根的存在性

若 $m$ 為 $2$, $4$, $p^{k}$, $2p^{k}$ ($p$ 為奇質數) 四者之一時，原根才存在。

證明可在各數論書籍找到，故略。我們把重點放在原根的計算上。

原根的計算