欢迎来到初等数论同余方程例题专题页面。本页面旨在为数学爱好者、竞赛选手及自学者提供一份详尽的同余方程解题指南。我们将通过大量的例题解析，深入探讨从基础的模运算到高阶的孙子定理、二次剩余等核心内容。无论您是初次接触同余概念，还是希望提升解决复杂数论问题的能力，这里都能为您提供有价值的参考。
若整数 a 和 b 除以正整数 m 的余数相同，则称 a 与 b 对模 m 同余，记作 a ≡ b (mod m)。这是初等数论中最基础也最重要的概念之一。
同余方程是代数结构在整数集上的具体体现。它在密码学（如RSA算法）、计算机科学（哈希函数）、以及日历推算等领域有着不可替代的应用价值。
我们将从一次同余方程的求解入手，逐步过渡到孙子定理（中国剩余定理）的应用，最后探讨二次同余和威尔逊定理等进阶话题，并附带大量实战例题。
一次同余方程是同余方程中最简单的形式，其标准形式为 ax ≡ b (mod m)，其中 a, b, m 为整数，且 m > 0。求解此类方程的核心在于判断解的存在性，并利用扩展欧几里得算法求出特解。
设 d = gcd(a, m)。则方程 ax ≡ b (mod m) 有解的充要条件是 d | b（即 d 整除 b）。
d | b，则方程在模 m 下有 d 个不同的解。d ∤ b，则方程无解。下面通过一个具体的例题来演示求解过程。
15x ≡ 12 (mod 25)解：
gcd(15, 25)。因为 15 = 3 × 5，25 = 5 × 5，所以 gcd(15, 25) = 5。5 是否整除 12？显然 5 ∤ 12。6x ≡ 9 (mod 15)解：
gcd(6, 15) = 3。3 是否整除 9？是的，3 | 9。15 下有 3 个不同的解。3：2x ≡ 3 (mod 5)2 在模 5 下的逆元。因为 2 × 3 = 6 ≡ 1 (mod 5)，所以逆元是 3。3：6x ≡ 9 (mod 5) → x ≡ 4 (mod 5)x₀ = 4。x ≡ x₀ + k·(m/d) (mod m)，其中 k = 0, 1, 2。m/d = 15/3 = 5。k=0 时，x ≡ 4 (mod 15) → x = 4k=1 时，x ≡ 4 + 5 = 9 (mod 15) → x = 9k=2 时，x ≡ 4 + 10 = 14 (mod 15) → x = 14x ≡ 4, 9, 14 (mod 15)当 gcd(a, m) = 1 时，方程 ax ≡ b (mod m) 有唯一解。此时可以通过扩展欧几里得算法求解 ax + my = 1 的整数解 (x, y)，其中的 x 即为 a 的逆元。
// 伪代码：扩展欧几里得算法
function extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
else:
(g, x1, y1) = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) y1
return (g, x, y)
孙子定理，又称中国剩余定理（Chinese Remainder Theorem, CRT），是初等数论中关于同余方程组求解的经典定理。它解决了模数两两互质时的线性同余方程组问题。
设 m₁, m₂, ..., mₖ 是两两互质的正整数，则对于任意整数 a₁, a₂, ..., aₖ，同余方程组：
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)
在模 M = m₁m₂...mₖ 下有唯一解。
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”
数学建模：
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
解法：
M = 3 × 5 × 7 = 105M₁ = 105/3 = 35M₂ = 105/5 = 21M₃ = 105/7 = 1535y₁ ≡ 1 (mod 3) → 2y₁ ≡ 1 (mod 3) → y₁ = 221y₂ ≡ 1 (mod 5) → 1y₂ ≡ 1 (mod 5) → y₂ = 115y₃ ≡ 1 (mod 7) → 1y₃ ≡ 1 (mod 7) → y₃ = 1x = a₁M₁y₁ + a₂M₂y₂ + a₃M₃y₃x = 2×35×2 + 3×21×1 + 2×15×1x = 140 + 63 + 30 = 233x ≡ 233 (mod 105) → 233 - 2×105 = 2323 个。若模数 mᵢ 不两两互质，则不能直接套用孙子定理。此时需将方程组两两合并，转化为模数互质的形式，或逐步消元求解。
除了基本的线性同余方程，初等数论中还包含许多高阶话题，如二次剩余、威尔逊定理等。以下通过选项卡形式展示不同技巧的应用。
若存在整数 x 使得 x² ≡ a (mod p)，则称 a 为模 p 的二次剩余。判断二次剩余通常使用勒让德符号和二次互反律。
解：
计算勒让德符号 (2/17)。
根据二次互反律的补充定理：
(2/p) = (-1)^((p²-1)/8)
(17²-1)/8 = (289-1)/8 = 288/8 = 36
因为 36 是偶数，所以 (2/17) = 1。
结论：2 是模 17 的二次剩余。
验证：6² = 36 ≡ 2 (mod 17)。
威尔逊定理指出：对于素数 p，(p-1)! ≡ -1 (mod p)。其逆命题也成立，即若 (n-1)! ≡ -1 (mod n)，则 n 为素数。
解：
因为 11 是素数，根据威尔逊定理：
10! ≡ -1 (mod 11)
-1 ≡ 10 (mod 11)
答案：10。
若 p 是素数，且 p ∤ a，则 a^(p-1) ≡ 1 (mod p)。
解：
因为 13 是素数，且 13 ∤ 2，根据费马小定理：
2^12 ≡ 1 (mod 13)
100 = 12 × 8 + 4
2^100 = (2^12)^8 × 2^4 ≡ 1^8 × 16 ≡ 16 (mod 13)
16 ≡ 3 (mod 13)
答案：3。
为了系统地掌握同余方程，建议按照以下时间轴顺序进行学习：
理解整除的定义、带余除法、欧几里得算法（辗转相除法）及其扩展形式。这是求解同余方程的基石。
掌握 ax ≡ b (mod m) 的求解方法，深入理解中国剩余定理的原理与应用。这是初等数论的核心内容之一。
学习欧拉函数 φ(n) 的计算，掌握费马小定理和欧拉定理在简化大指数幂中的应用。了解二次剩余和勒让德符号。
将同余方程知识应用于RSA加密算法、离散对数问题等。通过数学竞赛真题进行综合训练。
对于一次同余方程 ax ≡ b (mod m)，其有解的充要条件是 gcd(a, m) 整除 b。如果 gcd(a, m) 不能整除 b，则无解。对于高次同余方程，通常需要通过因式分解或利用二次互反律、威尔逊定理等工具来判断解的存在性及数量。
孙子定理主要用于求解模数两两互质的线性同余方程组。在计算机科学的RSA加密算法、大整数运算优化、以及日历推算（如干支纪年与公历的转换）中都有广泛应用。在数学竞赛中，常出现已知一个数除以不同余数所得余数，求该数的问题。
费马小定理是欧拉定理的特例，仅适用于模数 p 为素数的情况，即 a^(p-1) ≡ 1 (mod p)。而欧拉定理适用于任意正整数模数 m，即 a^φ(m) ≡ 1 (mod m)，其中 φ(m) 是欧拉函数。在解高次同余方程时，若模数为素数优先用费马小定理简化指数，若模数为合数则需计算欧拉函数值并使用欧拉定理。
当模数不互质时，不能直接应用中国剩余定理。此时可以将每个同余方程 x ≡ aᵢ (mod mᵢ) 转化为 x = aᵢ + k·mᵢ 的形式，然后代入下一个方程，逐步消元，或者将模数分解为素数幂的形式，分别求解后再合并。
二次互反律是数论中的核心定理，它描述了两个不同奇素数 p 和 q 的勒让德符号之间的关系：(p/q)(q/p) = (-1)^((p-1)/2 (q-1)/2)。它在判断一个数是否为模另一个数的二次剩余时非常有用，从而帮助判断二次同余方程是否有解。
通过本页面提供的初等数论同余方程例题解析，我们系统回顾了从基础的一次同余方程到高阶的孙子定理、二次剩余等核心知识。掌握这些内容不仅需要理解定理的证明，更需要通过大量的例题练习来培养直觉和计算能力。
希望这份攻略能为您的数论学习之路提供有力的支持。如果您有任何疑问或建议，欢迎在评论区留言交流。