中国剩余定理对于一元线性同余方程组的求解
文章目录
中国剩余定理的提出:
最早于中国南北朝时期(公元5世纪)的数学著作《孙子算经》提出,故又称孙子定理。
记载原文如下: “ 有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。”
意思是:有一个整数,除以3余2,除以5余3,除以7余2,求这个数是多少?
写成线性同余方程组:
{ x ≡ 2 ( m o d 3 ) x ≡ 3 ( m o d 5 ) x ≡ 2 ( m o d 7 ) \begin{cases} x\equiv2 \:(mod\:3) \\ x\equiv3 \:(mod\:5) \\ x \equiv 2\:(mod\:7)\\ \end{cases} ⎩ ⎨ ⎧x≡2(mod3)x≡3(mod5)x≡2(mod7)
什么是同余?
同余在数学中是指数论中的一种等价关系,符号为 ≡ \equiv ≡。
指当两个整数 a , b a,b a,b除以同一个正整数 m m m,若得相同余数 r r r,则称这两个整数 a , b a,b a,b对于模 m m m同余。
记作 a ≡ b ( m o d m ) a\equiv b\:(mod\:m) a≡b(modm),读作 a a a与 b b b关于模 m m m同余。
什么是线性同余方程?
在数论中,线性同余方程是最基本的同余方程,“线性”表示方程的未知数次数是一次。
即形如: a x ≡ b ( m o d m ) ax\equiv b (mod\:m) ax≡b(modm) 的方程。
求解关于x的线性同余方程组:
构造 x = 2 r 1 + 3 r 2 + 2 r 3 \:x=2r_1+3r_2+2r_3 x=2r1+3r2+2r3。
r 1 , r 2 , r 3 r_1,r_2,r_3 r1,r2,r3需要满足下列条件:
F o r r 1 For\quad r_1 Forr1:
{ r 1 ≡ 1 ( m o d 3 ) r 1 ≡ 0 ( m o d 5 ) r 1 ≡ 0 ( m o d 7 ) \begin{cases} r_1\equiv1\:(mod\:3)\\ r_1\equiv0 \:(mod\:5) \\ r_1 \equiv0\:(mod\:7)\\ \end{cases} ⎩
⎨
⎧r1≡1(mod3)r1≡0(mod5)r1≡0(mod7)
F o r r 2 For\quad r_2 Forr2
{ r 2 ≡ 0 ( m o d 3 ) r 2 ≡ 1 ( m o d 5 ) r 2 ≡ 0 ( m o d 7 ) \begin{cases} r_2\equiv0\:(mod\:3)\\ r_2\equiv1 \:(mod\:5) \\ r_2 \equiv0\:(mod\:7)\\ \end{cases} ⎩
⎨
⎧r2≡0(mod3)r2≡1(mod5)r2≡0(mod7)
F o r r 3 For\quad r3 Forr3
{ r 3 ≡ 0 ( m o d 3 ) r 3 ≡ 0 ( m o d 5 ) r 3 ≡ 1 ( m o d 7 ) \begin{cases} r_3\equiv0\:(mod\:3)\\ r_3\equiv0 \:(mod\:5) \\ r_3 \equiv1\:(mod\:7)\\ \end{cases} ⎩
⎨
⎧r3≡0(mod3)r3≡0(mod5)r3≡1(mod7)
定义** [ a − 1 ] b [a^{-1}]_b [a−1]b表示 a a a在模 b b b意义下的乘法逆元。**
什么是乘法逆元?
乘法逆元可以理解为倒数。在数学中,与 x x x相乘得 1 1 1的数,即为数 𝑥 的倒数/乘法逆元,记作 1 x \frac{1}{x} x1或 x − 1 x^{-1} x−1。
什么是模意义下的乘法逆元?
在线性同余方程中 a , x , n a,x,n a,x,n满足: a x ≡ 1 ( m o d m ) ax\equiv 1\:(mod\:m) ax≡1(modm) 就称 x x x是 a a a在模 m m m的意义下的乘法逆元,读作 a m o d m a\:mod\:m amodm的逆元,记作 [ a − 1 ] m [a^{-1}]_m [a−1]m。
逆元的求解一般用:
- 扩展欧几里得。
- 费马小定理。
- 线性求逆元。
这里由于篇幅问题就不过多描述。
∵ r 1 \because r_1 ∵r1 是 5 5 5 的倍数 , r 1 r_1\: r1是 7 7 7的倍数
∴ r 1 = 35 k 1 , k 1 ∈ Z \therefore\:r_1 = 35k_1,k_1\in\Z ∴r1=35k1,k1∈Z
∵ r 1 ≡ 1 ( m o d 3 ) \because r_1\equiv1\:(mod\:3) ∵r1≡1(mod3)
∴ r 1 \therefore r_1 ∴r1既是 35 35 35的倍数,又模 3 3 3余 1 1 1, k 1 k_1 k1是 r 1 m o d 3 r_1\:mod\:3 r1mod3 的逆元
∴ k 1 = [ 3 5 − 1 ] 3 = 2 + 3 t 1 ( t 1 ∈ Z ) \therefore k_1=[35^{-1}]_3 = 2+3t_1\:(t_1\in\Z) ∴k1=[35−1]3=2+3t1(t1∈Z)
∴ r 1 = 35 ∗ k 1 = 70 + 105 t 1 \therefore r_1=35*k_1=70+105t_1 ∴r1=35∗k1=70+105t1
同理可以解出 r 2 , r 3 r_2,r_3 r2,r3
{ r 1 = 35 ∗ [ 3 5 − 1 ] 3 = 70 + 105 t 1 r 2 = 21 ∗ [ 2 1 − 1 ] 5 = 21 + 105 t 2 r 3 = 15 ∗ [ 1 5 − 1 ] 7 = 15 + 105 t 3 \begin{cases} r_1=35*[35^{-1}]_3=70+105t_1\\ r_2=21*[21^{-1}]_5=21+105t_2\\ r_3=15*[15^{-1}]_7=15+105t_3 \end{cases} ⎩
⎨
⎧r1=35∗[35−1]3=70+105t1r2=21∗[21−1]5=21+105t2r3=15∗[15−1]7=15+105t3
代回 x = 2 r 1 + 3 r 2 + 2 r 3 \:x=2r_1+3r_2+2r_3 x=2r1+3r2+2r3,得到:
x = 140 + 6 t 1 + 63 + 15 t 2 + 30 + 14 t 3 x=140+6t_1+63+15t_2+30+14t_3 x=140+6t1+63+15t2+30+14t3 = 233 + 105 ( t 1 + t 2 + t 3 ) =233+105(t_1+t_2+t_3) =233+105(t1+t2+t3)
∵ t 1 , t 2 , t 3 \because t_1,t_2,t_3 ∵t1,t2,t3是任意的非负整数。
x = 233 + 105 t ( t ∈ Z ) x\:=233+105t\:(t\in\Z) x=233+105t(t∈Z)
所以这个问题的最小正整数解为 x = 23 x=23 x=23。
这样的构造就是中国剩余定理求解的过程。
中国剩余定理求解通解:
对于一个一元的线性同余方程组:
{ x ≡ a 1 ( m o d m 1 ) ⋅ ⋅ ⋅ ⋅ ( 1 ) x ≡ a 2 ( m o d m 2 ) ⋅ ⋅ ⋅ ⋅ ( 2 ) . . . x ≡ a n ( m o d m n ) ⋅ ⋅ ⋅ ⋅ ( n ) \begin{cases} x\equiv a_1 \:(mod\:m_1)····\:(1) \\ x\equiv a_2 \:(mod\:m_2)····\:(2) \\ ...\\ x \equiv a_n\:(mod\:m_n)····\:(n)\\ \end{cases} ⎩
⎨
⎧x≡a1(modm1)⋅⋅⋅⋅(1)x≡a2(modm2)⋅⋅⋅⋅(2)...x≡an(modmn)⋅⋅⋅⋅(n)
(为了方便表述,这里给每个同余方程编号 1 , 2 , . . . , i 1,2,...,i 1,2,...,i)
其中任意两个 m i m_i mi之间互质。
对于第 i i i个同余方程:我们需要构造出这样的一个数 r i r_i ri
使得 r i r_i ri满足:
{ r i ≡ 0 ( m o d m 1 ) ⋅ ⋅ ⋅ ⋅ ( 1 ) r i ≡ 0 ( m o d m 2 ) ⋅ ⋅ ⋅ ⋅ ( 2 ) . . . r i ≡ 1 ( m o d m i ) ⋅ ⋅ ⋅ ⋅ ( i ) r i ≡ 0 ( m o d m n ) ⋅ ⋅ ⋅ ⋅ ( n ) \begin{cases} r_i\equiv 0 \:(mod\:m_1)····\:(1) \\ r_i\equiv 0 \:(mod\:m_2)····\:(2) \\ ...\\ r_i \equiv 1\:(mod\:m_i)····\:(i)\\ r_i \equiv 0\:(mod\:m_n)····\:(n) \end{cases} ⎩
⎨
⎧ri≡0(modm1)⋅⋅⋅⋅(1)ri≡0(modm2)⋅⋅⋅⋅(2)...ri≡1(modmi)⋅⋅⋅⋅(i)ri≡0(modmn)⋅⋅⋅⋅(n)
通过上面的求解过程,我们可以给出构造的过程:
设 M M M表示 ∏ i = 1 n m i \prod_{i=1}^{n}m_i ∏i=1nmi, M i = M m i M_i = \frac{M}{m_i} Mi=miM
设 t t t 表示 M i M_i Mi在模 a i a_i ai意义下的最小正整数逆元。
得到 r i = M i ∗ t i + k ∗ M r_i =M_i*t_i + k*M ri=Mi∗ti+k∗M
∵ x = ∑ i = 1 n ( a i ∗ r i ) + k M \because x = \sum_{i=1}^n(a_i*r_i)+kM ∵x=∑i=1n(ai∗ri)+kM
∴ x = ∑ i = 1 n ( a i ∗ M i ∗ t i ) + k M ( k ∈ N ) \therefore x = \sum_{i=1}^n(a_i*M_i*t_i) + kM\quad(k\in\N) ∴x=∑i=1n(ai∗Mi∗ti)+kM(k∈N)
局限:
中国剩余定理并不适用于所有的一元线性同余方程,它只适用于模数均互质的情况。
对于模数不互质的情况,我们需要深入学习 拓展中国剩余定理 E X C R T EXCRT EXCRT
由于篇幅问题,本文章不进行讲解。