阶（multiplicative order）
( extbf{Def.})：(delta_m(a)) 为最小的 (n) 使得 (a^nequiv 1pmod m)，其中 ((a,m)=1)。
Observation 1：(oxed{a^0 otequiv a^1 otequivdots otequiv a^{delta_m(a)-1}pmod m})。
( extbf{Proof})：若 (exists i,j,s.t.0leqslant i<j<delta_m(a),a^iequiv a^jpmod m)，则 (a^{i-j}equiv 1pmod m)，又 (i-j<delta_m(a))，矛盾。
(lacksquare)
Observation 2：(oxed{delta_m(a)midvarphi(m)})。
( extbf{Proof})：由欧拉定理： (a^{varphi(m)}equiv 1pmod m)，因为 (1^x=1)，所以如果存在 (x_0) 使得 (a^{x_0}equiv 1pmod m)，那么 (x_0) 倍数也一定可以，也就是说存在周期性，所以 (delta_m(a)midvarphi(m))。BTW，同时也有若 (a^nequiv 1pmod m)，则 (delta_m(a)mid n)。
(lacksquare)
顺便可以知道若 (a^pequiv a^qpmod m)，则 (pequiv qpmod{delta_m(a)})。
Lemma 1：设 (minmathbb{N}^*)，(a,binmathbb{Z})，((a,m)=(b,m)=1)，则 (oxed{delta_m(ab)=delta_m(a)delta_m(b)}) 的重要条件是 ((delta_m(a),delta_m(b))=1)。
( extbf{Proof})：略，具体见此处。
Lemma 2：设 (kinmathbb{N})，(minmathbb{N}^*)，(ainmathbb{Z})，((a,m)=1)，则 (oxed{delta_m(a^k)=frac{delta_m(a)}{(delta_m(a),k)}})。
( extbf{Proof})：略，具体见此处。
原根（primitive root）
( extbf{Def.})：对于 ((a,m)=1)，若 (delta_m(a)=varphi(m))，则称 (a) 是模 (m) 的原根。
Lemma 1（判定定理）：设 (mgeqslant3)，((a,m)=1)，则 (a) 为模 (m) 的原根当且仅当 (oxed{forall pinmathbb{P},pmidvarphi(m),a^{frac{varphi(m)}{p}} otequiv1pmod m})。
( extbf{Proof})：必要性显然，充分性证明见此处。
Lemma 2（数量定理）：若 (m) 存在原根，则其原根数量为 (oxed{varphi(varphi(m))})。
( extbf{Proof})：略，具体见此处。
Lemma 3（存在定理）：(m) 存在原根当且仅当 (oxed{m=2,4,p^alpha,2p^alpha})，其中 (p) 为奇素数，(ainmathbb{N}^*)。
( extbf{Proof})：略，具体见此处。
若 (m) 存在原根，则最小原根 (leqslant m^frac{1}{4})。