数论四大定理的证明与部分应用（含算术基本定理）

博客园同步

首先声明：下文中所有的类似”因数“”整数“等的字眼，除特别说明，全部是对于正数而言，不包括负数或者是$0$。

Case 1. 欧拉定理

欧拉定理即：

对于 $p$ 为素数，$a$ 为任意正整数，存在

$a^{\varphi_p} \equiv 1 \pmod p$

其中 $\gcd(a,p)=1$.

说明： $\varphi_p$ 为 $\leq p$ 的数中与 $p$ 互质的数的个数。

证：

令

$S = \varphi_p$

构造数列：

$X_1,X_2 \cdots X_S$

满足对于 $1 \leq i \leq S$ 有：

$\gcd(X_i,p)=1$

显然存在这样的构造。

下面，由：

$\gcd(X_i,p)=1$

$\gcd(a,p)=1$

可得

$\gcd(X_i \cdot a , p)=1$

即

$\prod_{i=1}^S X_i \equiv \prod_{i=1}^S X_i \cdot a \pmod p$

下面证明另一个定理。

---

证 $1$.

定理 $1$.

对于

$a \equiv b \pmod p$

且 $\gcd(c,p)=1$

则：

$\frac{a}{c} \equiv \frac{b}{c} \pmod p$

这是因为除以$c$不会影响对$p$的取模。

---

回到原证，可得：

$\prod_{i=1}^S a \equiv 1 \pmod p$

代入 $S = \varphi_p$

即为：

$a^{\varphi_p} \equiv 1 \pmod p$

得证。

Case 2. 费马小定理

费马小定理即：对于 $p$ 为素数， $a$ 为正整数，有：

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

其中 $\gcd(a,p)=1$.

首先，我们有欧拉定理：

$a^{\varphi_p} \equiv 1 \pmod p$

当 $p$ 为质数，显然 $\varphi_p = p-1$ ，则：

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

得证。

Case 3. 威尔逊定理

威尔逊定理即：对于 $p$ 为素数，有：

$(p-1)! \equiv -1 \pmod p$

---

证 $1$.

定理 $2$：

对于质数 $p$ ，在 $2 - (p-2)$ 中不存在任何一个数自己是自己的逆元。

反证：若存在，设为 $a$. 即：

$a^2 \equiv 1 \pmod p$

$a^2-1 \equiv 0 \pmod p$

$(a-1)(a+1) \equiv 0 \pmod p$

必然存在 $a-1=0$ 或 $a+1=p$

则：

$a=1$ 或 $a=p-1$

所以，在 $2 - (p-2)$ 中不存在任何一个数自己是自己的逆元。

得证。

证 $2$.

定理 $2$ ：

$a$ 是 $b$ 的逆元 和 $b$ 是 $a$ 的逆元这两句话，必然同时成立或同时不成立。

反证：若其中一个成立，另一个不成立。必然有：

$ab \equiv 1 \pmod p$

此时两个都成立。矛盾。

得证。

证 $3$.

定理 $3$：

对于 $p$ 为质数且 $p>2$，可以将 $2 - (p-2)$ 的数两两分为一组，满足每组的两个数互为逆元。

显然，由定理 $1$ 和 定理 $2$ 可知 逆元的一一配对性。

得证。

---

下面回到原证。

根据定理 $3$ ，直接分为 $S$ 组，并将第 $i$ 组的第一个称为 $a_i$ ，第二个称为 $b_i$.

此时：

$(p-1)! \equiv \prod_{i=2}^{p-2} i \cdot (p-1) \equiv \prod_{i=1}^S ( a_i \cdot b_i ) \cdot (p-1) \equiv ( \prod_{i=1}^S 1 ) \cdot (p-1) \equiv (p-1) \equiv -1 \pmod p$

得证。

Case 4. 孙子定理

孙子定理（也称中国剩余定理）即：

对于：

$S= \begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \\ x \equiv a_n \pmod {m_n} \end{cases}$

且 $m_i$ 两两互质，此时：

$S$ 必然有解，并且在 $\prod_{i=1}^n m_i$ 中只有一个解。（对于任意的 $a_i$）

Case 4.1 证明存在性

构造法：

令

$M = \prod_{i=1}^n m_i$

$M_i = \frac{M}{m_i}$

$t_i \cdot M_i \equiv 1 \pmod m_i$

（即 $t_i$ 为 $M_i$ 关于 $m_i$ 的逆元。

此时 $S$ 的 解 $x$ 满足：

$x\equiv \sum_{i=1}^n a_i \cdot t_i \cdot M_i \pmod M$

