$n$的原根的个数为$ϕ(ϕ(n))$

hbghlyj

一般地,$n$的原根的个数为$ϕ(ϕ(n))$,这个如何证明呢

Czhang271828

hbghlyj 发表于 2022-6-15 22:49
一般地,$n$的原根的个数为$ϕ(ϕ(n))$,这个如何证明呢

如此贴所言, 计算群 $(\mathbb Z_n,+)$ 中可逆元导出的乘法群 $(\mathbb Z_n^\ast,\cdot)$ 即可, 该群同构于某一 $\varphi(n)$ 阶的 Abel 群 (计算方式见链接中帖). 原根即 $(\mathbb Z_n^\ast,\cdot)$ 中的生成元, 从而数量 (若存在, 即 $(\mathbb Z_n^\ast,\cdot)$ 同构于循环群) 为 $\varphi(\varphi(n))$.