原根学习小记

2019-04-14 17:24发布生成海报

站内文章 / 模拟电子

13450 0

（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 的余数即可。