中国(人)剰余定理/孫子(の)定理...

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Chinese.html より 引用 Orz〜

「

m₁，m₂ を互いに素な正整数（即ち最大公約数が１）とする。a₁，a₂ を整数する。 このとき，

x ≡a₁  (mod m₁)
x ≡a₂  (mod m₂)

を満たす整数 x が m₁m₂ を法にして唯ひとつ存在する。

この場合は２つの連立合同式ですが，全く同様にして，３個以上の連立合同式についての定理が得られます。この場合も中国の剰余定理と呼ばれます。

　具体例挙げます。

x ≡ 5 (mod  7 )
x ≡ 3 (mod 11)

証明は…

http://www.ics.nara-wu.ac.jp/~kako/teaching/ca2004/node104_ct.html などを参照〜m(_ _)m〜

具体的には...

x≡m1*a2*α+m2*a1*β　(mod m1*m2)という結合式を作り...ここで…m1*α≡1　(mod m2)m2*β≡1　(mod m1)なるものを見つければいいわけね…☆
so…x≡5　(mod 7)x≡3　(mod 11)
11*2≡1　(mod 7)7*8≡1　(mod 11)so…x≡7*3*8+11*5*2　(mod 7*11) を満たす  =7*(11*2+2)+11*(7+3)  ≡14+33  =47
^^
3個以上の連立合同式でも…2個ずつを解いて、一つずつ連立合同式の数を減らして行けるので解けますね ^^