[數論] 原根(Primitive Roots) - 數學筆記

為了要求解，我們會用到「原根(Primitive roots)」的概念。

... 設整數$a$ 和$m$ 互質。

使$a^{\delta }\equiv 1\; (\mathbf{mod\; }m)$ 成立的最小正整數$\ ... 2014年6月23日星期一 [數論]原根(PrimitiveRoots) 參考資料 張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493 李華介，基礎數論 http://math.ntnu.edu.tw/~li/ent-html/node34.html IntegerswithPrimitiveRoots https://proofwiki.org/wiki/Integers_with_Primitive_Roots PrimitiveRootsModulotheFirst1000Numbers http://dbfin.com/2012/04/primitive-roots-modulo-the-first-1000-numbers/ 在前兩篇(二次剩餘，LegendreSymbol) 我們只有討論二次剩餘的存在性，並沒有給出一個完整地求解方法，當然列舉法也算一種求解方法，但這不在本篇的討論範圍內。

為了要求解，我們會用到「原根(Primitiveroots)」的概念。

原根定義 設整數$a$和$m$互質。

使$a^{\delta}\equiv1\;(\mathbf{mod\;}m)$成立的最小正整數$\delta $稱為$a$對模$m$的次數(degree)或階(order)。

根據Euler'stheorem，若整數$a$和$m$互質，則$a^{\phi(m)}\equiv1\;(\mathbf{mod\;}m)$。

當$\delta=\phi(m)$，稱$a$是模$m$的一個原根。

定理1：若$a$對模$m$的次數是$\delta$。

若 $\delta\midn$，則 $a^{n}\equiv1\;(\mathbf{mod}\;m),\;n>0$。

這是一個充分必要條件的證明。

先證明充分性。

假設$\delta\midn$，即$n=k\cdot\delta,k\in\mathbb{Z}$。

因此$a^{n}\equiva^{k\cdot\delta}\equiv\left(a^{\delta} \right)^{k}\equiv1^{k}\equiv1\;(\mathbf{mod}\;m)$。

證明必要性。

若$n$不是$\delta$的倍數，表示存在兩整數$q$、$r$，使得$n=q\delta+r,\;0 假設有兩整數$k$，$l$，滿足$a^{k}\equiva^{l}\;(\mathbf{mod}\;m),\;0\leqk0$，$a^{\lambda}$對模$m$的次數是$t$，則$t=\frac{r}{(\lambda,r)}$。

根據上述定理1，我們有$r\mid\lambdat$，即得$\frac{r}{(\lambda,r)}\mid\frac{\lambda}{(\lambda,r)}\cdott$。

因為$\left(\frac{r}{(\lambda,r)},\frac{\lambda}{(\lambda,r)}\right)=1$，所以$\frac{r}{(\lambda,r)}\midt$。

另一方面，$(a^{\lambda})^{\frac{r}{(\lambda,r)}}\equiva^{r\cdot\frac{\lambda}{(\lambda,r)}}\equiv1\;(\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 在$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$。

設$ab$對模$m$的次數為$\delta$。

$(ab)^{st}=a^{st}\cdotb^{st}=[a^{s}]^{t}\cdot[b^{t}]^{s}\equiv1\;(\mathbf{mod}\;m)$。

我們得到$\delta\midst$。

另一方面，$1\equiv[(ab)^{\delta}]^{s}\equiv(ab)^{s\delta}\equiva^{s\delta}\cdotb^{s\delta}\equiva^{s\delta}\cdot(b^{s})^\delta\equivb^{s\delta}\;(\mathbf{mod}\;m)$，我們得到$t\mids\delta $。

因為gcd$(s,t)=1$，所以$t\mids\delta $可改寫成$t\mid\delta$。

同理，$1\equiv[(ab)^{t}]^{\delta}\equiva^{t\delta}\cdotb^{t\delta}\equiv(a^{t})^\delta\cdotb^{t\delta}\equivb^{t\delta}\;(\mathbf{mod}\;m)$，可以得到$s\mid\delta $。

因為gcd$(s,t)=1$，所以有$st\mid\delta$，而一開始已證明$\delta\midst$，故$st=\delta$，證畢。

實際解二次同餘方程之前，其實有很多東西要講。

首先，原根是否一定存在？答案是否，原根必須要符合某些條件才會存在。

例如對於模$8$，$\phi(8)=\phi\left(2^{3}\right)=2^{3}-2^{2}=4$，由於任何與$8$互質的整數都是奇數，奇數的平方除以$8$都是餘$1$，這表示對於奇數$x$，$x^{2}\equiv1\;(\mathbf{mod}\;8)$，$2