原根

設m是正整數，a是整數，若a模m的階等於φ(m)，則稱a為模m的一個原根。（其中φ(m)表示m的歐拉函數）

假設一個數g對於P來說是原根，那麼的結果兩兩不同，且有 ,,那麼g可以稱為是P的一個原根，歸根到底就是當且當指數為的時候成立.(這裡P是素數).

簡單來說，（p為素數）

其中i≠j且i, j介於1至之間

則g為p的原根。

求原根目前的做法只能是從2開始枚舉，然後暴力判斷是否當且當指數為的時候成立

而由於原根一般都不大，所以可以暴力得到.

1）可以證明，如果正整數和正整數 d 滿足，則 d 整除 φ(m)。因此Ordm(a)整除φ(m)。在例子中，當時，我們僅需要驗證 3 的 1 、2、3 和 6 次方模 7 的餘數即可。

2）記，則模 m 兩兩不同餘。因此當a是模m的原根時，構成模 m 的簡化剩餘系。

3）模m有原根的充要條件是，其中p是奇質數，n是任意正整數。

4）對正整數，如果 a 是模 m 的原根，那麼 a 是整數模n乘法群（即加法群的可逆元，也就是所有與 m 互素的正整數構成的等價類構成的乘法群）Zn的一個生成元。由於Zn有 φ(m)個元素，而它的生成元的個數就是它的可逆元個數，即 φ(φ(m))個，因此當模m有原根時，它有φ(φ(m))個原根。

設，則φ（7）等於6。

設，由於，，而，，所以2不是模7的一個原根。設，由於，，，，，，所以3是模7的一個原根。

補充一點，根據原根的性質1，只需要驗證，，，即可，這樣可以簡化運算。