独学ノート（土筆の子）コミュの中国の剰余定理

m_1,m_2,...m_nを、どの２つをとっても互いに素
（最大公約数が１であること）な整数としたとき、
１次連立合同方程式

x≡b_1 (mod m_1) (1)
x≡b_2 (mod m_2) (2)
......
x≡b_n (mod m_n) (n)

は、積M=m_1m_2...m_nを法としてただ一つの解を
持つ。
-------------------------------------

3 〜 5 世紀ごろ成立したとされる中国の算術書 『孫子算経』 には 「3 で割れば 2 余り，5 で割れば 3 余り， 7 で割れば 2 余るような数は何か」 という問いと解法が書かれている。中国の剰余定理はこの問いを他の整数についても適用できるように一般化したもの。

ｘ≡２（mod.3）、ｘ≡３ (mod.5)、ｘ≡２ (mod.7)
excelで105までの表を作って求めると答えは、２３

定理の趣旨は、(3,5)=(5,7)=(3,7)=1のとき、
3*5*7=105の中に、一つの解をもつ。 とのこと。

証明：
n=2　のときを考える。
　　　（１）より、x=b_1+m_1y (y∈Ζ(整数))
これを（２）:x≡b_2 (mod m_2)に代入し整理すると、
m_1y≡b_2-b_1 (mod m_2)
(m_1, m_2)=1 なので、この方程式は、法m_2でただ一つの解を持つ。
y≡y_0 (mod m_2) つまり、
　　　y=y_0+m_2q (q∈Ζ) ⇒ x=b_1+m_1(y_0+m_2q)
=b_1+m_1y_0+m_1m_2q
≡b_1+m_1y_0 (mod m_1m_2)

x=(b_1+m_1y_0)+m_1m_2q を、
x≡b_3 (mod m_3)に代入して整理
　　　 m_1m_2q≡b_3-(b_1+m_1y_0) (mod m_3)
(m_1m_2, m_3)=1 なので、qは、法m_3でただ一つの解を持つ。
q≡y_1 (mod m_3) つまり、
q=y_1+m_3r (r∈Ζ)
⇒ x=b_1+m_1{y_0+m_2(y_1+m_3r)}
=b_1+m_1y_0+m_1m_2y_1+m_1m_2m_3r
≡b_1+m_1(y_0+m_2y_1) (mod m_1,m_2,m_3)

x=b_1+m_1y_0+m_1m_2y_1+m_1m_2m_3r
-----
x=b_1+m_1(y_0+m_2(y_1+m_3(y_2+m_4(.....)))) (mod m_1,m_2,...m_n)


別証（ガウスの方法）
M=m_1m_2...m_n, M_i=M/m_i とする
　　　仮定から、(m_i, M_i)=1 (i=1,2,...n)がわかる。
M_if_i≡1 (mod m_i)
　を満たす整数f_i(i=1,2,...,n) が求められる。
　　　t_i=M_if_iとすると、
　　　M_iはm_j (j≠i)の倍数なので、
　　　t_i≡1 (mod m_i), t_i≡0 (mod m_j) (i≠j)
となることがわかる。これから、
　　　
　　　t_1b_1+t_2b_2+...+t_nb_n≡b_i (mod m_i) (i=1,...,n)
なので、
　　　x=t_1b_1+t_2b_2+...+t_nb_n が一つの解。

　　　もし、
　　　ｙ≡b_1 (mod m_1) (1)'
ｙ≡b_2 (mod m_2)　　(2)'　　　
......
ｙ≡b_n (mod m_n) (3)'

であれば、対応する式を引いて
　　　x≡y (mod m_1) (1)''
x≡y (mod m_2)　　(2)''　　　
......
x≡y (mod m_n) (3)''
を得る。これは、x-yが互いに素な　m_1,m_2,...m_nの
　　　倍数を意味する。
　　　したがって、x-yはそれらの最小公倍数Ｍで割れるので、
　　　x≡y (mod M) でＭを法として一致する。

例：３で割れば２余り、５で割れば３余り、７で割れば５が余る数を求めよ。

解答
x=b_1+m_1(y_0+m_2(y_1+m_3(y_2+m_4(.....)))) (mod m_1,m_2,...m_n)
=2+3*(y_0+5*(y_1+7*r)) (mod 3*5*7)
下の式からy_0=y=2, y_1=z=4
x=2+3(2+5*(4+7r))=2+6+3*20+3*5*7r=68+105r

-----------------------------------

x≡2 (mod 3)
　　 x=2+m_1y=2+3y
x≡3 (mod 5) 2+3y≡3
　　3y ≡3-2 =1 (mod 5) つまり 3y ≡6 (mod 5)より
y≡2 (mod 5)
y=2+5z
x≡5 (mod 7)
x=2+m_1y=2+3y=2+3(2+5z )=8+15z≡5 (mod 7) 　　
15z≡-3 ≡4 (mod 7) つまり、14z+z≡4 (mod 7)より
　z≡4(mod 7)
　z=4+m_3r (r∈Ζ) =4+7r
-----------------------------------------

別解：
方程式で表すと、x≡2 (mod 3)
x≡3 (mod 5)　
x≡5 (mod 7)
となる。定理の証明の記号を用いて、
　　M=3*5*7=105, M_1=5*7=35, M_2=3*7=21, M_3=3*5=15
したがって、
　　35f_1=1 (mod 3) ⇒ f_1=2 ⇒ t_1=70
21f_2=1 (mod 5) ⇒ f_2=1 ⇒ t_2=21
15f_3=1 (mod 7) ⇒ f_3=1 ⇒ t_3=15
これから
　　x=t_1b_1+t_2b_2+t_3b_3
　　x=70*2+21*3+15*5=1400+63+75=278 (mod 105)=68 (mod 105)
⇒ x=68+105k (k∈Ζ)　

参照：草場公邦著「ガロアと方程式」