模逆

如果p是一个素数，那么在有限域$\mathbb{Z}/p\mathbb{Z}$中的每一个非零元素都有一个乘法逆，也就是说，存在一个数b满足

$ab \equiv 1 (mod\ p).$$ 我们把b记作$a^{-1}\ mod\ p$. 证明显然由裴蜀定理可得。既然p是素数，上述定理，我们还可以写为：当p是素数，那么$$(\mathbb{Z}/p\mathbb{Z})^* = {1,2,3,4,\dots,p-1}$

也就是说0被从$\mathbb{Z}/p\mathbb{Z}$里面去掉了，并且剩下的元素都是单位元且对乘法封闭。

高次模

对于原根，我们来看这样一个好玩的情况，我们可以尝试，选取以下运算模数都为7\

::: center
$1^1 \equiv 1$ $1^2 \equiv 1$ $1^3 \equiv 1$ $1^4 \equiv 1$ $1^5 \equiv 1$ $1^6 \equiv 1$

$2^1 \equiv 2$ $2^2 \equiv 4$ $2^3 \equiv 1$ $2^4 \equiv 2$ $2^5 \equiv 4$ $2^6 \equiv 1$
$3^1 \equiv 3$ $3^2 \equiv 2$ $3^3 \equiv 6$ $3^4 \equiv 4$ $3^5 \equiv 5$ $3^6 \equiv 1$
$4^1 \equiv 4$ $4^2 \equiv 2$ $4^3 \equiv 1$ $4^4 \equiv 4$ $4^5 \equiv 2$ $4^6 \equiv 1$
$5^1 \equiv 5$ $5^2 \equiv 4$ $5^3 \equiv 6$ $5^4 \equiv 2$ $5^5 \equiv 3$ $5^6 \equiv 1$
$6^1 \equiv 6$ $6^2 \equiv 1$ $6^3 \equiv 6$ $6^4 \equiv 1$ $6^5 \equiv 6$ $6^6 \equiv 1$
:::

这只是1-6，我们可以继续写下去，但是显然我们知道，
7是一个素数，1-6都和他互素，如果a是7的倍数，$a^7 \equiv 0\ (mod\ 7)$
并且我们看到1-6的6次方模7均为1，所以有以下结论： $a^6 \equiv \begin{cases} 1 & (mod\ 7)\ if\ 7\ \nmid a\\ 0 & (mod\ 7)\ if\ 7\ \mid a\\ \end{cases}$ 由此引入费马小定理(Fermat’s little theorem)。

费马小定理

我们取p是一个素数，a为任意整数，于是有 $a^{p-1}\equiv \begin{cases} 1\ (mod\ p)\ if\ p \nmid a\\ 0\ (mod\ p)\ if\ p \mid a\\ \end{cases}$ 下面来看一个美妙的证明！
证明：如果$p \mid a$,那么很显然p的幂都能被a整除，所以我们只需要考虑$p\nmid a$的情况，
我们考虑这样一列数

$a\ ,\ 2a\ ,\ 3a\ ,\ \cdots\ ,\ (p-1)a\ reduced\ modules\ p.$

这里有p-1个数，我们假设他们都是不同的，为了证明他们不同，我们用反证法，先假定$ja\equiv ka\ mod\ p$
也就是说$(j-k)\equiv 0\ mod\ p$,所以p就整除$(j-k)a$,然而我们知道p不能整除a，所以显然p整除$(j-k)$，
但是j和k都是1到p之间的数，相减之后不可能被p整除，所以矛盾，也就是说上述列表中p-1个数都是不同的。
现在来继续往下证明这个定理，我们看到上面一列数，是已经模p之后的，而且还互不相等，在1到p之间，
有趣的是1到p之间本来就只有$p-1$个数，所以上面那一列数只是1到$p-1$的一个排列。\
我们将其乘起来：

$a \cdot 2a \cdot 3a \cdot \cdots \cdot (p-1)a \equiv 1\cdot 2\cdot 3\cdot \cdots \cdot (p-1)a \ (mod\ p)\\$

将其化简，左右两边都可以提出$(p-1)!$，然后从方程两边消去这一项，就变成了

$$a^{p-1} \equiv 1\ (mod\ p)\

$$ 定理证毕！