原根与阶

《原根与阶》¶

原根与阶的定义¶

阶¶

定义

\[ \begin{cases} (g,m)=1\\\\ g^d\equiv 1\pmod m \end{cases} \]

满足上面公式的最小正整数$d_0$被称为$g$模$m$的阶（或者次数），记作$ord_gm=d_0$

欧拉定理： $$ \begin{cases} (g,m)=1\\ g^\phi(m)\equiv 1\pmod m &\phi(m)是m的欧拉函数 \end{cases} $$

推论

$ord_gm \mid \phi(m)$

一个数的原根模$m$的原根一定是$ord_gm$的因数之一

原根¶

定义

如果$g$模$m$的阶恰好是$\phi(m)$，即$m$的欧拉函数，则称$g$为模$m$的一个原根（一个$g$可能有多个原根）

换句话说就是 $$ \begin{cases} (g,m)=1\\ g^d\equiv 1\pmod m \end{cases} $$

满足上面公式的最小正整数$d_0$恰好恰好等于$\phi(m)$的整数$g$，被称为模$m$的原根（之一）

推论

$g$是$m$原根的充要条件是$g,g^2,\cdots,g^{\phi(m)}$构成m的一组缩系

设$g$模$m$的阶是$d$，则$1,g,\cdots,g^{d-1}$模$m$两两不同余

如果$(g,m)=1$，则有 $$ g^r \equiv g^s \pmod m \\Updownarrow \ r \equiv s \pmod {ord_gm} $$

如果$p$为素数，则同余方程$x^k\equiv 1 \pmod p$有$(k,p-1)$个解

素数$p$的原根数量为$\phi(p-1)$