数论定理证明 - 洛谷保存站

作者注：因为本人太蒟，有些证明方法是从网上参考的，可能有些东西是伪证，勿喷。

## 欧拉定理（Euler）

若 $a$ 与 $n$ 互质，则有

$$a^{\varphi (n)}\equiv1\pmod n$$

**证明：**

设有正整数 $n$，易得在 $1$ 到 $n$ 中与 $n$ 互质的数有 $\varphi(n)$ 个。不妨令这些数为 $x_1,x_2,x_3\cdot\cdot\cdot x_{\varphi(n)}$。所有数相乘得 $x_1x_2x_3\cdot\cdot\cdot x_{\varphi(n)}$。

将这些数全部乘上 $a$，得到的序列为 $ax_1,ax_2,ax_3...ax_{\varphi(n)}$。所有数相乘得 $ax_1\times ax_2\times ax_3\times\cdot\cdot\cdot\times ax_{\varphi(n)}=a^{\varphi(n)}x_1x_2x_3\cdot\cdot\cdot x_{\varphi(n)}$。

易得这个新序列里的所有数都与 $n$ 互质，结合上面的，所以有

$$a^{\varphi(n)}x_1x_2x_3\cdot\cdot\cdot x_{\varphi(n)}\equiv x_1x_2x_3\cdot\cdot\cdot x_{\varphi(n)}\pmod n$$

根据同余的同乘性，可得

$$a^{\varphi(n)}\equiv1\pmod n$$

证完了。

## 欧拉定理推论

若 $a$ 与 $n$ 互质，则有

$$a^b\equiv a^{b\ \text{mod}\ \varphi(n)}\pmod n$$

**证明：**

当 $\text{gcd}(a,m)=1$ 时，即 $a$ 与 $m$ 互质，根据欧拉定理可得 $a^{\varphi(m)}\equiv1\pmod n$。令 $b=q\times\varphi(m)+r$，其中 $0\le r<\varphi(n)$，即 $r=b\ \text{mod}\ \varphi(m)$，所以 $a^b\equiv a^{q\times\varphi(m)+r}\equiv (a^{\varphi(n)})^q\times a^r\equiv 1^q\times a^r\equiv a^r\equiv a^{b\ \text{mod}\ \varphi(n)}\pmod n$。

证毕。

## 费马小定理（欧拉定理证法）

对于正整数 $a$ 和一个与 $a$ 互质的质数 $p$，总有

$$a^{p-1}\equiv1\pmod p$$

**证明：**

根据欧拉定理，$a^{\varphi (p)}\equiv1\pmod p$，因为 $p$ 是质数，所以 $\varphi(p)=p-1$，因此

$$a^{\varphi (p)}\equiv1\pmod p$$

等价于

$$a^{p-1}\equiv1\pmod p$$

证毕。

## 扩展欧拉定理（exEuler）

对于正整数 $a$，$b$，$m$，有

$$a^b\equiv\begin{cases}
 a^b & b<\varphi(m)\pmod m\\
 a^{b\ \text{mod}\ \varphi(m)+\varphi(m)}& b\ge\varphi(m)\pmod m\\
\end{cases}$$

**证明：**

1. 当 $b<\varphi(m)$ 时，十分显然，无需证明。
2. 当 $b\ge\varphi(m)$ 时：根据唯一分解定理，模数 $m=p_{1}^{c_1}p_{2}^{c_2}p_{3}^{c_3}...p_{k}^{c_k}$，对于每一个素数幂 $p_i^{c_i}$，共两种情况：
-  当 $a$ 与 $p_i$ 互质，根据欧拉定理可得 $a^{\varphi(p_i^{c_i})}\equiv1\pmod {p_i^{c_i}}$。那么令 $b=q\times \varphi(p_i^{c_i})+r$，所以 $a^{q\times \varphi(p_i^{c_i})+r}\equiv (a^{\varphi(p_i^{c_i})})^q\times a^r\equiv a^r\pmod {p_i^{c_i}}$。推广到 $m$，则可写为
  $$a^b\equiv a^{b\ \text{mod}\ \varphi(m)+\varphi(m)}\pmod m$$
-  当 $a$ 与 $p_i$ 不互质，则令 $a=p_i\times t$。当 $b\ge\varphi(p_i^{c_i})\ge c_i$ 时，显然有 $a^b\equiv p_i^b\times t^b\equiv0\pmod {p_i^{c_i}}$。此时 $b\ \text{mod}\ \varphi(p_i^{c_i})+\varphi(p_i^{c_i})\ge\varphi(p_i^{c_i})$，则有 $a^b\equiv a^{b\ \text{mod}\ \varphi(p_i^{c_i})+\varphi(p_i^{c_i})}\pmod {p_i^{c_i}}$。推广到 $m$，则可写为
  $$a^b\equiv a^{b\ \text{mod}\ \varphi(m)+\varphi(m)}\pmod m$$

至此，扩展欧拉定理得证。

## 裴蜀定理（Bézout）

对于任意整数 $a$，$b$，总存在一对整数 $x$，$y$，使得 $ax+by=\text{gcd}(a,b)$。

**证明：**

