数论基础（三）同余方程¶

章节概述¶

同余方程是数论中的重要内容，在密码学、计算机科学和算法竞赛中都有广泛应用。本章将详细介绍线性同余方程的求解方法以及著名的中国剩余定理。

学习目标¶

理解线性同余方程的概念
掌握线性同余方程的求解方法
理解同余方程解的结构
掌握中国剩余定理
学会使用中国剩余定理解同余方程组
了解同余方程在实际问题中的应用

（一）线性同余方程¶

线性同余方程的形式¶

标准形式：

a × x ≡ b (mod m)

其中： - a, b, m 是已知整数 - x 是未知数 - m > 0

解的存在性¶

定理：线性同余方程 a × x ≡ b (mod m) 有解的充分必要条件是 gcd(a, m) | b。

证明： - 必要性：如果方程有解，即存在 x 使得 a × x ≡ b (mod m)，则 a × x - b = k × m，即 a × x - k × m = b，所以 gcd(a, m) | b - 充分性：如果 gcd(a, m) | b，设 d = gcd(a, m)，则 b = d × b'。利用扩展欧几里得算法，可以找到 x₀, y₀ 使得 a × x₀ + m × y₀ = d，两边乘以 b'，得到 a × (x₀ × b') + m × (y₀ × b') = b，即 a × (x₀ × b') ≡ b (mod m)

解的个数¶

如果方程有解，则： - 当 gcd(a, m) = 1 时，方程在模 m 下有唯一解 - 当 gcd(a, m) = d > 1 时，方程在模 m 下有 d 个解

求解方法¶

方法一：使用扩展欧几里得算法¶

步骤： 1. 计算 d = gcd(a, m) 2. 检查 d 是否整除 b 3. 如果是，使用扩展欧几里得算法求出 a × x + m × y = d 的解 4. 将 x 乘以 b/d 得到特解 5. 通解为：x = x₀ + k × (m/d)，k = 0, 1, ..., d-1

def solve_linear_congruence(a, b, m):
    """
    求解线性同余方程 a × x ≡ b (mod m)

    参数:
        a, b: 整数
        m: 模数（正整数）

    返回:
        list: 所有解（在 [0, m-1] 范围内），按升序排列
              如果无解，返回空列表

    时间复杂度: O(log min(a, m))

    示例:
        >>> solve_linear_congruence(3, 5, 7)
        [4]  # 3 × 4 = 12 ≡ 5 (mod 7)
        >>> solve_linear_congruence(2, 4, 6)
        [2, 5]  # 2 × 2 = 4 ≡ 4 (mod 6), 2 × 5 = 10 ≡ 4 (mod 6)
        >>> solve_linear_congruence(4, 2, 6)
        [2, 5]
        >>> solve_linear_congruence(4, 3, 6)
        []  # 无解
    """
    # 计算 gcd(a, m)
    gcd_val, x, y = extended_gcd(a, m)

    # 检查是否有解
    if b % gcd_val != 0:
        return []  # 无解

    # 特解
    x0 = (x * (b // gcd_val)) % m

    # 通解：x = x0 + k × (m/d)，k = 0, 1, ..., d-1
    solutions = []
    step = m // gcd_val

    for k in range(gcd_val):
        solution = (x0 + k * step) % m
        solutions.append(solution)

    return sorted(solutions)

方法二：使用模逆元¶

适用条件：gcd(a, m) = 1

方法：x ≡ a^(-1) × b (mod m)

def solve_linear_congruence_with_inverse(a, b, m):
    """
    使用模逆元求解线性同余方程（仅当 gcd(a, m) = 1 时有效）

    参数:
        a, b: 整数
        m: 模数（正整数）

    返回:
        int: 方程的唯一解（在 [0, m-1] 范围内）
             如果无解返回 None

    示例:
        >>> solve_linear_congruence_with_inverse(3, 5, 7)
        4
    """
    inv_a = mod_inverse(a, m)

    if inv_a is None:
        return None  # 无解

    return (inv_a * b) % m

解的验证¶

def verify_solution(a, b, m, x):
    """
    验证 x 是否是方程 a × x ≡ b (mod m) 的解

    参数:
        a, b, m, x: 整数

    返回:
        bool: 如果是解返回 True，否则返回 False
    """
    return (a * x) % m == b % m

（二）中国剩余定理¶

定理陈述¶

对于一组两两互质的模数 m₁, m₂, ..., mₙ，同余方程组：

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₙ (mod mₙ)

在模 M = m₁ × m₂ × ... × mₙ 下有唯一解。

条件说明¶

两两互质：对于任意 i ≠ j，有 gcd(mᵢ, mⱼ) = 1

构造性证明¶

步骤： 1. 计算 M = m₁ × m₂ × ... × mₙ 2. 对于每个 i，计算 Mᵢ = M / mᵢ 3. 求 Mᵢ 模 mᵢ 的逆元 eᵢ，即 Mᵢ × eᵢ ≡ 1 (mod mᵢ) 4. 解为：x = Σ(aᵢ × Mᵢ × eᵢ) mod M

实现方法¶

方法一：逐步合并法¶

def crt(equations):
    """
    中国剩余定理（逐步合并法）

    参数:
        equations: 同余方程列表，每个元素是 (aᵢ, mᵢ) 的元组

    返回:
        tuple: (最小正整数解, 模数 M)
               如果无解返回 (None, None)

    时间复杂度: O(n × log M)

    示例:
        # 解方程组：
        # x ≡ 2 (mod 3)
        # x ≡ 3 (mod 5)
        # x ≡ 2 (mod 7)
        >>> equations = [(2, 3), (3, 5), (2, 7)]
        >>> solution, modulus = crt(equations)
        >>> print(f"解：{solution} (mod {modulus})")
        解：23 (mod 105)
    """
    if not equations:
        return None, None

    # 初始解
    x = equations[0][0]
    m = equations[0][1]

    for a, mi in equations[1:]:
        # 解方程：m × k ≡ a - x (mod mi)
        gcd_val, p, q = extended_gcd(m, mi)

        # 检查是否有解
        if (a - x) % gcd_val != 0:
            return None, None  # 无解

        # 计算新解
        lcm = m // gcd_val * mi  # 最小公倍数
        temp = ((a - x) // gcd_val) * p % (mi // gcd_val)
        x = x + m * temp
        x %= lcm
        m = lcm

    return x % m, m

方法二：构造法¶

def crt_constructive(equations):
    """
    中国剩余定理（构造法）

    参数:
        equations: 同余方程列表，每个元素是 (aᵢ, mᵢ) 的元组

    返回:
        tuple: (最小正整数解, 模数 M)
               如果无解返回 (None, None)

    时间复杂度: O(n × log M)

    示例:
        >>> equations = [(2, 3), (3, 5), (2, 7)]
        >>> solution, modulus = crt_constructive(equations)
        >>> print(f"解：{solution} (mod {modulus})")
        解：23 (mod 105)
    """
    if not equations:
        return None, None

    n = len(equations)

    # 提取 aᵢ 和 mᵢ
    a = [eq[0] for eq in equations]
    m = [eq[1] for eq in equations]

    # 检查模数是否两两互质
    for i in range(n):
        for j in range(i + 1, n):
            if gcd(m[i], m[j]) != 1:
                print(f"警告：m[{i}] = {m[i]} 和 m[{j}] = {m[j]} 不互质")

    # 计算 M = m₁ × m₂ × ... × mₙ
    M = 1
    for mi in m:
        M *= mi

    # 计算 x = Σ(aᵢ × Mᵢ × eᵢ) mod M
    x = 0
    for i in range(n):
        Mi = M // m[i]  # Mᵢ
        ei = mod_inverse(Mi, m[i])  # eᵢ
        if ei is None:
            return None, None  # 逆元不存在，无解
        x = (x + a[i] * Mi * ei) % M

    return x, M

验证解¶

def verify_crt_solution(equations, solution):
    """
    验证 solution 是否满足所有同余方程

    参数:
        equations: 同余方程列表
        solution: 候选解

    返回:
        bool: 如果满足所有方程返回 True，否则返回 False
    """
    for a, m in equations:
        if solution % m != a % m:
            return False
    return True

不满足互质条件的情况¶

如果模数不满足两两互质的条件，可以使用逐步合并法（crt函数），它可以处理一般情况。

（三）二次同余方程¶

二次同余方程的形式¶

标准形式：

x² ≡ a (mod p)

其中 p 是奇质数。

勒让德符号¶

定义：对于奇质数 p 和整数 a，勒让德符号 (a/p) 定义为： - (a/p) = 0，如果 a ≡ 0 (mod p) - (a/p) = 1，如果 a 是模 p 的二次剩余 - (a/p) = -1，如果 a 是模 p 的二次非剩余

二次剩余：存在整数 x，使得 x² ≡ a (mod p)

二次非剩余：不存在整数 x，使得 x² ≡ a (mod p)

欧拉判别法¶

定理：对于奇质数 p 和不被 p 整除的整数 a：

(a/p) ≡ a^((p-1)/2) (mod p)

实现：

def legendre_symbol_euler(a, p):
    """
    使用欧拉判别法计算勒让德符号 (a/p)

    参数:
        a: 整数
        p: 奇质数

    返回:
        int: 0, 1, 或 -1

    示例:
        >>> legendre_symbol_euler(2, 7)
        1
        >>> legendre_symbol_euler(3, 7)
        -1
    """
    a = a % p
    if a == 0:
        return 0

    result = mod_pow(a, (p - 1) // 2, p)
    if result == p - 1:
        return -1
    return result

求解二次同余方程¶

Tonelli-Shanks 算法：求解 x² ≡ n (mod p)

def tonelli_shanks(n, p):
    """
    Tonelli-Shanks 算法：求解 x² ≡ n (mod p)

    参数:
        n: 整数
        p: 奇质数

    返回:
        int: 一个解 x（如果存在）
             如果无解返回 None

    时间复杂度: O(log² p)

    示例:
        >>> tonelli_shanks(2, 17)
        6  # 因为 6² = 36 ≡ 2 (mod 17)
    """
    # 检查是否有解
    if legendre_symbol_euler(n, p) != 1:
        return None

    # 特殊情况：p ≡ 3 (mod 4)
    if p % 4 == 3:
        return mod_pow(n, (p + 1) // 4, p)

    # 将 p - 1 分解为 Q × 2^S，其中 Q 是奇数
    Q = p - 1
    S = 0
    while Q % 2 == 0:
        Q //= 2
        S += 1

    # 寻找一个二次非剩余 z
    z = 2
    while legendre_symbol_euler(z, p) != -1:
        z += 1

    # 初始化
    c = mod_pow(z, Q, p)
    x = mod_pow(n, (Q + 1) // 2, p)
    t = mod_pow(n, Q, p)
    m = S

    while t != 1:
        # 找到最小的 i，使得 t^(2^i) ≡ 1 (mod p)
        i = 1
        while i < m:
            if mod_pow(t, 2**i, p) == 1:
                break
            i += 1

        # 更新
        b = mod_pow(c, 2**(m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i

    return x

（四）实战应用¶

应用1：猴子分桃问题¶

问题：有 n 只猴子分 m 个桃子，第一个猴子把桃子分成 n 等份，多出 1 个，扔掉多出的 1 个，拿走 1 份；第二个猴子继续分剩下的桃子，重复同样的过程。求最初最少有多少个桃子。

def monkey_peaches(n):
    """
    猴子分桃问题

    参数:
        n: 猴子的数量

    返回:
        int: 最少的桃子数量

    示例:
        >>> monkey_peaches(5)
        3121
    """
    # 设第 i 只猴子分桃前有 xᵢ 个桃子
    # x₁ = n × k₁ + 1
    # xᵢ₊₁ = (n-1)/n × xᵢ - 1
    # 可以推导出 x₁ ≡ nⁿ - (n-1) (mod nⁿ)

    # 使用中国剩余定理
    equations = []
    for i in range(1, n + 1):
        equations.append((n - 1, n))

    solution, _ = crt(equations)
    return solution * n + 1

应用2：韩信点兵¶

问题：韩信带 1500 名士兵打仗，战死四五百人，士兵 3 人一排多 2 人，5 人一排多 3 人，7 人一排多 2 人。问幸存士兵有多少人？

def hanxin_soldiers():
    """
    韩信点兵问题

    返回:
        int: 幸存士兵数量
    """
    # 设士兵数量为 x
    # x ≡ 2 (mod 3)
    # x ≡ 3 (mod 5)
    # x ≡ 2 (mod 7)
    # 1000 < x < 1100

    equations = [(2, 3), (3, 5), (2, 7)]
    solution, modulus = crt(equations)

    # 找到满足条件的解
    while solution < 1000:
        solution += modulus

    return solution if solution < 1100 else None

# 运行
print(hanxin_soldiers())  # 输出: 1073

应用3：周期性问题¶

问题：某事件每 a 天发生一次，另一事件每 b 天发生一次，求两个事件同时发生的最小天数。

def simultaneous_event(a, b):
    """
    求两个周期事件同时发生的天数

    参数:
        a, b: 两个事件的周期（天）

    返回:
        int: 同时发生的天数

    示例:
        >>> simultaneous_event(3, 5)
        15
    """
    return lcm(a, b)

实战练习¶

练习1：解方程组¶

任务：解以下同余方程组：

x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 4 (mod 7)

def exercise_1():
    """
    解方程组
    x ≡ 1 (mod 2)
    x ≡ 2 (mod 3)
    x ≡ 3 (mod 5)
    x ≡ 4 (mod 7)
    """
    equations = [(1, 2), (2, 3), (3, 5), (4, 7)]
    solution, modulus = crt(equations)
    print(f"解：{solution} (mod {modulus})")
    return solution, modulus

练习2：判断二次剩余¶

任务：判断 a 是否是模 p 的二次剩余

def is_quadratic_residue(a, p):
    """
    判断 a 是否是模 p 的二次剩余

    参数:
        a: 整数
        p: 奇质数

    返回:
        bool: 如果是二次剩余返回 True，否则返回 False

    示例:
        >>> is_quadratic_residue(2, 7)
        True
        >>> is_quadratic_residue(3, 7)
        False
    """
    # 你的代码
    pass

练习3：求解同余方程¶

任务：求解 x，使得：

4x + 7 ≡ 3 (mod 9)

def exercise_3():
    """
    求解 4x + 7 ≡ 3 (mod 9)
    """
    # 你的代码
    pass

章节小结¶

本章介绍了同余方程的求解方法：

线性同余方程：掌握使用扩展欧几里得算法求解
中国剩余定理：理解定理内容和应用，掌握逐步合并法和构造法
二次同余方程：了解勒让德符号和 Tonelli-Shanks 算法
实际应用：学会将实际问题转化为同余方程求解

同余方程在密码学、编码理论和算法竞赛中都有重要应用。

下一步¶

继续学习第四章：数论函数，学习欧拉函数、莫比乌斯函数等重要数论函数。

重点提醒： - 线性同余方程有解的必要条件是 gcd(a, m) | b - 中国剩余定理要求模数两两互质 - 逐步合并法可以处理一般情况 - 勒让德符号用于判断二次剩余