class="markdown_views prism-kimbie-light">

[$frak{Link}$]

---

整数模 n 乘法群 在 $_n$ 群中，根据定义 $|_n|=phi(n)$ 。

---

阶 $a$ 关于 $p$ 的阶 $delta_p(a)$ 是满足 $a^xequiv1pmod{p}$ 的最小的 $x$ 。
也就是 $|<a>|$
同时根据群论拉格朗日定理 $|G|=[G:H]|H|$ 我们有 $|H|||G|$
（群论拉朗易得只需证等价，等价只需证自反对称传递）
那么 $|<a>||phi(p)$ 并且 $a^{|G|}=1$

---

原根 模 $p$ 的原根 $g$ 满足 $delta_p(g)=phi(p)$ 。
$p$ 的所有原根乘起来 $equiv1pmod{p}$
$p$ 的所有原根加起来 $equivmu(p-1)pmod{p}$ 模 $p$ 的原根个数为 $phi(phi(p))$ 。（证明：$|_p|=phi(p)$ 并且生成元个数为 $phi(|_p|)$ ）
（好多地方都写的上面这个证明，但是我实在是没有找到关于 $_p$ 可逆元的说法。。）
（我感觉貌似意思是说原根能生成 $_p$ 然后利用所有原根能互相得到的性质？）
（接着把不能作为生成元的与 $p$ 互质的数 $g^{x'}$ 去掉）
（然后能作为生成元的 $x$ 也就是应该满足 $x$ 的倍数模 $phi(p)$ 能取到所有的 $x$ ）
（这种 $x$ 有 $phi(phi(p))$ 个）
或者也可以利用 $delta_p(g^x)=frac{delta_p(g)}{(x,delta_p(g))}$ 即 $delta_p(g^x)=frac{phi(g)}{(x,phi(g))}$ 且 $g_{other}=g^x$
又 $delta_p(g^x)=phi(p)$ 的时候 $(x,phi(g))=1$ 即有 $phi(phi(g))$ 个 $g^x$ 为原根。得证。
（如果 $g$ 是 $p$ 的原根那么 $g^x$ 是 $p$ 的原根的充要条件为 $(x,phi(p))=1$ $g$ 是模 $p$ 的原根的充要条件为 $g^xpmod{p}$，$x=0,1,cdots,delta_p(g)$ 两两不相等。
也就是 $g^{x}equiv1pmod{p}$ 最小正整数解为 $x=phi(p)$ 有原根的数只有 $1,2,4,p^a,2p^a$ ，其中 $p$ 是奇素数。
模 $p$ 有原根，意味着 $_p$ 是一个循环群。 求原根：唯一分解 $phi(p)=prod{p_i}^{a_i}$ ， 暴枚 $xin[2,p)$
对每个 $x$ 判断 $x^{frac{phi(p)}{p_i}}$