在欧几里得算法的最后一步，也就是 $b=0$ 时，显然可以使 $x=1$，$y=0$，使得 $ax+by=a=\text{gcd}(a,0)$。

当 $b>0$ 时，则 $\text{gcd}(a,b)=\text{gcd}(b,a\ \text{mod}\ b)$。假设存在一对整数 $x'$，$y'$，满足 $b\times x'+(a\ \text{mod}\ b)\times y'=\text{gcd}(b,a\ \text{mod}\ b)$，因为 $b\times x'+(a\ \text{mod}\ b)\times y'=b\times x'+(a-b\times\lfloor\frac{a}{b}\rfloor)\times y'=ay'+b(x'-\lfloor\frac{a}{b}\rfloor y)$，因此令 $x=y'$，$y=x'-\lfloor\frac{a}{b}\rfloor y$，最终表达式为 $ax+by=\text{gcd}(a,b)$。

根据欧几里得算法的递归过程可知，裴蜀定理成立。

## 中国剩余定理（CRT）

~~也称中国单身狗定理。~~

设 $m_1,m_2,m_3,...,m_n$ 是两两互质的整数，设 $M=\prod\limits_{i=1}^{n}m_i$，$m'_i=\frac{M}{m_i}$，$t_i$ 是线性同余方程 $m_i't_i\equiv1(\text{mod}\ m_i)$ 的一个解，对于任意 $n$ 个整数 $a_1,a_2,a_3,...,a_n$，方程组

$$\begin{cases}
 x\equiv a_1\pmod {m_1}\\
 x\equiv a_1\pmod {m_2}\\
 x\equiv a_1\pmod {m_3}\\
 \cdot\cdot\cdot\\
 x\equiv a_1\pmod {m_n}\\
\end{cases}$$

有整数解，解为 $x=\sum\limits_{i=1}^{n}a_im_i't_i$。

**证明：**

因为 $m'_i=\frac{M}{m_i}$，也就是说对于 $\forall k\ne i$ 都有 $a_im_i't_i\equiv0\pmod {m_k}$。又因为 $a_im_i't_i\equiv a_i\pmod {m_i}$，代入原方程组可得 $x=\sum\limits_{i=1}^{n}a_im_i't_i$。

证毕。

## 威尔逊定理（Wilson）

对于一个质数 $p$，总有 $(p-1)!\equiv-1\pmod p$。

对于这个定理成立的数一定是质数，即“ $p$ 为质数”和威尔逊定理互为充分必要条件。

**证明：**

- 必要性：假设 $p$ 不是质数，则 $p$ 一定可以表示为两个数 $a$ 和 $b$ 的积的形式，其中 $1<a<p-1$，$1<b<p-1$。

把原式变一下：

$$1\times 2\times 3\times\cdot\cdot\cdot\times a\times\cdot\cdot\cdot\times b\times\cdot\cdot\cdot\times(p-2)\times(p-1)\equiv-1(\text{mod}\ p)$$
  
  若 $a\ne b$，那么 $(p-1)!\equiv0\pmod a$，$(p-1)!\equiv0\pmod {b}$，所以 $(p-1)!\equiv0\pmod {a\times b}$，即 $(p-1)!\equiv0\pmod {p}$，与命题矛盾；
  
  若 $a=b$，那么 $(p-1)!\equiv0\pmod a$，所以 $(p-1)!\equiv0\pmod {a^2}$，即 $(p-1)!\equiv0\pmod p$，与命题矛盾。
  
  因此 $p$ 一定是质数。
- 充分性：
  
  当 $p=2$ 时，显然成立。
  
  当 $p>2$ 且 $p$ 为质数时，对于集合 $A\in\{1,2,3,...,p-1\}$ 中 $\forall a\in A$，总会有整数 $x$ 满足 $ax\equiv1\pmod {p}$，即 $x$ 为 $a$ 的逆元。容易发现对于集合内两个不同的元素 $a$，$b$，它们的乘法逆元是不同的，又因为 $a$ 的逆元 $x$ 也在集合中，且当 $a\ne x$ 时，$ax\equiv1\pmod p$。而当 $a=x$ 时，$a^2\equiv1\pmod p$，即 $(a+1)(a-1)\equiv0\pmod p$，所以 $a=1$ 或 $a=p-1$。因此对于 $\forall 2\le i\le p-2$， 在集合中总会有一个数 $j$，使得 $i\times j\equiv1\pmod p$。

所以我们把 $(p-1)!$ 拆了，即 $1\times2\times3\times\cdot\cdot\cdot\times(p-1)$，然后我们就会发现：从 $2$ 到 $p-2$ 的所有数乘起来为 $1$。所以原式就变成了 $1\times (p-1)\equiv1\times(-1)\equiv-1\pmod p$。
  
至此，威尔逊定理得证。

## 卢卡斯定理（Lucas）

对于非负整数 $n$，$m$ 和质数 $p$，有

$$\binom{n}{m}\equiv\binom{n\ \text{mod}\ p}{m\ \text{mod}\ p}\times\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\pmod p$$

**证明：**

对于质数 $p$，根据二项式定理可得 $(1+x)^p=\sum\limits_{k=0}^{p}\binom{p}{k}x^k$，

正在渲染内容...