如何说明该解成立？

对于任何一组方程 $x \equiv a_i \pmod m_i$

除了 $a_i \cdot M_i \cdot t_i$ 这一项满足：

$a_i \cdot M_i \cdot t_i \equiv a_i \pmod m_i$

其余项均有：

$a_j \cdot M_j \cdot t_j \equiv 0 \pmod m_i$

这是因为，$j \not = {i}$ 时，必然 $M_j \equiv 0 \pmod m_i$.

所以其它项对 $m_i$ 的取模没有影响，满足该式。

进而 $S$ 被满足。

Case 4.2 证明唯一性

由于：

$x\equiv \sum_{i=1}^n a_i \cdot t_i \cdot M_i \pmod M$

所以，如果存在两个数 $x_1$ ，$x_2$ 均满足上式，且均 $<M$（其中$x_1 > x_2$

必然有：

$x_1 - x_2 \equiv 0 \pmod M$

由于 $x_1,x_2 < M$ ，所以 $x_1 - x_2 < M$.

再由上述可知

$x_1 = x_2$

由此“存在两个数”的假设矛盾。

得证。

Case 5. 应用

Case 5.1 欧拉定理与费马小定理

可以发现，费马小定理是欧拉定理的一种特殊情况。

如果求 $a$ 关于 $p$ 的逆元且 $p$ 为质数，由费马小定理有：

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

得出：

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

所以 $a$ 关于 $p$ 的逆元即为 $a^{p-2}$.

用快速幂计算，可以达到单次查询 $O(\log p)$ 的时间复杂度。

Case 5.2 威尔逊定理

当我们求 $(n-1)! \bmod n$ 时：（$n>1$）

如果 $n$ 为质数，由威尔逊定理得答案为 $n-2$.

如果 $n$ 为合数，先证明算术基本定理（或称唯一分解定理）：

---

证 $1$.

定理 $1$.

大于1的自然数必可写成质数的乘积。

反证：若存在一些不可写成质数乘积的数，设其其中最小的为 $n$.

首先 $n>1$ ，那么 $n$ 只会是质数或者合数。

如果 $n$ 是质数，那么 $n=n$ 就是质数的乘积形式。

否则，$n$ 必然是合数，存在 $a \times b = n$ 且 $a,b <n$.

由于 $n$ 是不满足该性质“最小”的数，所以 $a$ 与 $b$ 均满足，均可表示为质数的乘积；那么 $n$ 也可以被表示为质数的乘积。矛盾。

得证。

---

我们回到原证：

$n$ 为合数，将 $n$ 质因数分解，则其标准分解式为：

$n=\prod_{i=1}^k {p_i}^{a_i}$

其中 $p_i$ 为质数， $a_i$ 为正整数。

由于算术基本定理，存在这样的分解。下面将 $p_i$ 取出，也就是 $n$ 的所有质因子为：

$p_1,p_2 \cdots p_k$

其中对于 $1 \leq i < k$ ，有 $p_i < p_{i+1}$

那么，$p_k$ 也就是 $n$ 最大质因子必然 $<(n-1)$.

这是因为 $n-1 | n$ 当 $n>2$ 时恒不成立。

也就是说，对于 $1 \leq i \leq k$ ，都存在:

$p_i < n-1$

也就是说， $(n-1)!$ 中包含 $n$ 的所有质因子。

---

证 $2$.

定理 $2$ ：

如果一个数 $n$ 的所有质因子的指数都比另一个数 $a$ 的小（或等于）。此时可以得出：

$n | a$

这是显然的一个定理，只需说明，不必证明。

证 $3$.

推论 $3$ ：（其中 $n$ 为合数）

$n | (n-1)!$

由定理 $2$ 推论：

假设 $n$ 有质因子 $p$ ，则其个数最多为 ${\log}_p n$.

而在 $(n-1)!$ 中，则有：

$\sum_{p|i}^{n-p} {\log}_p i$

很显然，这是多于 $n$ 的个数（也有可能等于）。读者可以自证。

由于 $n$ 是合数，显然 $n \geq 4$.

但是，对于 $n=4$ 的合数情况，不满足 $4 | 3!$，所以应当特殊判断之。

而 $3! \bmod 4 = 6 \bmod 4 = 2 $.

---

回到原证，由定理 $3$ 可知：

$n | (n-1)!$

这可以说明：

$(n-1)! \bmod n = 0$

所以最终结论为：

求 $(n-1)! \bmod n$ 的值（$n>1$）：

如果 $n$ 为质数，那么答案为 $n-1$.

否则 $n$ 为合数，那么当 $n=4$ 时答案为 $2$ ，否则为 $0$.

