前置知识欧拉, 欧拉定理, 模反元素(模逆元) 可参见: RSA加密

阶

由欧拉定理可知，若 $n,a$ 为正整数，且 $n,a$ 互素（即 $\gcd(a,n)=1$ ），则

$a^{\varphi(n)}\equiv 1\pmod n$

因此满足同余式

$a^m\equiv 1\pmod n$

的最小正整数 $m$ 存在，这个 $m$ 称作 $a$ 模 $n$ 的阶，记作 $\delta(n,a)$ 。

原根

若 $n,a$ 为正整数，且 $n,a$ 互质，如果 $\gcd(a,n)=1$ 且 $\delta(n,a)=\varphi(n)$ ，则称 $a$ 为模 $n$ 的原根。
简单来说，使该式成立的 $d$ 可能有很多个值，又由欧拉定理可知 $\delta(n,a)=\varphi(n)$ 一定是满足的，如果此时所有 $\delta(n,a)$ 的可能取值中 $\varphi(n)$ 是最小的，那么就称 $a$ 为模 $n$ 的原根。

eg:

$a=3,\ n=7$
可知 $3,7$ 互质，所以

$\varphi(n)=7-1=6$

可得

$3^6\equiv 1\pmod 7$

计算 $3^1,3^2,3^3,3^4,3^5\pmod 7$ 都不等于 $1$ ，所以 $6$ 为满足

$a^x\equiv 1\pmod n$

的最小正整数。

$\delta(7,3)=6=\varphi(7)$

可得 $3$ 为模 $7$ 的原根。

性质