原根
前置知識
這部分知識與抽象代數相關。如果想要進一步瞭解文中的「階」、「原根」名字來源，可以參考羣論部分。
階
定義
由歐拉定理可知，對 \(a\in \mathbf{Z}\)，\(m\in\mathbf{N}^{*}\)，若 \((a,m)=1\)，則 \(a^{\varphi(m)}\equiv 1\pmod m\).
因此滿足同餘式 \(a^n \equiv 1 \pmod m\) 的最小正整數 \(n\) 存在，這個 \(n\) 稱作 \(a\) 模 \(m\) 的階，記作 \(\delta_m(a)\) 或 \(\operatorname{ord}_m(a)\).
注
在抽象代數中，這裏的「階」就是模 \(m\) 縮剩餘系關於乘法形成的羣中，元素 \(a\) 的階。記號 \(\delta\) 表示階也只用於這個特殊的羣。
下面的諸多性質可以直接擴展到抽象代數中階的性質。
另外還有「半階」的概念，在數論中會出現 \(\delta^-\) 記號，表示同餘式 \(a^n \equiv -1 \pmod m\) 的最小正整數。半階不是羣論中的概念。階一定存在，半階不一定存在。
性質
性質 1
\(a,a^2,\cdots,a^{\delta_m(a)}\) 模 \(m\) 兩兩不同餘。
證明
考慮反證，假設存在兩個數 \(i\ne j\)，且 \(a^i\equiv a^j\pmod m\)，則有 \(a^{|i-j|}\equiv 1\pmod p\).
但是顯然的有：\(0<|i-j|<\delta_m(a)\)，這與階的最小性矛盾，故原命題成立。
性質 2
若 \(a^n \equiv 1 \pmod m\)，則 \(\delta_m(a)\mid n\).
證明
對 \(n\) 除以 \(\delta_m(a)\) 作帶餘除法，設 \(n=\delta_m(a)q+r,0\leq r<\delta_m(a)\).
若 \(r>0\)，則
這與 \(\delta_m(a)\) 的最小性矛盾。故 \(r=0\)，即 \(\delta_m(a)\mid n\).
據此還可推出：
若 \(a^p\equiv a^q\pmod m\)，則有 \(p\equiv q\pmod{\delta_m(a)}\).
還有兩個與四則運算有關的重要性質。
性質 3
設 \(m\in\mathbf{N}^{*}\)，\(a,b\in\mathbf{Z}\)，\((a,m)=(b,m)=1\)，則
的充分必要條件是
證明
-
必要性：由 \(a^{\delta_m(a)}\equiv 1 \pmod m\) 及 \(b^{\delta_m(b)} \equiv 1 \pmod m\)，可知
\[ (ab)^{[\delta_m(a), \delta_m(b)]}\equiv 1 \pmod m \]由前面所述階的性質，有
\[ \delta_m(ab)\mid \left[\delta_m(a), \delta_m(b)\right] \]又由於 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\)，故
\[ \delta_m(a)\delta_m(b)\mid \left[\delta_m(a), \delta_m(b)\right] \]即 \((\delta_m(a),\delta_m(b))=1\).
-
充分性：由 \((ab)^{\delta_m(ab)}\equiv 1 \pmod m\) 可知
\[ 1 \equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)\delta_m(b)} \pmod m \]故 \(\delta_m(a)\mid\delta_m(ab)\delta_m(b)\). 結合 \((\delta_m(a),\delta_m(b))=1\) 即得
\[ \delta_m(a)\mid\delta_m(ab) \]對稱地，同理可得
\[ \delta_m(b)\mid\delta_m(ab) \]所以
\[ \delta_m(a)\delta_m(b)\mid\delta_m(ab) \]另一方面，有
\[ (ab)^{\delta_m(a)\delta_m(b)}\equiv(a^{\delta_m(a)})^{\delta_m(b)}\times(b^{\delta_m(b)})^{\delta_m(a)}\equiv 1 \pmod m \]故
\[ \delta_m(ab)\mid\delta_m(a)\delta_m(b) \]綜合以上兩點即得
\[ \delta_m(ab)=\delta_m(a)\delta_m(b) \]
性質 4
設 \(k \in \mathbf{N}\)，\(m\in \mathbf{N}^{*}\)，\(a\in\mathbf{Z}\)，\((a,m)=1\)，則
證明
注意到：
另一方面，由 \(a^{\delta_m(a)}\equiv 1 \pmod m\)，可知：
故：
綜合以上兩點，得：
原根
定義
設 \(m \in \mathbf{N}^{*}\)，\(g\in \mathbf{Z}\). 若 \((g,m)=1\)，且 \(\delta_m(g)=\varphi(m)\)，則稱 \(g\) 為模 \(m\) 的原根。
即 \(g\) 滿足 \(\delta_m(g) = \left| \mathbf{Z}_m^* \right| = \varphi(m)\). 當 \(m\) 是質數時，我們有 \(g^i \bmod m,\,0 \lt i \lt m\) 的結果互不相同。
注
在抽象代數中，原根就是循環羣的生成元。這個概念只在模 \(m\) 縮剩餘系關於乘法形成的羣中有「原根」這個名字，在一般的循環羣中都稱作「生成元」。
並非每個模 \(m\) 縮剩餘系關於乘法形成的羣都是循環羣，存在原根就表明它同構於循環羣，如果不存在原根就表明不同構。
原根判定定理
設 \(m \geqslant 3, (g,m)=1\)，則 \(g\) 是模 \(m\) 的原根的充要條件是，對於 \(\varphi(m)\) 的每個素因數 \(p\)，都有 \(g^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m\).
證明
必要性顯然，下面用反證法證明充分性。
當對於 \(\varphi(m)\) 的每個素因數 \(p\)，都有 \(g^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m\) 成立時，我們假設存在一個 \(g\)，其不是模 \(m\) 的原根。
因為 \(g\) 不是 \(m\) 的原根，則存在一個 \(t<\varphi(m)\) 使得 \(g^t\equiv 1\pmod{m}\).
由 裴蜀定理 得，一定存在一組 \(k,x\) 滿足 \(kt=x\varphi(m)+(t,\varphi(m))\).
又由 歐拉定理 得 \(g^{\varphi(m)}\equiv 1\pmod{m}\)，故有：
由於 \((t, \varphi(m)) \mid \varphi(m)\) 且 \((t, \varphi(m))\leqslant t < \varphi(m)\).
故存在 \(\varphi(m)\) 的素因數 \(p\) 使得 \((t, \varphi(m)) \mid \frac{\varphi(m)}{p}\).
則 \(g^{\frac{\varphi(m)}{p}}\equiv g^{(t, \varphi(m))}\equiv 1\pmod{m}\)，與條件矛盾。
故假設不成立，原命題成立。
原根個數
若一個數 \(m\) 有原根，則它原根的個數為 \(\varphi(\varphi(m))\).
證明
若 \(m\) 有原根 \(g\)，則：
所以若 \(\left(k,\varphi(m)\right)=1\)，則有：\(\delta_m(g^k)=\varphi(m)\)，即 \(g^k\) 也是模 \(m\) 的原根。
而滿足 \(\left(\varphi(m),k\right)=1\) 且 \(1\leq k \leq \varphi(m)\) 的 \(k\) 有 \(\varphi(\varphi(m))\) 個。所以原根就有 \(\varphi(\varphi(m))\) 個。
原根存在定理
原根存在定理
一個數 \(m\) 存在原根當且僅當 \(m=2,4,p^{\alpha},2p^{\alpha}\)，其中 \(p\) 為奇素數，\(\alpha\in \mathbf{N}^{*}\).
我們來證明它，分成 \(m=2,4\)、\(m=p^{\alpha}\)、\(m=2p^{\alpha}\) 與 \(m\ne 2,4,p,p^{\alpha}\)，四個部分。
-
\(m=2,4\)，原根顯然存在。
-
\(m=p^{\alpha}\)，其中 \(p\) 為奇素數，\(\alpha\in \mathbf{N}^*\).
定理 1
對於奇素數 \(p\)，\(p\) 有原根。
證明
先證一個引理：
設 \(a\) 與 \(b\) 是與 \(p\) 互素的兩個整數，則存在 \(c\in\mathbf{Z}\) 使得 \(\delta_p(c)=\left[\delta_p(a),\delta_p(b)\right]\).
證明
我們先將 \(\delta_m(a),\delta_m(b)\) 表示成質因數分解的形式：
\[ \left(\delta_m(a)=\prod_{i=1}^k{p_i^{\alpha_i}},\delta_m(b)=\prod_{i=1}^k{p_i^{\beta_i}} \right) \]接着將它們表示成如下形式：
\[ \delta_m(a)=XY,\delta_m(b)=ZW \]其中：
- \(Y=\prod_{i=1}^k{p_i^{[\alpha_i>\beta_i]\alpha_i}}\)
- \(X=\dfrac {\delta_m(a)}Y\)
- \(W=\prod_{i=1}^k{p_i^{[\alpha_i\le\beta_i]\beta_i}}\)
- \(Z=\dfrac {\delta_m(b)}W\)
則由階的 性質 4，可得：
\[ \begin{aligned} \delta_m\left(a^X\right)&=\dfrac{\delta_m(a)}{\left(\delta_m(a),X\right)}\\ &=\dfrac{XY}{X}\\ &=Y \end{aligned} \]同理：
\[ \delta_m\left(b^Z\right)=W \]又因為顯然有 \((Y,W)=1\)，\(YW=\left[\delta_p(a),\delta_p(b)\right]\)，則再由階的 性質 3，可得：
\[ \begin{aligned} \delta_m\left(a^Xb^Z\right)&=\delta_m\left(a^X\right)\delta_m\left(b^Z\right)\\ &=YW\\ &=\left[\delta_p(a),\delta_p(b)\right] \end{aligned} \]於是令 \(c=a^Xb^Z\) 則原命題得證。
回到原命題，對 \(1 \sim (p-1)\) 依次兩兩使用引理，可知存在 \(g\in \mathbf{Z}\) 使得
\[ \delta_p(g)=\left[\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1)\right] \]這表明 \(\delta_p(j)\mid\delta_p(g)(j=1,2,\cdots,p-1)\)，所以 \(j=1,2,\cdots,p-1\) 都是同餘方程
\[ x^{\delta_p(g)}\equiv 1\pmod p \]的根。由拉格朗日定理，可知方程的次數 \(\delta_p(g) \geq p-1\).
又由費馬小定理，易知 \(\delta_p(g) \leq p-1\)，故 \(\delta_p(g)=p-1=\varphi(p)\).
綜上可知 \(g\) 為模 \(p\) 的原根。
定理 2
對於奇素數 \(p\)，\(\alpha \in \mathbf{N}^{*}\)，\(p^\alpha\) 有原根。
證明
一個基本的想法是將模 \(p\) 的原根平移。
先證明一個引理：
存在模 \(p\) 的原根 \(g\)，使得 \(g^{p-1}\not\equiv 1 \pmod {p^2}\).
證明
事實上，任取模 \(p\) 的原根 \(g\)，若 \(g\) 不滿足條件，我們認定 \(g+p\) 滿足條件。
易知 \(g+p\) 也是模 \(p\) 的原根。
我們有
\[ \begin{aligned} (g+p)^{p-1}&\equiv \binom{p-1}{0}g^{p-1}+\binom{p-1}{1}pg^{p-2} \pmod {p^2}\\ &\equiv g^{p-1}+p(p-1)g^{p-2} \pmod {p^2}\\ &\equiv 1-pg^{p-2} \pmod {p^2}\\ &\not\equiv 1 \pmod {p^2} \end{aligned} \]回到原題，我們證明若 \(g\) 是一個滿足引理條件的原根，則對任意 \(\alpha\in\mathbf{N}^{*}\)，\(g\) 是模 \(p^{\alpha}\) 的原根。
首先，證明下面的結論：對任意 \(\beta\in\mathbf{N}^{*}\)，都可設
\[ g^{\varphi(p^\beta)}=1+p^{\beta} k_{\beta} \]這裏 \(p\nmid k_{\beta}\)。事實上，\(\beta=1\) 時，由 \(g\) 的選取可知結論成立。現設上式對 \(\beta\) 時成立，則
\[ \begin{aligned} g^{\varphi(p^{\beta+1})}&=\left(g^{\varphi\left(p^{\beta}\right)}\right)^p\\ &=\left(1+p^{\beta}k_{\beta}\right)^p\\ &\equiv 1+p^{\beta+1}k_{\beta} \pmod {p^{\beta+2}} \end{aligned} \]結合 \(p\nmid k_{\beta}\) 可知命題對 \(\beta+1\) 成立。
所以命題對任意 \(\beta\in\mathbf{N}^{*}\) 都成立。
其次，記 \(\delta=\delta_{p^\alpha}(g)\)，則由歐拉定理，可知 \(\delta\mid p^{\alpha-1}(p-1)\).
而由 \(g\) 為模 \(p\) 的原根，及 \(g^{\delta}\equiv 1\pmod {p^\alpha}\).
所以可設 \(\delta=p^{\beta-1}(p-1)\)，這裏 \(1\leq \beta\leq \alpha\).
現在利用之前的結論，可知：
\[ g^{\varphi(p^{\beta})}\not\equiv 1\pmod {p^{\beta+1}}\implies g^{\delta}\not\equiv 1\pmod {p^{\beta+1}} \]結合 \(g^{\delta}\equiv 1\pmod {p^\alpha}\) 可知 \(\beta \geq \alpha\).
綜上可知，\(\beta=\alpha\)，即：
\[ \delta_{p^{\alpha}}(g)=p^{\alpha-1}(p-1)=\varphi(p^\alpha) \]從而，\(g\) 是模 \(p^{\alpha}\) 的原根。
-
\(m=2p^{\alpha}\)，其中 \(p\) 為奇素數，\(\alpha\in\mathbf{N}^*\).
定理 3
對於奇素數 \(p\)，\(\alpha\in\mathbf{N}^{*}\)，\(2p^{\alpha}\) 的原根存在。
證明
設 \(g\) 是模 \(p^{\alpha}\) 的原根，則 \(g+p^{\alpha}\) 也是模 \(p^{\alpha}\) 的原根。
在 \(g\) 和 \(g+p^{\alpha}\) 中有一個是奇數，設這個奇數是 \(G\)，則 \((G,2p^{\alpha})=1\).
由歐拉定理，\(\delta_{2p^{\alpha}}(G)\mid\varphi(2p^{\alpha})\).
而 \(G^{\delta_{2p^{\alpha}}(G)}\equiv 1\pmod {2p^{\alpha}}\)，故：
\[ G^{\delta_{2p^{\alpha}}(G)}\equiv 1 \pmod {p^{\alpha}} \]利用 \(G\) 為模 \(p^{\alpha}\) 的原根可知 \(\varphi(p^{\alpha})\mid\delta_{2p^{\alpha}}(G)\).
結合 \(\varphi(p^{\alpha})=\varphi(2p^{\alpha})\) 可知 \(G\) 為模 \(2p^{\alpha}\) 的原根。
-
\(m\ne 2,4,p^{\alpha},p^{\alpha}\)，其中 \(p\) 為奇素數，\(\alpha\in\mathbf{N}^*\).
定理 4
對於 \(m\ne 2,4\)，且不存在奇素數 \(p\) 及 \(\alpha \in \mathbf{N}^{*}\) 使得 \(m=p^{\alpha},2p^{\alpha}\)，模 \(m\) 的原根不存在。
證明
對於 \(m=2^{\alpha}\)，\(\alpha\in\mathbf{N}^{*},\alpha\geq 3\)，則對任意奇數 \(a=2k+1\) 均有：
\[ \begin{aligned} a^{2^{\alpha-2}}&=(2k+1)^{2^{\alpha-2}}\\ &\equiv 1+\binom{2^{\alpha-2}}{1}(2k)+\binom{2^{\alpha-2}}{2}(2k)^{2} \pmod {2^{\alpha}}\\ &\equiv1+2^{\alpha-1}k+2^{\alpha-1}(2^{\alpha-2}-1)k^2 \pmod {2^{\alpha}}\\ &\equiv 1+2^{\alpha-1}(k+(2^{\alpha-2}-1)k^2) \pmod {2^{\alpha}}\\ &\equiv 1 \pmod {2^{\alpha}} \end{aligned} \]其中最後一步用到 \(k\) 與 \((2^{\alpha-2}-1)k^2\) 同奇偶，故其和為偶數。
若 \(m\) 不是 \(2\) 的冪，且 \(m\) 為符合題目條件的數，則可設 \(m=rt\)，這裏 \(2<r<t\) 且 \((r,t)=1\).
此時，若 \((a,m)=1\)，由歐拉定理可知：
\[ a^{\varphi(r)}\equiv 1 \pmod r\;,\quad a^{\varphi(t)}\equiv1\pmod t \]注意到 \(n>2\) 時，\(\varphi(n)\) 為偶數，所以：
\[ a^{\frac{1}{2}\varphi(r)\varphi(t)}\equiv 1\pmod {rt} \]進而：
\[ \delta_m(a)\leq\dfrac{1}{2}\varphi(r)\varphi(t)=\dfrac{1}{2}\varphi(rt)=\dfrac{1}{2}\varphi(m)<\varphi(m) \]由原根定義可得：模 \(m\) 的原根不存在。
綜合以上 \(4\) 個定理，我們便給出了一個數存在原根的充要條件。
最小原根的範圍估計
王元2和 Burgess1證明了素數 \(p\) 的最小原根 \(g_p=O\left(p^{0.25+\epsilon}\right)\)，其中 \(\epsilon>0\).
Fridlander3和 Salié4證明了素數 \(p\) 的最小原根 \(g_p=\Omega(\log p)\).
這保證了我們暴力找一個數的最小原根，複雜度是可以接受的。
參考資料與註釋
-
BURGESS, David A. On character sums and primitive roots.Proceedings of the London Mathematical Society, 1962, 3.1: 179-192. ↩
-
Wang Y. On the least primitive root of a prime (in Chinese).Acta Math Sinica, 1959, 4: 432–441; English transl. inSci. Sinica, 1961, 10: 1–14 ↩
-
FRIDLENDER, V. R. On the least n-th power non-residue. In:Dokl. Akad. Nauk SSSR. 1949. p. 351-352. ↩
-
SALIÉ, Hans. Über den kleinsten positiven quadratischen Nichtrest nach einer Primzahl.Mathematische Nachrichten, 1949, 3.1: 7-8. ↩
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用