初等數論--原根--怎么判斷a是不是模m的原根

博主是初學初等數論（整除+同余+原根），本意是想整理一些較難理解的定理、算法，加深記憶也方便日后查找；如果有錯，歡迎指正。
我整理成一個系列：初等數論，方便檢索。

• 根據定義

$m$為正整數，$(a,m)=1,$滿足$a^d\equiv 1(modm)$的最小正整數$d$，如果$d=\phi (m),$那么$a$是模$m$的原根。

這種方法需要使$d$遍歷$\{1,2,3\dots \dots \phi (m)?1,\phi (m)\}$,如果$d$直到試到$\phi (m)$才有$a^d\equiv 1(modm),$那么$a$是模$m$的原根。

• 根據$or{d}_m(a)\mid \phi (m)$

由歐拉定理證明過的“如果$(a,n)=1,$則$a^{\phi (n)}\equiv 1(modn)”，$我們知道一定有$a^{\phi (m)}\equiv 1(modm)$；所以對于$a^{or{d}_m(a)}\equiv 1(modm),$且$or{d}_m(a)$“最小”，所以$or{d}_m(a)\mid \phi (m)$。

這樣我們就不需要遍歷$\{1,2,3\dots \dots \phi (m)?1,\phi (m)\}$了，只用遍歷$\phi (m)$的正因子即可。

總結

以上是生活随笔為你收集整理的初等数论--原根--怎么判断a是不是模m的原根的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。