中国の剰余定理についての詳しい記述はこちら↓
http://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86
一般に
a≡b mod m
はaとbをmで割った余りが等しいことを表します
こういった式を合同式といいます
（定理）中国の剰余定理
m_1,m_2,m_3・・・m_nを互いに素な自然数
a_1,a_2,a_3・・・a_nを整数とすると
連立合同式★
x≡a_1 mod m_1
x≡a_2 mod m_2
x≡a_3 mod m_3
・・・・・・
x≡a_n mod m_n
の解は
mod m=m_1・m_2・m_3・・・・・・m_n
で求められ、かつ、一意的である
（証明）
M_i=m/m_i
と置く
m_iは互いに素であるので
gcd(m_i,M_i)=1
が成り立つ（i=1,2,3,・・・,n)
次に拡張ユークリッド互除法によりy_iを求める
ただし、
y_i・M_i≡1 mod m_i・・・・・・①
を満たすものとする（i=1,2,3,・・・,n)
拡張ユークリッド互除法については下記参照
http://mixi.jp/view_diary.pl?id=1700949837&owner_id=4331598
ここで
x≡a_1・y_1・M_1+a_2・y_2・M_2+a_3・y_3・M_3+・・・+a_n・y_n・M_n mod m・・・・・・②
と置くと、①より
a_i・y_i・M_i≡a_i mod m_i（i=1,2,3,・・・,n)・・・・・・③
さらにi≠jの場合m_iはM_jの約数なので
a_j・y_j・M_j≡0 mod m_i・・・・・・④
②、③、④より
x≡a_i・y_i・M_i+Σ_(j≠i)a_j・y_j・M_j mod m_i
≡a_i+0 mod m_i
=a_i
よってxは連立合同式★の解である
次に一意性を示す
今、x, x´を★の解とすると
x≡x´ mod m_i (i=1,2,3,・・・,n)
しかし、m_iは互いに素であるので、
x≡x´ mod m
よって解は一意的
（証明終わり）
「孫子算経」の問題を解きます
「孫子算経」の問題とは簡単に言うと
「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」
という問題です
合同式で書くと
x≡2 mod 3
x≡3 mod 5
x≡2 mod 7
となります
上述のm, M_1, M_2, M_3を求めると
m=3・5・7=105
M_1=m/m_1=105/3=35
M_2=m/m_2=105/5=21
M_3=m/m_3=105/7=15
y_1を求めます
35・y_1≡1 mod 3
拡張ユークリッド互除法より
gcd(35,3)=gcd(r_0,r_1)=gcd(3,35 mod 3)
=gcd(3,2)=gcd(r_1,r_2)=gcd(2,3 mod 2)
=gcd(2,1)=gcd(r_2,r_3)=gcd(1,2 mod 1)
=gcd(1,0)=r_3=1
n=3, q_1=11, q_2=1, q_3=2
x_k, z_k（y_iを先に使ってしまったので代わりにz）を計算する
x_0=1, z_0=0
x_1=0, z_1=0
x_2=q_1・x_1+x_0=11・0+1=1
z_2=q_1・z_1+z_0=11・1+0=11
x_3=q_2・x_2+x_1=1・1+0=1
z_3=q_2・z_2+z_1=1・11+1=12
よって
r_3=(-1)^3・x_3・35+(-1)^4・z_3・3
=-1・35+12・3=-35+36=1
よって
y_1=-1
ここで1つの命題を示します
（命題）
a=bm+rのとき
ac≡rc mod m
(証明)
ac=(bm+r)c=bcm+rc≡rc mod m
（証明終わり）
これを使ってy_2, y_3を求めます
y_2は
21・y_2≡1 mod 5
を満たします
21・y_2=(5・4+1)y_2≡y_2≡1 mod 5
よって
y_2=1
y_3は
15・y_2≡1 mod 7
15・y_3=(7・2+1)y_3≡y_3≡1 mod 7
よって
y_3=1
したがって、中国の剰余定理より
x≡a_1・y_1・M_1+a_2・y_2・M_2+a_3・y_3・M_3 mod m
≡2・(-1)・35+3・1・21+2・1・15 mod 105
≡-70+63+30 mod 105
≡23 mod 105
よって
x=23
http://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86
一般に
a≡b mod m
はaとbをmで割った余りが等しいことを表します
こういった式を合同式といいます
（定理）中国の剰余定理
m_1,m_2,m_3・・・m_nを互いに素な自然数
a_1,a_2,a_3・・・a_nを整数とすると
連立合同式★
x≡a_1 mod m_1
x≡a_2 mod m_2
x≡a_3 mod m_3
・・・・・・
x≡a_n mod m_n
の解は
mod m=m_1・m_2・m_3・・・・・・m_n
で求められ、かつ、一意的である
（証明）
M_i=m/m_i
と置く
m_iは互いに素であるので
gcd(m_i,M_i)=1
が成り立つ（i=1,2,3,・・・,n)
次に拡張ユークリッド互除法によりy_iを求める
ただし、
y_i・M_i≡1 mod m_i・・・・・・①
を満たすものとする（i=1,2,3,・・・,n)
拡張ユークリッド互除法については下記参照
http://mixi.jp/view_diary.pl?id=1700949837&owner_id=4331598
ここで
x≡a_1・y_1・M_1+a_2・y_2・M_2+a_3・y_3・M_3+・・・+a_n・y_n・M_n mod m・・・・・・②
と置くと、①より
a_i・y_i・M_i≡a_i mod m_i（i=1,2,3,・・・,n)・・・・・・③
さらにi≠jの場合m_iはM_jの約数なので
a_j・y_j・M_j≡0 mod m_i・・・・・・④
②、③、④より
x≡a_i・y_i・M_i+Σ_(j≠i)a_j・y_j・M_j mod m_i
≡a_i+0 mod m_i
=a_i
よってxは連立合同式★の解である
次に一意性を示す
今、x, x´を★の解とすると
x≡x´ mod m_i (i=1,2,3,・・・,n)
しかし、m_iは互いに素であるので、
x≡x´ mod m
よって解は一意的
（証明終わり）
「孫子算経」の問題を解きます
「孫子算経」の問題とは簡単に言うと
「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」
という問題です
合同式で書くと
x≡2 mod 3
x≡3 mod 5
x≡2 mod 7
となります
上述のm, M_1, M_2, M_3を求めると
m=3・5・7=105
M_1=m/m_1=105/3=35
M_2=m/m_2=105/5=21
M_3=m/m_3=105/7=15
y_1を求めます
35・y_1≡1 mod 3
拡張ユークリッド互除法より
gcd(35,3)=gcd(r_0,r_1)=gcd(3,35 mod 3)
=gcd(3,2)=gcd(r_1,r_2)=gcd(2,3 mod 2)
=gcd(2,1)=gcd(r_2,r_3)=gcd(1,2 mod 1)
=gcd(1,0)=r_3=1
n=3, q_1=11, q_2=1, q_3=2
x_k, z_k（y_iを先に使ってしまったので代わりにz）を計算する
x_0=1, z_0=0
x_1=0, z_1=0
x_2=q_1・x_1+x_0=11・0+1=1
z_2=q_1・z_1+z_0=11・1+0=11
x_3=q_2・x_2+x_1=1・1+0=1
z_3=q_2・z_2+z_1=1・11+1=12
よって
r_3=(-1)^3・x_3・35+(-1)^4・z_3・3
=-1・35+12・3=-35+36=1
よって
y_1=-1
ここで1つの命題を示します
（命題）
a=bm+rのとき
ac≡rc mod m
(証明)
ac=(bm+r)c=bcm+rc≡rc mod m
（証明終わり）
これを使ってy_2, y_3を求めます
y_2は
21・y_2≡1 mod 5
を満たします
21・y_2=(5・4+1)y_2≡y_2≡1 mod 5
よって
y_2=1
y_3は
15・y_2≡1 mod 7
15・y_3=(7・2+1)y_3≡y_3≡1 mod 7
よって
y_3=1
したがって、中国の剰余定理より
x≡a_1・y_1・M_1+a_2・y_2・M_2+a_3・y_3・M_3 mod m
≡2・(-1)・35+3・1・21+2・1・15 mod 105
≡-70+63+30 mod 105
≡23 mod 105
よって
x=23
