# 指数

## **定义**

* 指数

  设$$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$$的因数，挨个验证