指数

定义

• 指数

  设$m>1$为整数，$a$是与$m$互素的正整数，则使得$a^e\equiv1\left(\mod m\right)$成立的最小正整数$e$叫做$a$对模$m$的指数，记作$\mathrm{ord}_{m}{\left(a\right)}$

• 原根

  若$e=\varphi{\left(m\right)}$，则$a$为模$m$的原根

定理

• $a^d\equiv1\left(\mod m\right)\Longleftrightarrow\mathrm{ord}_{m}{\left(a\right)}\mid d$

• 设$p$为奇素数，$\frac{p-1}{2}$为素数，若$a\not\equiv0,1,-1\left(\mod p\right)$，则$\mathrm{ord}_{p}{\left(a\right)}=\frac{p-1}{2}$或$p-1$

• $b\equiv a\left(\mod m\right)\Longrightarrow \mathrm{ord}_{m}{\left(b\right)}=\mathrm{ord}_{m}{\left(a\right)}$

• $a^{-1}a\equiv1\left(\mod m\right)\Longrightarrow \mathrm{ord}_{m}{\left(a^{-1}\right)}=\mathrm{ord}_{m}{\left(a\right)}$

• $1=a^0,a,\cdots,a^{\mathrm{ord}_{m}{\left(a\right)}-1}$

• $a^d\equiv a^k\left(\mod m\right)\Longleftrightarrow d\equiv k\left(\mod \mathrm{ord}_{m}{\left(a\right)}\right)$

• $\mathrm{ord}_{m}{\left(a^d\right)}=\frac{\mathrm{ord}_{m}{\left(a\right)}}{\left(d,\mathrm{ord}_{m}{\left(a\right)}\right)}$

• 设$g$为模$m$的原根，则$g^d$为模$m$的原根$\Longleftrightarrow \left(d,\varphi{\left(m\right)}\right)=1$

• 设$k\mid \mathrm{ord}_{m}{\left(a\right)}$，则使得$\mathrm{ord}_{m}{\left(a^d\right)}=k,1\leq d\leq \mathrm{ord}_{m}{\left(a\right)}$成立的正整数$d$满足$\frac{\mathrm{ord}_{m}{\left(a\right)}}{k}\mid d$，且共有$\varphi{\left(k\right)}$个这样的$d$

• 模$m$有原根$\Longrightarrow$模$m$有$\varphi{\left(\varphi{\left(m\right)}\right)}$个不同的原根

• $\left(\mathrm{ord}_{m}{\left(a\right)},\mathrm{ord}_{m}{\left(b\right)}\right)=1\Longleftrightarrow \mathrm{ord}_{m}{\left(a\cdot b\right)}=\mathrm{ord}_{m}{\left(a\right)}\cdot \mathrm{ord}_{m}{\left(b\right)}$

求指数

根据$a^d\equiv1\left(\mod m\right)\Longleftrightarrow\mathrm{ord}_{m}{\left(a\right)}\mid d$，求出$m$的因数，挨个验证