阶与原根

仅包含基础知识以及部分感性理解，不包括严谨证明。OI_Wiki。

阶与原根

阶

我们知道 \((a,m)=1\) 时，\(a^p\) 是有循环节 \(\varphi(m)\) 的，但是我们更好奇最小循环节是多少，于是我们称它为阶 \(\delta_m(a)\)。你考虑感性理解这个东西其实就是一个简单环。

这里补充一句，当 \((a,m)\not=1\) 时，\(a^p\) 当然也有循环节，但是不是那种“纯”循环节。举例来说，\(1\) 肯定不会在这个循环当中出现。我们不作研究。

性质

\(a,a^2\dots,a^{\delta_m(a)}\) 两两不同余。

显然环上没有相同元素。

若 \(a^n\equiv1(\text{mod}\ m)\)，则 \(\delta_m(a)|n\)。

你想遍历整个环一定走了若干整数圈。

若 \((a,m)=(b,m)=1\)，则 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\) 等价于 \(\gcd(\delta_m(a),\delta_m(b))=1\)。

在两个环上同时跑。

\((a,m)=1\)，则 \(\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}\)。

本来有一个环，现在你一次跨 \(k\) 步，你想回到起点就需要走这么多次。

原根

我们发现，对于一组 \((a,m)\)，\(a^p\) 不一定能生成所有 \(0\dots m-1\) 的数，这很不好，所以我们好奇那些能生成所有数的数。

这样的数就叫原根，即，使 \(\delta_m(g)=\varphi(m)\) 的 \(g\)。

性质

判定定理：\(g\) 是模 \(m\) 的原根充要条件是 \(\forall_{p|\varphi(m),p\in Prime},g^{\frac{\varphi(m)}{p}}\not\equiv1(\text{mod}\ m)\)。

必要显然。充分性可以通过说明任意一个不是原根的数的阶是 \(\varphi(m)\) 的约数直接得到。

原根个数：若有，为 \(\varphi(\varphi(m))\)。

显然 \(g^k\ (\gcd(k,\varphi(m))=1)\) 都满足要求。记得证一下别的不行。

存在定理：有且只有 \(2,4,p^{\alpha},2p^{\alpha}\) 存在原根，\(p\) 为奇素数。

最小原根量级：\(O(m^{0.25})\)。

记下来吧 /ch。