题解。

阶

定义

设 a,m∈N+a,m\in\mathbb{N^+}，且 a⊥ma\perp m，使 ax≡1(modm)a^x\equiv 1\pmod m 成立的最小正整数 xx，称为 aa 模 mm 的阶，记为 ordma\text{ord}_ma。

性质

比较显然的，根据定义直接得到：

an≡1(modm)a^n\equiv 1\pmod m 的充要条件为 ordma∣n\mathrm{ord}_ma|n。

ordma∣φ(m)\mathrm{ord}_ma\mid\varphi(m)，欧拉定理证明。

设 p,q∈Np,q\in\mathbb N，ap≡aq(modm)a^p\equiv a^q\pmod m 的充要条件为 p≡q(modordma)p\equiv q\pmod {\text{ord}_ma}。

ordma=x\text{ord}_ma=x，则 1,a,a2,⋯ ,ax−11,a,a^2,\cdots,a^{x-1}，模 mm 两两不同余。

需要稍微推一下的（其实感性理解还是很容易的）：

设 b∈N+b\in\mathbb N^+，若 ab≡1(modm)ab\equiv1\pmod m，则 ordma=ordmb\text{ord}_ma=\text{ord}_mb。
axbx≡bx≡1a^xb^x\equiv b^x\equiv1，bx=1b^x=1，ayby≡ay≡1a^yb^y\equiv a^y\equiv 1，ax=1a^x=1。

这个比较有用：令 x=ordmax=\text{ord}_ma，有 t∈N+t\in\mathbb N^+ 则 ordmat=xgcd⁡(t,x)\text{ord}_ma^t=\frac{x}{\gcd(t,x)}。

设 w∈N+w\in\mathbb N^+，若 w∣mw\mid m，则 ordwa∣ordma\text{ord}_wa\mid \text{ord}_ma。
用这个：aordma=km+1=xkw+1a^{\mathrm{ord}_ma}=km+1=xkw+1 容易得到。

设 n∈N+n\in\mathbb N^+。若 m⊥n,a⊥nm\bot n,a\bot n，则 ordmna=lcm(ordma,ordna)\text{ord}_{mn}a=\text{lcm}(\text{ord}_{m}a,\text{ord}_{n}a)。

设 b∈N+b\in\mathbb N^+，若 b⊥mb\bot m 且 ordma⊥ordmb\mathrm{ord}_ma\bot \mathrm{ord}_mb，则 ordmab=ordma×ordmb\mathrm{ord}_mab=\mathrm{ord}_ma\times \mathrm{ord}_mb 。

原根

P6091 【模板】原根。

定义

设 g,m∈N+g,m\in\mathbb N^+，且 g⊥mg\bot m，若 ordmg=φ(m)\mathrm{ord}_mg=\varphi(m)，则称 gg 是模 mm 的原根。

原根存在定理

模 m{\displaystyle m} 有原根的充要条件是 m=2,4,pk,2pkm=2,4,p^k,2p^k，其中 pp 是奇素数，kk 是任意正整数。

证明困难。

原根判定定理

若 gg 为模 mm 的原根，则对于任意 φ(m)\varphi(m) 的质因子 pp，必有 gφ(m)p≢1(modm)g^{\frac{\varphi(m)}{p}}\not\equiv 1 \pmod m。

求所有原根

设 gg 为模 mm 的原根，则集合 S={gs∣1≤s≤φ(m),s⊥φ(m)}S=\{g^{s} \mid 1 \leq s \leq \varphi(m),s\bot\varphi(m)\} 给出模 mm 的全部原根。模 mm 的原根有 φ(φ(m))\varphi(\varphi(m)) 个。

最小原根是 m14m^{\frac{1}{4}} 级别的。