无极之地
WUJI
无极之地。记录所思所见，慢慢写下去。
首页 / 数论 / 算法
同余方程怎么解：从判别式到可运行代码 一次同余方程 ax ≡ b (mod m) 有没有解、有几个解、怎么全部找出来。用扩展欧几里得求特解，再写中国剩余定理与一份 Python 实现。
下一篇 整除、最大公约数与裴蜀定理 世界时钟 北京 --:--:-- 东京 --:--:-- UTC --:--:-- 伦敦 --:--:-- 纽约 --:--:-- 一次同余方程看起来只是 a x ≡ b ( m o d m ) ax \equiv b \pmod m a x ≡ b ( mod m )
同余在说什么
整数 a a a b b b m m m
a ≡ b ( m o d m ) a \equiv b \pmod m a ≡ b ( mod m )
意思是 m m m a − b a-b a − b m m m 17 ≡ 5 ( m o d 12 ) 17 \equiv 5 \pmod{12} 17 ≡ 5 ( mod 12 ) 17 − 5 = 12 17-5=12
同余可以像普通等式那样做加减乘，但不能随便约分。6 ≡ 15 ( m o d 9 ) 6 \equiv 15 \pmod 9 6 ≡ 15 ( mod 9 ) 3 3 3 2 ≡ 5 ( m o d 9 ) 2 \equiv 5 \pmod 9 2 ≡ 5 ( mod 9 )
一次同余方程 a x ≡ b ( m o d m ) ax \equiv b \pmod m a x ≡ b ( mod m ) 其中 m > 0 m > 0 m > 0 x x x k k k
a x − m y = b ax - my = b a x − m y = b 这是二元一次不定方程，也叫线性丢番图方程。于是整套理论可以落到一件事上：求 gcd ( a , m ) \gcd(a,m) g cd( a , m ) b b b
设 d = gcd ( a , m ) d = \gcd(a,m) d = g cd( a , m )
若 d ∤ b d \nmid b d ∤ b
若 d ∣ b d \mid b d ∣ b d d d m m m
先求出一个特解 x 0 x_0 x 0
x ≡ x 0 + m d t ( m o d m ) , t = 0 , 1 , … , d − 1 x \equiv x_0 + \frac{m}{d}\, t \pmod m,\qquad t = 0,1,\dots,d-1 x ≡ x 0 + d m t 也可以写成对更小的模 m d \frac{m}{d} d m
x ≡ x 0 ( m o d m d ) x \equiv x_0 \pmod{\frac{m}{d}} x ≡ x 0 ( mod d m )
为什么是这个判别 a x − m y = b ax - my = b a x − m y = b d d d d d d a a a m m m b b b
反过来，裴蜀定理保证：存在整数 x , y x,y x , y a x + m y = d ax + my = d a x + m y = d b / d b/d b / d b b b
解的个数来自周期。若 x 0 x_0 x 0
x 0 + m d t x_0 + \frac{m}{d}t x 0 + d m t 也都是解。这些解模 m m m d d d t = 0 , 1 , … , d − 1 t = 0,1,\dots,d-1 t = 0 , 1 , … , d − 1
扩展欧几里得：把特解算出来 普通欧几里得算法只给出 d d d
d = a x + m y d = ax + my d = a x + m y 迭代写法最适合写代码。维护两组系数，使每一步的余数都能写成 a a a m m m
def egcd ( a : int , b : int ) -> tuple [ int , int , int ]: """ 返回 (d, x, y)，满足 d = gcd(a, b) = a*x + b*y。 """ old_r , r = a , b old_s , s = 1 , 0 old_t , t = 0 , 1 while r : q = old_r // r old_r , r = r , old_r - q * r old_s , s = s , old_s - 得到 d , x , y d,x,y d , x , y x x x a x ≡ d ( m o d b ) ax \equiv d \pmod b a x ≡ d ( mod b ) d ∣ b d \mid b d ∣
x 0 = x ⋅ b d x_0 = x \cdot \frac{b}{d} x 0 = x ⋅ d b 再把 x 0 x_0 x 0 [ 0 , m ) [0, m) [ 0 , m )
手算例子
例一：有唯一解 解 3 x ≡ 4 ( m o d 7 ) 3x \equiv 4 \pmod 7 3 x ≡ 4 ( mod 7 )
gcd ( 3 , 7 ) = 1 \gcd(3,7)=1 g cd( 3 , 7 ) = 1 4 4 4 7 7 7
7 = 2 ⋅ 3 + 1 3 = 3 ⋅ 1 + 0 \begin{aligned}
7 &= 2\cdot 3 + 1 \\
3 &= 3\cdot 1 + 0
\end{aligned} 7 3 = 2 ⋅ 3 + 1 = 3 ⋅ 1 + 0 回代：1 = 7 − 2 ⋅ 3 1 = 7 - 2\cdot 3 1 = 7 − 2 ⋅ 3 3 ⋅ ( − 2 ) ≡ 1 ( m o d 7 ) 3\cdot(-2) \equiv 1 \pmod 7 3 ⋅ ( − 2 ) ≡ 1 ( mod 7 ) 4 4
3 ⋅ ( − 8 ) ≡ 4 ( m o d 7 ) ⟹ x ≡ − 8 ≡ 6 ( m o d 7 ) 3\cdot(-8) \equiv 4 \pmod 7 \implies x \equiv -8 \equiv 6 \pmod 7 3 ⋅ ( − 8 ) ≡ 4 ( mod 7 ) ⟹ x ≡ − 8 ≡ 6 验算：3 ⋅ 6 = 18 ≡ 4 ( m o d 7 ) 3\cdot 6 = 18 \equiv 4 \pmod 7 3 ⋅ 6 = 18 ≡ 4 ( mod 7 )
例二：有多个解 解 6 x ≡ 9 ( m o d 15 ) 6x \equiv 9 \pmod{15} 6 x ≡ 9 ( mod 15 )
d = gcd ( 6 , 15 ) = 3 d=\gcd(6,15)=3 d = g cd( 6 , 15 ) = 3 3 ∣ 9 3 \mid 9 3 ∣ 9 3 3 3 3 3 3
2 x ≡ 3 ( m o d 5 ) 2x \equiv 3 \pmod 5 2 x ≡ 3 ( mod 5 ) 2 2 2 5 5 5 3 3 3 2 ⋅ 3 = 6 ≡ 1 2\cdot 3=6\equiv 1 2 ⋅ 3 = 6 ≡ 1
x ≡ 9 ≡ 4 ( m o d 5 ) x \equiv 9 \equiv 4 \pmod 5 x ≡ 9 ≡ 4 ( mod 5 ) x = 4 + 5 t , t = 0 , 1 , 2 x = 4 + 5t,\qquad t=0,1,2 x = 4 + 5 t , t = 0 , 1 , 2 也就是模 15 15 15 4 , 9 , 14 4,9,14 4 , 9 , 14
验算：6 ⋅ 4 = 24 ≡ 9 6\cdot 4=24\equiv 9 6 ⋅ 4 = 24 ≡ 9 6 ⋅ 9 = 54 ≡ 9 6\cdot 9=54\equiv 9 6 ⋅ 9 = 54 ≡ 9 6 ⋅ 14 = 84 ≡ 9 ( m o d 15 ) 6\cdot 14=84\equiv 9 \pmod{15} 6
例三：无解 4 x ≡ 2 ( m o d 6 ) 4x \equiv 2 \pmod 6 4 x ≡ 2 ( mod 6 ) gcd ( 4 , 6 ) = 2 \gcd(4,6)=2 g cd( 4 , 6 ) = 2 2 2 2 2 2 2
模逆元是特例 当 gcd ( a , m ) = 1 \gcd(a,m)=1 g cd( a , m ) = 1 a x ≡ 1 ( m o d m ) ax\equiv 1 \pmod m a x ≡ 1 ( mod m ) a a a m m
a x ≡ b ( m o d m ) ⟺ x ≡ a − 1 b ( m o d m ) ax \equiv b \pmod m \iff x \equiv a^{-1} b \pmod m a x ≡ b ( mod m ) ⟺ x ≡ a − 1 b ( 费马小定理给素数模一个快算法：若 p p p p ∤ a p \nmid a p ∤ a
a − 1 ≡ a p − 2 ( m o d p ) a^{-1} \equiv a^{p-2} \pmod p a − 1 ≡ a p − 2 ( mod p ) def modinv ( a : int , m : int ) -> int : d , x , _ = egcd ( a , m ) if d != 1 : raise ValueError ( f " { a } 与 { m } 不互素，没有逆元" ) return x % m
同余方程组：中国剩余定理 { x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋮ x ≡ a k ( m o d m k ) \begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\vdots \\
x \equiv a_k \pmod{m_k}
\end{cases} ⎩ ⎨ 在模 M = m 1 m 2 ⋯ m k M=m_1 m_2 \cdots m_k M = m 1 m 2 ⋯ m k
M i = M m i , t i ≡ M i − 1 ( m o d m i ) , x = ∑ i = 1 k a i M i t i M_i = \frac{M}{m_i},\qquad t_i \equiv M_i^{-1} \pmod{m_i},\qquad x = \sum_{i=1}^{k} a_i M_i t_i M i = m i 最后取 x m o d M x \bmod M x mod M
若模数不两两互素，仍可能有解，条件更严：对任意 i , j i,j i , j
a i ≡ a j ( m o d gcd ( m i , m j ) ) a_i \equiv a_j \pmod{\gcd(m_i,m_j)} a i ≡ a j ( mod g cd( m 这时可以用两两合并：先解前两个，得到一个新的同余，再和下一个合并。
例四：韩信点兵 { x ≡ 2 ( m o d 3 ) x ≡ 3 ( m o d 5 ) x ≡ 2 ( m o d 7 ) \begin{cases}
x \equiv 2 \pmod 3 \\
x \equiv 3 \pmod 5 \\
x \equiv 2 \pmod 7
\end{cases} ⎩ ⎨ ⎧ M = 105 M=105 M = 105 M 1 = 35 M_1=35 M 1 = 35 M 2 = 21 M_2=21 M 2 = 21
35 ≡ 2 ( m o d 3 ) 35 \equiv 2 \pmod 3 35 ≡ 2 ( mod 3 ) 2 2 2 2 ⋅ 2 = 4 ≡ 1 2\cdot 2=4\equiv 1 2 ⋅ 2 = 4 ≡ 1 21 ≡ 1 ( x = 2 ⋅ 35 ⋅ 2 + 3 ⋅ 21 ⋅ 1 + 2 ⋅ 15 ⋅ 1 = 140 + 63 + 30 = 233 ≡ 23 ( m o d 105 ) x = 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 = 140+63+30=233 \equiv 23 \pmod{105} x = 2 ⋅ 35 ⋅ 2 + 3 ⋅ 21 ⋅ 1 + 2 ⋅ 15 23 23 23 3 3 3 2 2 2 5 5 5 3 3 3 7 7 7 2 2 2
一份可直接用的实现 下面把「单方程」和「方程组」放在一起。单方程返回模 m m m
from math import gcd
def egcd ( a : int , b : int ) -> tuple [ int , int , int ]: old_r , r = a , b old_s , s = 1 , 0 old_t , t = 0 , 1 while r : q = old_r // r old_r , r = r , old_r - q * r old_s , s = s , 跑一下就能对上前面的手算。solve_linear 的时间是欧几里得的 O ( log m ) O(\log m) O ( log m ) O ( d ) O(d) O ( d )
写代码时容易踩的坑 先取模再求 gcd \gcd g cda a a % 会收成非负，扩展欧几里得也能处理负数，但先规范化更不容易错。
特解要乘 b / d b/d b / d b b b a x ≡ d ax\equiv d a x ≡ d a x ≡ b ax\equiv b a x ≡ b
通解的步长是 m / d m/d m / d d d d 6 x ≡ 9 ( m o d 15 ) 6x\equiv 9\pmod{15} 6 x ≡ 9 ( mod 15 ) 5 5 5 3 3 3
合并方程组时，新模是 l c m ( m 1 , m 2 ) = m 1 m 2 / gcd \mathrm{lcm}(m_1,m_2)=m_1 m_2 / \gcd lcm ( m 1 , m 2 ) = m 1 m
若只要任意一个解，不必枚举 d d d x 0 x_0 x 0 − 1 -1 − 1
和更高次方程的边界 二次同余 x 2 ≡ n ( m o d p ) x^2 \equiv n \pmod p x 2 ≡ n ( mod p ) a x ≡ b ax\equiv b a x ≡ b
所以不必把一次同余看成小学奥数。它是数论算法里最常被调用的那一层。把存在性、特解和通解三件事分开，手算和代码就会对得上。
17
−
5 =
12
(
mod
m
)
,
t
=
0 , 1 , … , d −
1
d
q
*
s
old_t , t = t , old_t - q * t
return old_r , old_s , old_t
b
4
( mod 7 )
⋅
14 =
84 ≡
9
( mod 15 )
4 x ≡ 3 ( m o d 6 ) 4x \equiv 3 \pmod 6 4 x ≡ 3 ( mod 6 )
m
mod
m
)
⎧
x ≡ a 1 ( mod m 1 ) x ≡ a 2 ( mod m
M
,
t i
≡
M i − 1
( mod m i ) , x =
i = 1 ∑ k a i M i t i
i
,
m j
))
x ≡ 2 ( mod 3 ) x ≡ 3 ( mod 5 ) x ≡ 2 ( mod 7 )
M 3 = 15
m o d 5 ) 21 \equiv 1 \pmod 5 21 ≡ 1 ( mod 5 )
15 ≡ 1 ( m o d 7 ) 15 \equiv 1 \pmod 7 15 ≡ 1 ( mod 7 ) 1 1 1 ⋅
1 =
140 +
63 +
30 =
233 ≡
23
( mod 105 )
old_s
-
q
*
s
old_t , t = t , old_t - q * t
return old_r , old_s , old_t
def solve_linear ( a : int , b : int , m : int ) -> list [ int ]:
""" 解 a x ≡ b (mod m)，返回 [0, m) 内全部解；无解返回空列表。 """
if m <= 0 :
raise ValueError ( " 模数必须为正 " )
a , b = a % m , b % m
d , x , _ = egcd ( a , m )
if b % d :
return []
x0 = ( x * ( b // d )) % ( m // d )
step = m // d
return sorted (( x0 + step * t ) % m for t in range ( d ))
def merge ( a1 : int , m1 : int , a2 : int , m2 : int ) -> tuple [ int , int ] | None :
""" 合并 x ≡ a1 (mod m1) 与 x ≡ a2 (mod m2)。 """
d = gcd ( m1 , m2 )
if ( a2 - a1 ) % d :
return None
# 解 m1 * t ≡ a2 - a1 (mod m2)
t = solve_linear ( m1 , a2 - a1 , m2 )
if not t :
return None
lcm = m1 // d * m2
return ( a1 + m1 * t [ 0 ]) % lcm , lcm
def solve_system ( congruences : list [ tuple [ int , int ]]) -> tuple [ int , int ] | None :
""" congruences 为 [(a, m), ...]，表示 x ≡ a (mod m)。
有解返回 (x0, modulus)，无解返回 None。 """
x , mod = 0 , 1
for a , m in congruences :
merged = merge ( x , mod , a , m )
if merged is None :
return None
x , mod = merged
return x , mod
if __name__ == " __main__ " :
print ( solve_linear ( 3 , 4 , 7 )) # [6]
print ( solve_linear ( 6 , 9 , 15 )) # [4, 9, 14]
print ( solve_linear ( 4 , 3 , 6 )) # []
print ( solve_system ([( 2 , 3 ), ( 3 , 5 ), ( 2 , 7 )])) # (23, 105)
2
/
g cd
2
)
⋮
x ≡ a k ( mod m k )
同余方程怎么解：从判别式到可运行代码 · 无极之地
