初等数论是数学中最古老且最基础的分支之一，它主要研究整数的性质。而同余方程则是数论研究的核心内容之一，它在现代密码学、计算机科学以及编码理论中扮演着至关重要的角色。从古代的“韩信点兵”问题到现代的RSA加密算法，同余方程的思想贯穿始终。
所谓同余，是指两个整数除以同一个正整数所得的余数相同。若整数 a 和 b 除以正整数 m 所得的余数相同，则称 a 和 b 模 m 同余，记作 a ≡ b (mod m)。同余方程则是求解满足特定同余关系的未知整数。
给定整数 a, b, m (m > 0)，方程 ax ≡ b (mod m) 称为线性同余方程。求解此类方程是理解更复杂数论问题的基础。
中国剩余定理最早见于《孙子算经》中的“物不知数”问题，比西方早了数百年，体现了中国古代数学的智慧。
在现代计算机安全领域，大整数的模幂运算和离散对数问题是构建公钥密码体系的基石。
线性同余方程 ax ≡ b (mod m) 是最基本的同余方程形式。其解的存在性和个数取决于系数 a 和模数 m 的最大公约数。
令 d = gcd(a, m)。线性同余方程 ax ≡ b (mod m) 有解的充要条件是 d | b（即 d 整除 b）。
求解线性同余方程通常使用扩展欧几里得算法。以下是详细步骤：
| 方程形式 | 条件 | 解的个数 | 求解方法 |
|---|---|---|---|
| ax ≡ b (mod m) | gcd(a, m) ∤ b | 0 | 无解 |
| ax ≡ b (mod m) | gcd(a, m) | b | d = gcd(a, m) | 扩展欧几里得算法 |
| ax ≡ 1 (mod m) | gcd(a, m) = 1 | 1 | 求乘法逆元 |
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x, y = extended_gcd(b % a, a)
return gcd, y - (b // a) x, x
def solve_linear_congruence(a, b, m):
gcd, x, y = extended_gcd(a, m)
if b % gcd != 0:
return [] # 无解
else:
x0 = (x (b // gcd)) % m
solutions = []
for i in range(gcd):
solutions.append((x0 + i (m // gcd)) % m)
return solutions
示例：求解 6x ≡ 3 (mod 9)
print(solve_linear_congruence(6, 3, 9)) # 输出: [0, 3, 6]
中国剩余定理（Chinese Remainder Theorem, CRT）是同余方程组求解的核心定理。它解决了当模数两两互素时，线性同余方程组的解的存在性和唯一性问题。
设 m1, m2, ..., mk 是两两互素的正整数，则对于任意整数 a1, a2, ..., ak，同余方程组
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ ak (mod mk)
在模 M = m1 m2 ... mk 下有唯一解。
1. 计算 M = m1 m2 ... mk。
2. 计算 Mi = M / mi。
3. 计算 Mi 模 mi 的乘法逆元 ti，即 Mi ti ≡ 1 (mod mi)。
4. 解为 x = (a1 M1 t1 + a2 M2 t2 + ... + ak Mk tk) mod M。
问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
即求解同余方程组：
解：M = 3 5 7 = 105。
M1 = 35, M2 = 21, M3 = 15。
t1 = 35^-1 mod 3 = 2 (因为 35 2 = 70 ≡ 1 mod 3)
t2 = 21^-1 mod 5 = 1 (因为 21 1 = 21 ≡ 1 mod 5)
t3 = 15^-1 mod 7 = 1 (因为 15 1 = 15 ≡ 1 mod 7)
x = (2 35 2 + 3 21 1 + 2 15 1) mod 105 = (140 + 63 + 30) mod 105 = 233 mod 105 = 23。
所以最小正整数解为 23。
存在性：构造 x = Σ(ai Mi ti)，显然 x ≡ ai (mod mi) 对所有 i 成立。
唯一性：若 x1 和 x2 都是解，则 x1 ≡ x2 (mod mi) 对所有 i 成立。由于 mi 两两互素，故 x1 ≡ x2 (mod M)。因此在模 M 下解唯一。
def chinese_remainder_theorem(congruences):
# congruences 是 [(a1, m1), (a2, m2), ...] 形式的列表
M = 1
for _, m in congruences:
M = m
x = 0
for ai, mi in congruences:
Mi = M // mi
ti = pow(Mi, -1, mi) # 求逆元
x += ai Mi ti
return x % M
示例：x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
print(chinese_remainder_theorem([(2, 3), (3, 5), (2, 7)])) # 输出: 23
二次剩余是数论中另一个重要概念。若存在整数 x 使得 x^2 ≡ a (mod p) 有解，则称 a 是模 p 的二次剩余；否则称为二次非剩余。
对于奇素数 p 和整数 a (p ∤ a)，a 是模 p 的二次剩余当且仅当：
a^((p-1)/2) ≡ 1 (mod p)
若 a^((p-1)/2) ≡ -1 (mod p)，则 a 是模 p 的二次非剩余。
勒让德符号 (a/p) 定义为：
二次互反律是数论中最优美的定理之一。设 p 和 q 为不同的奇素数，则：
(p/q) (q/p) = (-1)^((p-1)/2 (q-1)/2)
这意味着：
模 7 的二次剩余：1^2=1, 2^2=4, 3^2=2, 4^2=2, 5^2=4, 6^2=1。
所以模 7 的二次剩余是 1, 2, 4；非剩余是 3, 5, 6。
二次剩余的性质可用于设计概率素性测试算法，如Solovay-Strassen测试，用于判断一个大整数是否为素数。
同余方程不仅仅是抽象的数学理论，它在现代科技中有着广泛的应用，尤其是在密码学和计算机科学领域。
RSA算法是目前应用最广泛的公钥密码体制之一，其安全性基于大整数分解的困难性。其核心操作涉及模幂运算，这与同余方程密切相关。
解密过程的正确性依赖于欧拉定理：若 gcd(m, n) = 1，则 m^φ(n) ≡ 1 (mod n)。因此 c^d = (m^e)^d = m^(ed) = m^(kφ(n)+1) ≡ m (mod n)。
在许多哈希算法中，模运算被用来将任意长度的输入映射到固定长度的输出。例如，CRC（循环冗余校验）算法使用多项式除法（本质上是模 2 算术）来生成校验和，用于检测数据传输中的错误。
线性同余生成器（LCG）是一种经典的伪随机数生成算法，其递推公式为：
X_{n+1} = (a X_n + c) mod m
其中 a 是乘数，c 是增量，m 是模数。虽然 LCG 的随机性质量不高，不适用于密码学，但在模拟和游戏中广泛使用。
RSA算法首次被提出，标志着公钥密码学的诞生，其核心依赖于模运算。
椭圆曲线密码学（ECC）被提出，利用椭圆曲线上的离散对数问题，提供更强的安全性，其数学基础也是数论。
量子计算的发展对基于数论的密码体制构成威胁，Shor算法可以高效分解大整数和求解离散对数，促使后量子密码学的研究。
在学习和研究初等数论同余方程的过程中，许多学习者会遇到一些共性问题。以下是针对这些问题的深度解答，帮助您更好地理解和应用相关知识。
要判断 b 是否是 a 模 m 的逆元，只需验证 a b ≡ 1 (mod m) 是否成立。在实际计算中，可以使用扩展欧几里得算法来求解逆元，该算法不仅能判断逆元是否存在（即 gcd(a, m) 是否为 1），还能给出具体的逆元值。
标准形式中国剩余定理要求模数两两互素。如果模数不互素，同余方程组可能有解，也可能无解。解存在的充要条件是：对于任意 i, j，有 ai ≡ aj (mod gcd(mi, mj))。如果解存在，解在模 lcm(m1, m2, ..., mk) 下唯一。
对于奇素数 p，在 1 到 p-1 的整数中，恰好有 (p-1)/2 个二次剩余和 (p-1)/2 个二次非剩余。二次剩余在模 p 的剩余类中分布相对均匀，但具体位置没有简单的公式。二次互反律提供了计算勒让德符号的高效方法，从而判断二次剩余性。
RSA 算法的安全性依赖于大整数分解的困难性。如果 p 和 q 很小，攻击者可以轻易地分解 n = p q，从而计算出 φ(n) 和私钥 d。使用大素数（通常是 1024 位或更长）使得分解计算在现有计算能力下不可行，从而保证安全性。
除了密码学，同余方程还应用于：