阶(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}$。