阶
称最小的正整数\(k\)，使得\(a^k\equiv 1\pmod m\)为\(a\)在膜\(m\)意义下的阶。
\(a\)在膜\(m\)意义下有阶的充要条件是\(gcd(a,m)=1\),必要性由裴蜀定理得出，充分性由欧拉定理给出
阶可以通俗的理解为膜意义下幂的最小循环节，根据欧拉定理，这个上界是\(\phi(m)\)
原根
1. 定义
若\(g\)的阶为\(\phi(m)\),即取到上界，则称\(g\)为\(m\)的原根
2. 存在条件
有且仅有\(2,4,p^c,2p^c\)有原根，其中\(p\)表示奇素数
3. 性质
-
\(g^0,g^1,\cdots ,g^{\phi (m)-1}\)两两不相同
证明：反证法，若存在，则能推出\(g\)的阶小于\(\phi(m)\),矛盾
-
\(g^0,g^1,\cdots ,g^{\phi (m)-1}\)恰好取遍\([1,m]\)中所有与\(m\)互质的数
证明：由于\(g\)与\(m\)互质，那么\(g^0,g^1,\cdots ,g^{\phi (m)-1}\)都与\(m\)互质，而与\(m\)互质的数恰有\(\phi(m)\)个，因此得证
-
若\(m\)存在原根，则原根数为\(\phi(\phi(m))\)
设\(m\)的一个原根为\(g\)，那么所有\(m\)的原根都可以表示为\(g^k\)的形式，因为原根必定与\(m\)互质。
考虑\(g^k\)的阶如何表示，即最小的正整数\(x\)使得\(\phi(m)|kx\),那么有 \(\frac{\phi(m)}{gcd(\phi(m),k)}|x\)
即\(g^k\)的阶为\(\frac{\phi(m)}{gcd(\phi(m),k)}\)
由此推出，若\(g^k\)为原根，那么\(gcd(\phi(m),k)=1\),也就是说所有满足条件的\(k\)恰为与\(\phi(m)\)的\(k\)，自然，\(k\)一共有\(\phi(\phi(m))\)种