Case 5.3 算术基本定理（唯一分解定理）

算术基本定理上面已经证毕。而其应用就在于：

可以将一个 $>1$ 的 合数 表达为若干个质数的乘积。其应用广泛，若

$n=\prod_{i=1}^k {p_i}^{a_i}$

（其中 $p_i$ 为质数，$a_i$ 为正整数）

则具有以下的应用：

1.求 $n$ 的因数个数。此时由组合可以得到，$n$ 的因数个数为 $\prod_{i=1}^k (a_i+1)$.

1. 求 $n$ 的因数之和。此时仍然由组合可以得到，$n$ 的因数之和为 $\prod_{i=1}^k \sum_{j=0}^{a_i} (p_i)^j$

2. 可以重新定义 $\gcd(a,b)$ 和 $\operatorname{lcm}(a,b)$.也可以证明 $\gcd(a,b) \cdots \operatorname{lcm}(a,b)=a \times b$.

---

证 $1$.

定理 $1$.

$\gcd(a,b) \cdots \operatorname{lcm}(a,b)=a \times b$

首先，将 $a$ 和 $b$ 质因数分解为：

$a=\prod_{i=1}^k {p_i}^{a1_i}$

$b=\prod_{i=1}^k {p_i}^{a2_i}$

（其中 $p_i$ 为质数，$a1_i$ 与 $a2_i$ 为自然数。即如果两个数中只有一个数是该质数的倍数，那么另一个数中该质数对应的指数就是 $0$ ）

由质因数分解可以得到：

$\gcd(a,b) = \prod_{i=1}^k {p_i}^{\min(a1_i,a2_i)}$

$\operatorname{lcm}(a,b) = \prod_{i=1}^k {p_i}^{\min(a1_i,a2_i)}$

由于：

$\min(a,b)+\max(a,b)=a+b$

所以可以得到：

$\gcd(a,b) \cdot \operatorname{lcm}(a,b) = \prod_{i=1}^k ({p_i}^{\min(a1_i,a2_i)} \times {p_i}^{\min(a1_i,a2_i)}) = \prod_{i=1}^k {p_i}^{a1_i+a2_i}$

而：

$a \times b = \prod_{i=1}^k {p_i}^{a1_i+a2_i}$.

于是可以得到

$\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a\times b$

得证。

---

4. 由此可以证明 $\sqrt{2}$ 是无理数。

---

证 $1$.

定理 $1$.

$\sqrt{2}$ 是无理数。

反证：如果 $\sqrt{2}$ 是有理数，则其可以表示为：

$\sqrt{2}=\frac{a}{b}$

其中 $\gcd(a,b)=1$

于是我们可以得到：

$a^2 = 2b^2$

那么 $2 | a^2$，根据完全平方数的性质，存在 $2 | a$.

另：如果 $2 | a$ 不成立 则 $2 | a^2$ 也不成立。矛盾。

由于 $2 | a$ ，可以得到 $4 | a^2$ ，进而：

$4 | 2b^2$，即 $2 | b^2$.同理可知 $2 | b$.

此时： $2 | \gcd(a,b)$. 与之前我们假设的 $\gcd(a,b)=1$ 矛盾。

得证。

---

由此可以扩展为：

$\sqrt{k}$ 是无理数当且仅当 $k$ 不是完全平方数。

5. 证明素数个数无限。

---

证 $1$.

定理 $1$. 素数个数无限。

反证：假设有限，为 $k$ 个，且这些质数为：

$p_1,p_2 \cdots p_k$

那么考虑

$(\prod_{i=1}^k p_i )+1$

该数不会被 $p_i$ 的任何一个数筛掉。 （$1 \leq i \leq k$）

所以这个数也是质数，并且这个数大于当前所有的质数。

那么，这与我们先前假设的“质数是有限个”是矛盾的。因为用这种方法可以不断加入新的质数并不断计算乘积、再加入新的质数。

得证。

---

当然还有一些更高级的应用，这里就不再赘述。

Case 5.4 孙子定理

孙子定理（即中国剩余定理）可以求：

$S= \begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \\ x \equiv a_n \pmod {m_n} \end{cases}$

其中$S$方程的解 $x \bmod (\prod_{i=1}^n m_i)$.

由此可以求出 满足 $S$ 的最小的 $x$.

当然，可以求出第 $k$ 小。

这在数学域、计算机域都有极大的应用，可以将多个同余方程式合并为一个同余方程式，在解方程组时提供了极大的便利。

转载：https://blog.csdn.net/bifanwen/article/details/105892823