|
|
order of an element
模 p 的原根 正整数 $a$ 被称为模 $n$ 的 原根，如果 $\gcd(a, n) = 1$ 并且 $\text{ord}_{ n }(a) = \phi (n)$。证明模 $p$ 存在原根（其中 $p$ 是素数）的过程涉及计算模 $p$ 的各种阶的元素。以下是大纲。
步骤 1: 证明一个关于系数在 $ {\mathbb Z}_p$ 中的多项式的 除法算法 的版本。即，给定两个系数在 $ {\mathbb Z}_p$ 中的多项式 $ a(x) $ 和 $ b(x) $，我们可以写成 $ a(x) = b(x)q(x)+r(x) $，其中 $ q(x) $ 和 $ r(x) $ 是一些多项式，并且 $ r(x) = 0 $ 或 deg $ r(x) < $ deg $ b(x) $。
步骤 2: 使用步骤 1 来证明一个度为 $ d $ 的多项式在模 $ p $ 下最多有 $ d $ 个根：如果 $ a $ 是 $ f(x) $ 的一个根，写成 $ f(x) = (x-a)q(x)+r(x) $ 并在 $ a $ 处求值以证明 $ r(x) = 0 $。对 $ f(x) $ 的次数进行归纳。注意，我们在一个微妙的地方使用了 $ p $ 是素数：即，如果 $ f(b) \equiv 0 \pmod p $，那么 $ (b-a)q(b) \equiv 0 \pmod p $，所以要么 $ b\equiv a $，要么 $ q(b) \equiv 0 $。这个结论在一般的合数模数下是不成立的。例如，$ x^2-1 $ 在模 $ 8 $ 下有四个根。
步骤 3: 假设存在一个阶为 $ d $ 的元素 $ a $，$ d\mid(p-1) $。那么 $ x^d-1 $ 在模 $ p $ 下最多有 $ d $ 个根，通过步骤 2，但另一方面 $ 1,a,a^2,\ldots, a^{d-1} $ 都是不同的根。所以这是整个根集。证明这些根中恰好有 $ \phi(d) $ 个根的阶为 $ d $（因为其他的根阶较小）。
步骤 4: 对于每个 $ d\mid(p-1) $，令 $ \psi(d) $ 为模 $ p $ 下阶为 $ d $ 的元素的数量。步骤 3 表明 $ \psi(d) = 0 $ 或 $ \psi(d) = \phi(d) $。现在每个非零元素模 $ p $ 都有某个阶 $ d\mid(p-1) $，所以 $ \psi(d) $ 的和是 $ p-1 $：$$p-1 = \sum_{d\mid(p-1)} \psi(d) \le \sum_{d\mid(p-1)}\phi(d) = p-1.$$（这个最后的等式在 双射证明 的页面中证明。）所以每个地方都成立等式，所以我们证明了：
令 $ p $ 为一个奇素数。对于每个 $ d\mid(p-1)$，在 $ {\mathbb Z}_p^* $ 中恰好有 $ \phi(d) $ 个阶为 $ d $ 的元素。
特别地，有 $\phi(p-1)$ 个原根。 |
|
