初等數論/原根

数论 > 初等数论 > 初等數論/原根

---

根據費馬小定理及其推廣，我們可知當(a,m)=1時，存在d<m，使$a^d\equiv 1(\mathrm{mod}m)$，其中d=$\varphi (m)$，下面來定義原根：

(a,m)=1時，使$a^d\equiv 1(\mathrm{mod}m)$成立的最小整數d，定義為$D_m(a)$，當$D_m(a)$=$\varphi (m)$時，稱使此式成立的a是模m的原根

模m有原根的充要條件為：$m=1,2,4,p^n,2p^n$，其中p是奇質數