从‘韩信点兵’到‘中国剩余定理’一个趣味算法背后的数学原理与Python代码实现中国古代军事家韩信在点兵时曾遇到一个有趣的数学问题当士兵按3人一排、5人一排、7人一排排列时都会多出1人按8人一排则多2人按6人一排则刚好排完。这个看似简单的计数问题背后隐藏着深刻的数学原理——中国剩余定理。本文将带你从历史故事出发逐步揭开这个千年数学智慧的面纱并用现代Python代码实现其算法。1. 韩信点兵问题的数学抽象韩信点兵问题本质上是一个同余方程组的求解问题。让我们先将其转化为数学语言设军队总人数为x根据题意可以得到以下同余式x ≡ 1 mod 3 x ≡ 1 mod 5 x ≡ 1 mod 7 x ≡ 2 mod 8 x ≡ 0 mod 6这类问题在古代中国、希腊和印度都有记载但最早的系统解法出现在中国南北朝时期的数学著作《孙子算经》中因此被称为中国剩余定理Chinese Remainder TheoremCRT。有趣的是这个问题在西方被称为孙子问题因为《孙子算经》的作者身份已不可考西方学者误以为与《孙子兵法》的作者孙武有关。2. 中国剩余定理的核心思想中国剩余定理解决的是模数两两互质的同余方程组问题。其基本形式为给定一组同余方程x ≡ a₁ mod m₁ x ≡ a₂ mod m₂ ... x ≡ aₖ mod mₖ其中m₁, m₂,..., mₖ两两互质则这个方程组在模Mm₁m₂...mₖ下有唯一解。定理的构造性证明给出了具体的求解步骤计算所有模数的乘积M ∏mᵢ对每个mᵢ计算Mᵢ M/mᵢ找到Mᵢ关于mᵢ的模逆元yᵢ即Mᵢ·yᵢ ≡ 1 mod mᵢ解为 x ≡ ∑aᵢMᵢyᵢ mod M注意模逆元存在的条件是Mᵢ与mᵢ互质这正是定理要求模数两两互质的原因。3. Python实现中国剩余定理让我们先用Python实现标准的中国剩余定理算法。这里我们使用SymPy库中的模逆元函数from math import prod from sympy import mod_inverse def chinese_remainder_theorem(a_list, m_list): 解同余方程组 x ≡ a_i mod m_i M prod(m_list) total 0 for a, m in zip(a_list, m_list): Mi M // m yi mod_inverse(Mi, m) total a * Mi * yi return total % M # 韩信点兵问题中的部分条件 a [1, 1, 1] # 余数 m [3, 5, 7] # 模数 print(f满足前三个条件的最小解为{chinese_remainder_theorem(a, m)})运行这段代码会输出106这是满足前三个条件的最小正整数解。实际上所有解的形式为106 105kk≥0因为3×5×7105。4. 处理非互质模数的情况韩信点兵问题中的模数并不完全互质例如6和3不互质这时标准的中国剩余定理不能直接应用。我们需要更通用的方法def extended_gcd(a, b): 扩展欧几里得算法返回(gcd, x, y)其中ax by gcd(a,b) if a 0: return (b, 0, 1) else: g, y, x extended_gcd(b % a, a) return (g, x - (b // a) * y, y) def solve_congruences(a1, m1, a2, m2): 解两个同余方程x ≡ a1 mod m1, x ≡ a2 mod m2 g, p, q extended_gcd(m1, m2) if (a1 - a2) % g ! 0: return None # 无解 lcm m1 // g * m2 x (a1 (a2 - a1) // g * p % (m2 // g) * m1) % lcm return x, lcm def general_chinese_remainder(a_list, m_list): 逐步合并同余方程的解 current_a, current_m a_list[0], m_list[0] for a, m in zip(a_list[1:], m_list[1:]): result solve_congruences(current_a, current_m, a, m) if not result: return None current_a, current_m result return current_a使用这个通用解法处理韩信点兵的所有条件# 韩信点兵的所有条件 a_list [1, 1, 1, 2, 0] # 余数 m_list [3, 5, 7, 8, 6] # 模数 solution general_chinese_remainder(a_list, m_list) if solution: print(f韩信军队的总人数可能是{solution} (最小正整数解)) else: print(这些条件无解)5. 算法优化与性能比较原始的暴力解法如输入信息中的代码虽然简单但对于大模数效率极低。让我们比较几种解法的性能方法时间复杂度适用条件优点缺点暴力枚举O(N)任意条件实现简单效率低下标准CRTO(k²)模数互质高效精确限制严格扩展CRTO(k² log M)任意条件通用性强实现复杂对于教育目的我们可以实现一个更易理解的逐步合并版本def merge_congruences(c1, c2): 合并两个同余条件(a1,m1)和(a2,m2) a1, m1 c1 a2, m2 c2 # 解方程 x a1 k*m1 a2 l*m2 # 即 k*m1 ≡ a2-a1 mod m2 g, p, _ extended_gcd(m1, m2) if (a2 - a1) % g ! 0: return None # 无解 k0 (a2 - a1) // g * p % (m2 // g) new_a a1 k0 * m1 new_m m1 // g * m2 return new_a % new_m, new_m def solve_all_congruences(conditions): 逐步合并所有同余条件 current (0, 1) # 初始条件x ≡ 0 mod 1表示任意整数 for cond in conditions: current merge_congruences(current, cond) if not current: return None return current使用示例conditions [(1,3), (1,5), (1,7), (2,8), (0,6)] result solve_all_congruences(conditions) if result: a, m result print(f解的形式为x ≡ {a} mod {m}) print(f最小正整数解为{a if a !0 else m})6. 实际应用与现代密码学中国剩余定理不仅在古代用于历法计算和军事调度在现代计算机科学中也有广泛应用RSA解密优化使用CRT可以加速RSA解密过程约4倍并行计算将大数运算分解为多个小模数运算哈希算法设计抗碰撞的哈希函数编码理论纠错码的设计以下是一个使用CRT优化RSA解密的示例def rsa_crt_decrypt(c, d, p, q): 使用CRT进行RSA解密 dp d % (p-1) dq d % (q-1) qinv mod_inverse(q, p) m1 pow(c, dp, p) m2 pow(c, dq, q) h (qinv * (m1 - m2)) % p return m2 h * q # 示例参数实际应用中p,q应为大素数 p, q 61, 53 n p * q phi (p-1)*(q-1) e 17 d mod_inverse(e, phi) # 加密消息m65 c pow(65, e, n) print(f密文{c}) # 常规解密 m pow(c, d, n) print(f常规解密结果{m}) # CRT优化解密 m_crt rsa_crt_decrypt(c, d, p, q) print(fCRT解密结果{m_crt})7. 教学建议与常见误区在教学中国剩余定理时有几个关键点需要特别注意模数互质条件学生常常忽略这一点导致错误应用标准CRT解的唯一性解是在模M下的唯一不是绝对的唯一负数的处理同余方程中负数需要规范化无解情况的判断方程组可能无解需要提前检查一个常见的错误实现是忽略模逆元不存在的情况# 错误示例未检查模逆元是否存在 def incorrect_crt(a_list, m_list): M prod(m_list) total 0 for a, m in zip(a_list, m_list): Mi M // m try: yi mod_inverse(Mi, m) except ValueError: return None # 必须处理无逆元的情况 total a * Mi * yi return total % M正确的教学顺序应该是从具体问题如韩信点兵引入同余概念讲解简单情况的解法如两个同余方程推广到一般情况的CRT讨论模数不互质的扩展情况最后介绍算法实现和优化
从‘韩信点兵’到‘中国剩余定理’：一个趣味算法背后的数学原理与Python代码实现
发布时间：2026/6/1 14:13:25
从‘韩信点兵’到‘中国剩余定理’一个趣味算法背后的数学原理与Python代码实现中国古代军事家韩信在点兵时曾遇到一个有趣的数学问题当士兵按3人一排、5人一排、7人一排排列时都会多出1人按8人一排则多2人按6人一排则刚好排完。这个看似简单的计数问题背后隐藏着深刻的数学原理——中国剩余定理。本文将带你从历史故事出发逐步揭开这个千年数学智慧的面纱并用现代Python代码实现其算法。1. 韩信点兵问题的数学抽象韩信点兵问题本质上是一个同余方程组的求解问题。让我们先将其转化为数学语言设军队总人数为x根据题意可以得到以下同余式x ≡ 1 mod 3 x ≡ 1 mod 5 x ≡ 1 mod 7 x ≡ 2 mod 8 x ≡ 0 mod 6这类问题在古代中国、希腊和印度都有记载但最早的系统解法出现在中国南北朝时期的数学著作《孙子算经》中因此被称为中国剩余定理Chinese Remainder TheoremCRT。有趣的是这个问题在西方被称为孙子问题因为《孙子算经》的作者身份已不可考西方学者误以为与《孙子兵法》的作者孙武有关。2. 中国剩余定理的核心思想中国剩余定理解决的是模数两两互质的同余方程组问题。其基本形式为给定一组同余方程x ≡ a₁ mod m₁ x ≡ a₂ mod m₂ ... x ≡ aₖ mod mₖ其中m₁, m₂,..., mₖ两两互质则这个方程组在模Mm₁m₂...mₖ下有唯一解。定理的构造性证明给出了具体的求解步骤计算所有模数的乘积M ∏mᵢ对每个mᵢ计算Mᵢ M/mᵢ找到Mᵢ关于mᵢ的模逆元yᵢ即Mᵢ·yᵢ ≡ 1 mod mᵢ解为 x ≡ ∑aᵢMᵢyᵢ mod M注意模逆元存在的条件是Mᵢ与mᵢ互质这正是定理要求模数两两互质的原因。3. Python实现中国剩余定理让我们先用Python实现标准的中国剩余定理算法。这里我们使用SymPy库中的模逆元函数from math import prod from sympy import mod_inverse def chinese_remainder_theorem(a_list, m_list): 解同余方程组 x ≡ a_i mod m_i M prod(m_list) total 0 for a, m in zip(a_list, m_list): Mi M // m yi mod_inverse(Mi, m) total a * Mi * yi return total % M # 韩信点兵问题中的部分条件 a [1, 1, 1] # 余数 m [3, 5, 7] # 模数 print(f满足前三个条件的最小解为{chinese_remainder_theorem(a, m)})运行这段代码会输出106这是满足前三个条件的最小正整数解。实际上所有解的形式为106 105kk≥0因为3×5×7105。4. 处理非互质模数的情况韩信点兵问题中的模数并不完全互质例如6和3不互质这时标准的中国剩余定理不能直接应用。我们需要更通用的方法def extended_gcd(a, b): 扩展欧几里得算法返回(gcd, x, y)其中ax by gcd(a,b) if a 0: return (b, 0, 1) else: g, y, x extended_gcd(b % a, a) return (g, x - (b // a) * y, y) def solve_congruences(a1, m1, a2, m2): 解两个同余方程x ≡ a1 mod m1, x ≡ a2 mod m2 g, p, q extended_gcd(m1, m2) if (a1 - a2) % g ! 0: return None # 无解 lcm m1 // g * m2 x (a1 (a2 - a1) // g * p % (m2 // g) * m1) % lcm return x, lcm def general_chinese_remainder(a_list, m_list): 逐步合并同余方程的解 current_a, current_m a_list[0], m_list[0] for a, m in zip(a_list[1:], m_list[1:]): result solve_congruences(current_a, current_m, a, m) if not result: return None current_a, current_m result return current_a使用这个通用解法处理韩信点兵的所有条件# 韩信点兵的所有条件 a_list [1, 1, 1, 2, 0] # 余数 m_list [3, 5, 7, 8, 6] # 模数 solution general_chinese_remainder(a_list, m_list) if solution: print(f韩信军队的总人数可能是{solution} (最小正整数解)) else: print(这些条件无解)5. 算法优化与性能比较原始的暴力解法如输入信息中的代码虽然简单但对于大模数效率极低。让我们比较几种解法的性能方法时间复杂度适用条件优点缺点暴力枚举O(N)任意条件实现简单效率低下标准CRTO(k²)模数互质高效精确限制严格扩展CRTO(k² log M)任意条件通用性强实现复杂对于教育目的我们可以实现一个更易理解的逐步合并版本def merge_congruences(c1, c2): 合并两个同余条件(a1,m1)和(a2,m2) a1, m1 c1 a2, m2 c2 # 解方程 x a1 k*m1 a2 l*m2 # 即 k*m1 ≡ a2-a1 mod m2 g, p, _ extended_gcd(m1, m2) if (a2 - a1) % g ! 0: return None # 无解 k0 (a2 - a1) // g * p % (m2 // g) new_a a1 k0 * m1 new_m m1 // g * m2 return new_a % new_m, new_m def solve_all_congruences(conditions): 逐步合并所有同余条件 current (0, 1) # 初始条件x ≡ 0 mod 1表示任意整数 for cond in conditions: current merge_congruences(current, cond) if not current: return None return current使用示例conditions [(1,3), (1,5), (1,7), (2,8), (0,6)] result solve_all_congruences(conditions) if result: a, m result print(f解的形式为x ≡ {a} mod {m}) print(f最小正整数解为{a if a !0 else m})6. 实际应用与现代密码学中国剩余定理不仅在古代用于历法计算和军事调度在现代计算机科学中也有广泛应用RSA解密优化使用CRT可以加速RSA解密过程约4倍并行计算将大数运算分解为多个小模数运算哈希算法设计抗碰撞的哈希函数编码理论纠错码的设计以下是一个使用CRT优化RSA解密的示例def rsa_crt_decrypt(c, d, p, q): 使用CRT进行RSA解密 dp d % (p-1) dq d % (q-1) qinv mod_inverse(q, p) m1 pow(c, dp, p) m2 pow(c, dq, q) h (qinv * (m1 - m2)) % p return m2 h * q # 示例参数实际应用中p,q应为大素数 p, q 61, 53 n p * q phi (p-1)*(q-1) e 17 d mod_inverse(e, phi) # 加密消息m65 c pow(65, e, n) print(f密文{c}) # 常规解密 m pow(c, d, n) print(f常规解密结果{m}) # CRT优化解密 m_crt rsa_crt_decrypt(c, d, p, q) print(fCRT解密结果{m_crt})7. 教学建议与常见误区在教学中国剩余定理时有几个关键点需要特别注意模数互质条件学生常常忽略这一点导致错误应用标准CRT解的唯一性解是在模M下的唯一不是绝对的唯一负数的处理同余方程中负数需要规范化无解情况的判断方程组可能无解需要提前检查一个常见的错误实现是忽略模逆元不存在的情况# 错误示例未检查模逆元是否存在 def incorrect_crt(a_list, m_list): M prod(m_list) total 0 for a, m in zip(a_list, m_list): Mi M // m try: yi mod_inverse(Mi, m) except ValueError: return None # 必须处理无逆元的情况 total a * Mi * yi return total % M正确的教学顺序应该是从具体问题如韩信点兵引入同余概念讲解简单情况的解法如两个同余方程推广到一般情况的CRT讨论模数不互质的扩展情况最后介绍算法实现和优化
