数论四大定理

四大定理 #

威尔逊定理、欧拉定理、孙子定理（中国剩余定理）、费马小定理并称数论四大定理

威尔逊定理 #

威尔逊定理给出了判定一个自然数是否为素数的充分必要条件

简述为，若一个数(p - 1)！+ 1能被 p 整除，那么 p 为质数，定义

\[ (p - 1)! ≡ -1 \mod p \quad 是 p 为素数的充分必要条件 \]

欧拉定理 #

欧拉函数 \( \varphi(n)\) 定义 #

\[ \forall n \in N_{+}，\varphi(n) = ∣A∣，\text{where }A = \{ m ∣ 1 ≤ m < n, gcd(m, n) = 1 \} 注：∣S∣ 表示集合S元素的个数 \]

给定一个正整数 n，欧拉函数就是求在 \([1, n)\)区间上，与 n 互质的整数的个数，1和任何数都互质

举例来说，设 m = 8，则与 8 互质的正整数集合 A = {1, 3, 5, 7}，此集合共有4个元素，所以 \(\varphi(8) = 4\)

注：\( \varphi 读作 fài \)

欧拉函数性质 #

欧拉函数的定义域与值域有一一对应关系，即已知 m 可以求出唯一的 \( \varphi(m) \)，但是已知 \( \varphi(m) \) 却可能有多个 m 与之对应。如已知 \( \varphi(m) = 4 \)，除了8，结果还可以是其他值，如10(A = {1, 3, 7, 9})，尤其是当 \( \varphi(m) \) 的值很大时，有更多的解

怎么计算\(\varphi(n)\)先分以下情况讨论：

  • n = 1，则 \(\varphi(n) = 1\)，因为1和任何数都互质，当然包含了自身
  • n 是质数，则 \(\varphi(n) = n − 1\)，因为任何一个质数与比自身小的数都只有 1 这个公约数，\([1,n)\) 共有n-1个数，每个数都与n互指
  • \(n = p^k\)，其中 p 为质数, k ≥ 1，则 \( \varphi(p^k) = p^k - p^{k-1} = (p − 1) * p^{k − 1} \)
  • \(n = pq\)，gcd(p,q)=1，则 \(\varphi(n) = \varphi(pq) = \varphi(p)\varphi(q)\)

关于情况3，我们可以简单证明：
由于 p 是质数，所以在 \([1, p^k)\) 中与 \(p^k\) 不互质的数是 p 的倍数，即： \(p, 2p, 3p, ... , p^k - p\)
一共 \( p^{k - 1} - 1 \) 个，所以
\( \varphi(p^k) = p^k - 1 - [p^{k - 1} - 1] = p^k - p^{k - 1} = (p − 1) * p^{k − 1} \)

关于情况4，我们可以简单证明：
由于 p, q 是质数，所以与 p*q 不互质的数只有两种情况：

  • p的整数倍： \(p, 2p, 3p, ... ,(q − 1)p\) 共 q − 1 个；
  • q的整数倍： \(q, 2q, 3q, ... ,(p − 1)q\) 共 p − 1 个；

所以在区间 \([1, pq)\)上，与 p*q 互质的正整数个数为 \( \varphi(pq) = (pq - 1) - (q - 1) - (p - 1) = pq - q - p + 1 = (p - 1)(q - 1) \)

欧拉函数通式 #

\( \varphi(n) = n(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_r)，n = {p_1}^{k_1} {p_2}^{k_2} ... {p_r}^{k_r}，为 n 的质因数分解 \)

如n = 100我们就可以写成 \(100 = 2^2 * 5^2\)，所以 2 和 5 分别是 \(p_1\) 和 \(p_2\)

\(\varphi(100) = 100 * (1 - 1/2) * (1 - 1/5) = 40 \)

即知道质因数分解可以求\( \varphi(n) \)

欧拉定理 #

\[ a^{\varphi(n)} \equiv 1 \mod n 其中，a 与 n 均为正整数，且两者互质 \]

为费马小定理的扩充

中国剩余定理（孙子定理） #

中国剩余定理(Chinese Remainder Theorem)是数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理

明朝数学家程大位在《算法统宗》中将解法编成易于上口的《孙子歌诀》：

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知

形式描述 #

给出了以下的一元线性同余方程组 \(x \equiv a_i \mod m_i 记为(S)\):

\[ \begin{align} x \equiv a_1 & \mod m_1 \\ x \equiv a_2 & \mod m_2 \\ ... \\ x \equiv a_n & \mod m_n \\ \end{align} \]

假设整数 \(m_1, m_2, ... , m_n\) 其中任意两数互质，则对任意的整数：\(a_1, a_2, ... , a_n\)，方程组(S)有解，并且通解可以用如下方式构造得到：

  1. 设 \(M = m_1 * m_2 * ... * m_n\) 是整数 \(m_1, m_2, ... , m_n\) 的乘积，并设 \(M_i = M/m_i\)，即 \(M_i\) 是除了 \(m_i\) 以外的其余 n − 1 个整数的乘积
  2. 设 \(t_i\) 为 \(M_i\) 模 \(m_i\) 的数论倒数：\(t_iM_i \equiv 1 \mod m_i\)，这里可以看出为什么要求\(m_i\)任意两数互质
  3. 方程组 (S) 的通解形式为：\( x = a_1t_1M_1 + a_2t_2M_2 + ... + a_nt_nM_n + kM \)
  4. 在模 M 的意义下，方程组 (S) 只有一个解：\(x = a_1t_1M_1 + a_2t_2M_2 + ... + a_nt_nM_n\)

