小学一波数论

费马小定理

若 $p$ 为素数，$\gcd(a, p) = 1$，则 $a^{p - 1} \equiv 1 \pmod{p}$。

另一个形式：对于任意整数 $a$，有 $a^p \equiv a \pmod{p}$。

证明

设一个质数为 $p$，我们取一个不为 $p$ 倍数的数 $a$。

构造一个序列：$A={1,2,3\dots,p-1}$，这个序列有着这样一个性质：

$$
\prod_{i=1}^{n}\space A_i\equiv\prod_{i=1}^{n} (A_i\times a) \pmod p
$$

证明：

$$
\because gcd(A_i,p)=1,gcd(A_i\times a,p)=1
$$

又因为每一个 $A_i\times a \pmod p$ 都是独一无二的，且 $A_i\times a \pmod p < p$

得证（每一个 $A_i\times a$ 都对应了一个 $A_i$)

设 $f=(p-1)!$, 则 $f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p$

$$
a^{p-1}\times f \equiv f \pmod p \ a^{p-1} \equiv 1 \pmod p
$$

证毕。

欧拉定理

欧拉定理实际上就是费马小定理的推广，欧拉定理的内容如下。

若 $\gcd(a, m) = 1$，则 $a^{\varphi(m)} \equiv 1 \pmod{m}$。

至于这个证明么，有点复杂，不细讲了（实则也不会）。可以说，费马小定理撑起了很多东西，比如我们经常算的逆元，或者是经典非对称加密 RSA 都有用到费马小定理。

逆元

这个概念是抽象代数里面的，定义代数中的二元运算 * 和有限集 G ，若 $a*b∈G(a∈G,b∈G)$ 则，群 $<G,*>$ 是一个关系代数。

代数中，有一个很重要的概念就是幺元 ，幺元是指与任意数进行关系运算结果都等于那个数，比如在加法运算中，0就是幺元，因为0加任何数都等于任何数嘛。在乘法中，1就是幺元，同样1乘任何数也等于任何数。而逆元就是说两个数相互进行关系运算之后得到幺元，那么这两个数就互称为对方的逆元。

而我们平时算法竞赛研究的代数体系通常是乘法取模运算，它其实跟乘法类似，就多个取模，取模也限定了它集合的有限性。在乘法模运算中，我们不难发现1是幺元。所以若 $b$ 是 $a$ 在模 $m$ 意义下的逆元，则有 $a\times b \equiv 1 \pmod p$。而这个1我们稍微用一下费马小定理，把它变成 $a^{p-1}$，那么整个式子就变成了 $b\equiv a^{p-2}\ (mod\ p)$。我们就能已知其中一个数算出另一个数的逆元了，至于幂运算可以使用快速幂解决，那么我们算一个数的逆元的复杂度就是 $O(log_2p)$ 了。