元根学习笔记,原根和本原根

原根学习小记

摘要：

在数论，特别是整除理论中，原根是一个很重要的概念。由此，在时，定义对模的指数为使成立的最小的正整数。由前知一定小于等于，若，则称是模的原根。设，由于，，，，，，因此有，所以3是模7的一个原根。在例子中，当时，我们仅需要验证3的1、2、3和6次方模7的余数即可。记，则模m两两不同余。因此当是模的原根时，构成模m的简化剩余系。模有原根的充要条件是，其中是奇质数，是任意正整数。

（1）在数论，特别是整除理论中，原根是一个很重要的概念。

对于两个正整数 $gcd(a,m)=1$ ，由欧拉定理可知，存在正整数 $d le m-1$ ，比如说欧拉函数 $d= phi (m)$ ，即小于等于m的正整数中与m互质的正整数的个数，使得 $a^d equiv 1 pmod{m}$ 。由此，在 $gcd(a,m)=1$ 时，定义 $a$ 对模 $m$ 的指数 $Ord_m(a)$ 为使 $a^d equiv 1 pmod{m}$ 成立的最小的正整数 $d$ 。由前知 $Ord_m(a)$ 一定小于等于 $phi (m)$ ，若 $Ord_m (a) = phi (m)$ ，则称 $a$ 是模 $m$ 的原根。

设 $m=7$ ，则 $varphi (m)$ 等于6。

设 $a=2$ ，由于 $2^3 = 8 equiv 1 pmod{7}$ ，而 $displaystyle 3 < 6$ ，所以 2 不是模 7 的一个原根。
设 $a=3$ ，由于 $3^1 equiv 3 pmod{7}$ ， $3^2 equiv 2 pmod{7}$ ， $3^3 equiv 6 pmod{7}$ ， $3^4 equiv 4 pmod{7}$ ， $3^5 equiv 5 pmod{7}$ ， $3^6 equiv 1 pmod{7}$ ，因此有 $Ord_7(3) = 6 =varphi (7)$ ，所以 3 是模 7 的一个原根。

（2）原根的一些性质

可以证明，如果正整数 $(a,m)=1$ 和正整数 d 满足 $a^d equiv 1 pmod{m}$ ，则 d 整除 $phi (m)$ 。因此 $Ord_m (a)$ 整除 $phi (m)$ 。在例子中，当 $a=3$ 时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。