指数和原根

如果 $(a,m)=1$，则使得下面同余式成立的最小的 d 称为 a 对模 m 的指数（或阶）

$$a^d\equiv 1(modm)$$

记为

$$d=or{d}_m(a)\in [1,\phi (m)]$$

根据 元素的阶 的性质，有

$$d|\phi (m)$$

如果正好 $d=\phi (m)$，则称此时的 a 为模 m 的一个 原根（即群的 生成元）

$$or{d}_m(1)=1$$

原根不一定存在，如对 8 来说，$\phi (8)=4$，此时所有元素的阶都是二，所以没有原根

指数的性质

原根存在的条件