数论进阶

原根与阶

阶

若 \(a,p\) 互质，定义 \(a\) 在模 \(p\) 意义下的阶为最小的正整数 \(t\) 满足 \(a^t \mod p =1\)。

\(a\) 在模 \(p\) 意义下的阶记作 \(ord_p(a)\)，\(a^{ord_p(a)} \mod p =1\)。

对于整数 \(k\)，\(a^k \equiv 1(\mod p)\) 当且仅当 \(ord_p(a)|k\)。

• 计算

• 拉格朗日定理

  对于一个 \(n\) 次多项式，其在模质数 \(p\) 的意义下至多有 \(n\) 个根。

\(a^t \equiv b(\mod p)\) 的一个必要条件是 \(ord_p(b)|ord_p(a)\)。

原根

对于自然数 \(p\) 和整数 \(a\)，如果 $\gcd(a,p) =1 $ 且 \(ord_p(a)=\phi(p)\)，则称 \(a\) 为模 \(p\) 意义下的原根。

所有的质数都存在原根。