§ 阶（multiplicative order）

$\textbf{Def.}$：$\delta_m(a)$ 为最小的 $n$ 使得 $a^n\equiv 1\pmod m$，其中 $(a,m)=1$。

Observation 1：$\boxed{a^0\not\equiv a^1\not\equiv\dots\not\equiv a^{\delta_m(a)-1}\pmod m}$。

$\textbf{Proof}$：若 $\exists i,j,s.t.0\leqslant i<j<\delta_m(a),a^i\equiv a^j\pmod m$，则 $a^{i-j}\equiv 1\pmod m$，又 $i-j<\delta_m(a)$，矛盾。

$\blacksquare$

Observation 2：$\boxed{\delta_m(a)\mid\varphi(m)}$。

$\textbf{Proof}$：由欧拉定理： $a^{\varphi(m)}\equiv 1\pmod m$，因为 $1^x=1$，所以如果存在 $x_0$ 使得 $a^{x_0}\equiv 1\pmod m$，那么 $x_0$ 倍数也一定可以，也就是说存在周期性，所以 $\delta_m(a)\mid\varphi(m)$。BTW，同时也有若 $a^n\equiv 1\pmod m$，则 $\delta_m(a)\mid n$。

$\blacksquare$

顺便可以知道若 $a^p\equiv a^q\pmod m$，则 $p\equiv q\pmod{\delta_m(a)}$。

Lemma 1：设 $m\in\mathbb{N}^*$，$a,b\in\mathbb{Z}$，$(a,m)=(b,m)=1$，则 $\boxed{\delta_m(ab)=\delta_m(a)\delta_m(b)}$ 的重要条件是 $(\delta_m(a),\delta_m(b))=1$。

$\textbf{Proof}$：略，具体见此处。

Lemma 2：设 $k\in\mathbb{N}$，$m\in\mathbb{N}^*$，$a\in\mathbb{Z}$，$(a,m)=1$，则 $\boxed{\delta_m(a^k)=\frac{\delta_m(a)}{(\delta_m(a),k)}}$。

$\textbf{Proof}$：略，具体见此处。

§ 原根（primitive root）

$\textbf{Def.}$：对于 $(a,m)=1$，若 $\delta_m(a)=\varphi(m)$，则称 $a$ 是模 $m$ 的原根。

Lemma 1（判定定理）：设 $m\geqslant3$，$(a,m)=1$，则 $a$ 为模 $m$ 的原根当且仅当 $\boxed{\forall p\in\mathbb{P},p\mid\varphi(m),a^{\frac{\varphi(m)}{p}}\not\equiv1\pmod m}$。

$\textbf{Proof}$：必要性显然，充分性证明见此处。

Lemma 2（数量定理）：若 $m$ 存在原根，则其原根数量为 $\boxed{\varphi(\varphi(m))}$。

$\textbf{Proof}$：略，具体见此处。

Lemma 3（存在定理）：$m$ 存在原根当且仅当 $\boxed{m=2,4,p^\alpha,2p^\alpha}$，其中 $p$ 为奇素数，$a\in\mathbb{N}^*$。

$\textbf{Proof}$：略，具体见此处。

若 $m$ 存在原根，则最小原根 $\leqslant m^\frac{1}{4}$。