计算逆的第二种方式

费马小定理和快速幂算法提供给我们第二种计算模p的逆的方式，即

也就是说这可以代替了扩展欧几里得算法，并且可以再用快速幂算法减少时间复杂度。
我们来看一个例子

::: Example
Example 1. *考虑$m = 15485207$, 用我们的快速幂算法，不难得出

我们并没有得到1，看起来费马小定理对于$m = 15485207$好像不对了。其实并不是，费马小定理告诉我们，
当$m$是素数时我们才会得到1，那么就是说15485207并不是素数。*
:::

我们证明出了m不是一个素数，但是并没有得到它的因子，这就引出了正题：阶。

阶

::: Definition
Definition 1 (阶的定义).
对于任意的素数a，都存在一个a的最小幂指数k使得$a^{k} \equiv 1\ (mod p)$，我们称k为a模p的阶。
:::

::: Proposition
Proposition 2.
设p是一个素数，a是一个正整数且$p\nmid a$.假设$a^n\equiv 1\ (mod p)$.于是a模p的阶一定整除n.
特别地，a的阶整除p-1.
:::

::: proof
Proof.
我们假设a模p的阶为k，所以根据定义$a^k \equiv 1\ (mod p)$，并且k是满足这一幂性质的最小正指数，
我们还有$a^n \equiv 1\ (mod p)$.我们用n除以k得到

但是$r < k$，然而假设k是阶，也就是最小正数指数，这存在矛盾。所以根据定义，r一定是0。因此，$n = kq$，
所以$k \mid n$。 最后，由费马小定理可知，$k \mid p-1$。 ◻
:::

下面引入本章最重要的概念，原根。

原根

::: Theorem
Theorem 3 (Primitive Root Theorem).
我们设p是一个素数，于是存在一个元素$g \in \mathbb{F}_p^$，g的幂能够给出$\mathbb{F}_p^$中的所有元素。
也就是 $$\mathbb{F}_p^ = {1,g,g^2, g^3,\dots,g^{p-2}}$$
有这样性质的元素们称为$\mathbb{F}_p$的原根，或者称为$\mathbb{F}_p^$的生成元。
显然，$\mathbb{F}_p^$中的元素有阶$p-1$。*
:::

为什么上面是$p-2$次方呢，因为p是素数，$p-1$次方为1了，这就形成了循环，所以前$p-2$次方就生成了
$\mathbb{F}_p^*$中所有元素。

::: Example
Example 2. $\mathbb{F}_p$有2作为原根，那么在$\mathbb{F}_p$中

::: center
$2^0 = 1$ $2^1 = 2$ $2^2 = 4$ $2^3 = 8$ $2^4 = 5$

$2^5 = 10$ $2^6 = 9$ $2^7 = 7$ $2^8 = 3$ $2^9 = 6$
:::

因此$\mathbb{F}p$的10个非零元素，都由2的幂模产生，所以2是它的原根。我们看一个反例，2不是
$\mathbb{F}{17}$的原根，因为在$\mathbb{F}_{17}$中，

::: center
$2^0 = 1$ $2^1 = 2$ $2^2 = 4$ $2^3 = 8$ $2^4 = 16$

$2^5 = 15$ $2^6 = 13$ $2^7 = 9$ $2^8 = 1$
:::

我们在拿到全部的16个数之前就回到了1，然而如果2是其原根，应该在$p-1$次方时才才会出现1，提前进入
循环说明其不是原根。
:::

::: Remark
Remark 4.
如果p很大，有限域$\mathbb{F}_p$中有很多原根。原根数量计算公式：$\mathbb{F}_p$中有$\phi(p-1)$个原根，
$\phi$就是欧拉函数。
:::