使用中国剩余定理来求解上面的“物不知数”问题。这里的线性同余方程组 (S) 是：

\[ \begin{align} x \equiv 2 \mod 3 \\ x \equiv 3 \mod 5 \\ x \equiv 2 \mod 7 \\ \end{align} \]

三个模数 \(m_1 = 3, m_2 = 5, m_3 = 7\) 的乘积是 M = 105，对应的 \(M_1 = 35, M_2 = 21, M_3 = 15\)，而可以计算出相应的数论倒数：\(t_1 = 2, t_2 = 1, t_3 = 1\)

\[ \begin{align} 70 = 2 * 35 &\equiv 1 \mod 3 \\ &\equiv 0 \mod 5 \\ &\equiv 0 \mod 7 \\ \\ &\equiv 0 \mod 3 \\ 21 = 1 * 21 &\equiv 1 \mod 5 \\ &\equiv 0 \mod 7 \\ \\ &\equiv 0 \mod 3 \\ &\equiv 0 \mod 5 \\ 15 = 1 * 15 &\equiv 1 \mod 7 \\ \end{align} \]

所以《孙子歌诀》中的 70、21 和 15 其实是这个“物不知数”问题的基础解

而将原方程组中的余数相应地乘到这三个基础解上（\(a_i*t_iM_i\)），再加起来，其和就是原方程组的解：

\[ \begin{align} \equiv 2 * 1 + 3 * 0 + 2 * 0 \equiv 2 \mod 3 \\ 2 * 70 + 3 * 21 + 2 * 15 \equiv 2 * 0 + 3 * 1 + 2 * 0 \equiv 3 \mod 5 \\ \equiv 2 * 0 + 3 * 0 + 2 * 1 \equiv 2 \mod 7 \\ \end{align} \]

这个和是 233，原方程组的通解公式为：\( x = 233 + k * 105 \)

《孙子算经》中实际上给出了最小正整数解，也就是 \(k = -2\) 时的解：\(x = 23\)

从假设可知，\(gcd(m_i, m_j) = 1, i \ne j, 所以 gcd(m_i, M_i) = 1\)

\(gcd(m_i, M_i) = 1\) 说明存在整数\(t_i\) 使得 \(t_iM_i \equiv 1 \mod mi\)，这样的 \(t_i\) 叫做 \(M_i\) 模 \(m_i\) 的数论倒数

观察乘积

\[ \begin{align} a_it_iM_i \equiv a_i * 1 \equiv a_i & \mod m_i \\ a_jt_jM_j \equiv 0 & \mod m_i, i \ne j \\ \end{align} \]

所以 \(x = a_1t_1M_1 + a_2t_2M_2 + ... + a_nt_nM_n\) 满足（即理解为每一项参与贡献满足方程中的一个等式）

\[ x \equiv a_i + 0 \equiv a_i \mod m_i \]

即 x 就是方程组 (S) 的一个解

另外，假设 \(x_1\) 和 \(x_2\) 都是方程组 (S) 的解，那么：

\(x_1 - x_2 \equiv 0 \mod m_i \)，而 \(m_1,m_2, ..., m_n 两两互质\)，这说明 \(M = m_1 * m_2 * ... * m_n 整除 x_1 - x_2\)，所以方程组 (S) 的任何两个解之间必然相差 M 的整数倍，所有形式为：

\[ x = a_1t_1M_1 + a_2t_2M_2 + ... + a_nt_nM_n + kM \]
from libnum import invmod, gcd

# Define the moduli and residues
moduli = [3, 5, 7]
residues = [2, 3, 2]

# Compute the product of the moduli
M = 1
for m in moduli:
    M *= m

# Compute the solution using the CRT
solution = 0
for i in range(len(moduli)):
    mi = M // moduli[i]
    mi_inv = invmod(mi, moduli[i])
    solution += residues[i] * mi * mi_inv

# Reduce the solution modulo M
solution %= M

print(solution)

费马小定理 #

费马小定理给出的是关于素数判定的必要非充分条件。假如 a 是一个整数，p 是一个质数，那么 \(a^p - a\) 是 p 的倍数，可以表示为

\[ a^p \equiv a \mod p \]

进一步，如果 a 不是 p 的倍数即 gcd(a, p) = 1，这个定理也可以写成更加常用的一种形式

\[ a^{p - 1} \equiv 1 \mod p \]

费马小定理是欧拉定理的一个特殊情况，不要求模数为质数，如果 gcd(a, n) = 1，那么

\[ a^{\varphi(n)} \equiv 1 \mod n \]

费马小定理的逆叙述不成立，即假如 \(a^p - a\) 是 p 的倍数，p 不一定是一个质数。例如\(2^341 - 2\) 是 341 的倍数，但\(341 = 11 x 31\)，不是质数。

满足费马小定理的合数被称为费马伪素数，第一个伪素数 341 是萨鲁斯(Sarrus)在1819年发现的，有人已经证明了伪素数的个数是无穷的

Calendar September 11, 2025
Edit Edit this page