階

稱最小的正整數\(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))\)種

4. 應用