数论——中国剩余定理及其扩展详解

概述

1. 引入：

   一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
   有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
   即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

2. 概述：
   孙子定理，又称中国剩余定理或中国余数定理，是数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。

3. 内容
   用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：
   有解的判定条件，并用构造法给出了在有解情况下解的具体形式。

   中国剩余定理说明：假设整数$m_1,m_2,...,m_n$其中任两数互质，则对任意的整数：$a_1,a_2,...,a_n$，方程组$(S)$有解，并且通解可以用如下方式构造得到：

   1. 设$M=m_1\times m_2\times \cdots \times m_n=\prod _{i=1}^n{m}_i$是整数$m_1,m_2,...,m_n$的乘积，并设 M i = M / m i ,      ∀ i ∈ { 1 , 2 , ⋯   , n } M i = M / m i ,      ∀ i ∈ { 1 , 2 , ⋯   , n } {\displaystyle M_{i}=M/m_{i},\;\;\forall i\in \{1,2,\cdots ,n\}}M_i = M/m_i, \; \; \forall i \in \{1, 2, \cdots , n\} Mi​=M/mi​,∀i∈{1,2,⋯,n}Mi​=M/mi​,∀i∈{1,2,⋯,n}，即$M_i$是除了$m_i$以外的n − 1个整数的乘积。
   2. 设$t_i=M_i^{-1}为M_i$模 m i 的 逆 元 ： t i M i ≡ 1 ( m o d m i ) ,      ∀ i ∈ { 1 , 2 , ⋯   , n } . {\displaystyle m_{i}}的逆元：{\displaystyle t_{i}M_{i}\equiv 1{\pmod {m_{i}}},\;\;\forall i\in \{1,2,\cdots ,n\}.} mi​的逆元：ti​Mi​≡1(modmi​),∀i∈{1,2,⋯,n}.
   3. $方程组(S)的通解形式为：$$x=a_1{t}_1{M}_1+a_2{t}_2{M}_2+\cdots +a_n{t}_n{M}_n+kM=kM+\sum _{i=1}^n{a}_i{t}_i{M}_i,k\in \mathbb{Z}.$$在模M的意义下，方程组(S)只有一个解：x=\sum _{i=1}^n{a}_i{t}_i{M}_i.$

4. 证明：
   

def exgcd(a, b) :
	if b == 0 :
	return 1, 0, a
	x, y, d = exgcd(b, a % b)
	return y, x - (a // b) * y, d
1
2
3
4
5

def CRT(a, b) : #a, b分别是模数和余数
	M = 1
	X = 0
	for i in a :
		M *= i
	for i in zip(a, b) :
		w = M // i[0]
		x, y, d = exgcd(w, i[0])
		X = (X + x * w * i[1]) % M	
	return (X % M + M) % M
1
2
3
4
5
6
7
8
9
10

中国剩余定理扩展

求解模数不互质情况下的线性方程组

1. 原理说明：
   普通中国剩余定理要求所有的模数$m_i$互素，如果不互素就需要使用扩展中国剩余定理
   $x\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)$ —— (1)
   $x\equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)$ ——（2）
   $....$
   $x\equiv a_n(\mathrm{m}\mathrm{o}\mathrm{d}{m}_n)$
   对于（1）、（2）式，可得$x=m_1{x}_1+a_1$、$x=m_2{x}_2+a_2$
   可以推出$m_1{x}_1+a_1=m_2{x}_2+a_2$->$m_1{x}_1=(a_2-a_1)+m_2{x}_2$
   如果该式成立则$gcd(m_1,m_2)|(a_2-a_1)$
   ->$m_1{x}_1=(a_2-a_1)(mod{m}_2)$
   要求x最小，即求$x_1$最小，使用扩展欧几里得算法$exgcd(m_1,m_2)$求出最小公约数d以及$m_1/d$的逆，最小$x_1\equiv (a_2-a_1)/d\ast (m_1/d{)}^{-1}(mod{m}_2/d)$。
   所以$x_1取最小值，x1=[(a_2-a_1)/d\ast (m_1/d{)}^{-1}+m_2/d]\%(m_2/d)$
   代入$x=m_1{x}_1+a_1$
   得到一个$x=(m_1\ast m_2)/d\ast k+a_1+m_1\ast (a_2-a_1)/d\ast (m_1/d{)}^{-1}$
   则k可视为一个新的$x$,$a_1+m_1\ast (a_2-a_1)/d\ast (m_1/d{)}^{-1}$可视为新的a

例题

n = int(input())
def exgcd(a, b) :
	if b == 0 :
		return 1, 0, a
	x, y, g = exgcd(b, a % b)
	return y, x - (a // b) * y, g
x = 0
m1, a1 = map(int, input().split())

for i in range(n - 1):
	m2, a2 =  map(int, input().split())
	k1, k2, d = exgcd(m1, m2)
	k1 *= (a2 - a1) // d
	k1 = (k1 % (m2 // d) + (m2 // d)) % (m2 // d) ###求最小正整数
	x = k1 * m1 + a1
	m1 = abs(m1 * m2 // d)
	a1 = x
if x != -1 :
	x = (a1 % m1 + m1) % m1
print(x)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

总结

中国剩余定理真孙子，太难啦，我要成孙子了。