中国の剰余定理 （2数の場合）
p,q を互いに素な自然数とする整数a,bを 0≦a≦p-1, 0≦b≦p-1 とする．このときx≡a (mod p)かつx≡b (mod q)を満たすx は，0≦x≦pq-1 であり，ただ一つ存在する．具体例 p=3,q=5 としよう．a,bを 0≦a≦2, 0≦b≦4 であるので，(a,b) の組み合わせは，以下の15通りある．(0,0),(0,1),(0,2),(0,3),(0,4)(1,0),(1,1),(1,2),(1,3),(1,4)(2,0),(2,1),(2,2),(2,3),(2,4)例えば (a,b)=(2,3) のときx≡2 (mod 3)x≡3 (mod 5)で，x (mod 15) を求めると以下のようになる．k,sを整数としてx=3k+2x=5s+3であるので、3k+2=5s+33k=5s+1よって5s+1≡0 (mod 3)5s≡-12s≡-12s≡-1+32s≡2s≡1 (mod 3)よって nを整数として，s=3n+1x=5(3n+1)+3=15n+5+3=15n+8よってx (mod15)≡8確かに pq-1=3×5-1=140≦x≦14 の間に x=8 が見つかった．これを (2,3)→8 と書こう例えば (a,b)=(1,4) としてみようx≡1 (mod 3)x≡4 (mod 5)のとき，x (mod 15) を求めるk,sを整数としてx=3k+1x=5s+4であるので、3k+1=5s+43k=5s+3よって5s+3≡0 (mod 3)5s≡0s≡0 (mod 3)よって nを整数として，s=3nx=5(3n)+4=15n+4よってx (mod15)≡4これも0≦x≦14 の間の数である．(1,4)→4例えば (a,b)=(1,3) としてみようx≡1 (mod 3)x≡3 (mod 5)のとき，x (mod 15) を求めるk,sを整数としてx=3k+1x=5s+3であるので、3k+1=5s+33k=5s+2よって5s+2≡0 (mod 3)5s≡-22s≡-2s≡-1s≡-1+3s≡2 (mod 3)よって nを整数として，s=3n+2x=5(3n+2)+3=15n+13よってx (mod15)≡13これも0≦x≦14 の間の数である．(1,4)→4結局，15通りの(a,b) の答えは，0から14までの14個に1対1対応すると思われる．実際に15個を対応させてみる．x≡a (mod 3)x≡b (mod 5)のとき，x (mod 15) を求めるx=3k+ax=5s+bだから3k+a=5s+b3k=5s+b-aよって5s+b-a≡0(mod 3)よって，2s≡a-b (mod 3)ここでa=0,1,2b=0,1,2,3,4だからⅰ) a-b=0 のとき2s≡0 (mod3)s≡0 (mod 3)s=3nx=15n+bこのとき，b=0,1,2 だから(a,b)=(0,0)→ x≡0 (mod 15)(a,b)=(1,1)→ x≡1 (mod 15)(a,b)=(2,2)→ x≡2 (mod 15)ⅱ) a-b=1のとき2s≡1 (mod 3)2s≡1+32s≡4s≡2 (mod 3)s=3n+2x=5(3n+2)+bx =15n+(b+10)このとき，b=0,1 だから，(a,b)=(1,0)→ x≡10 (mod 15)(a,b)=(2,1)→ x≡11(mod 15)ⅲ) a-b=2 のとき2s≡2 (mod 3)s≡1 (mod 3)s=3n+1x=5(3n+1)+bx=15n+(b+5)このとき,b=0 だから(a,b)=(2,0)→ x≡5 (mod 15)ⅳ) a-b=-1のとき2s≡-1 (mod 3)2s≡-1+32s≡2s≡1 (mod 3)s=3n+1x=5(3n+1)+bx =15n+(b+5)このとき，b=1,2,3 だから，(a,b)=(0,1)→ x≡6 (mod 15)(a,b)=(1,2)→ x≡7(mod 15)(a,b)=(2,2)→ x≡8(mod 15)ⅴ) a-b=-2のとき2s≡-2 (mod 3)s≡-1s≡-1+3s≡2 (mod 3)s=3n+2x=5(3n+2)+bx =15n+(b+10)このとき，b=2,3,4 だから，(a,b)=(0,2)→ x≡12 (mod 15)(a,b)=(1,3)→ x≡13(mod 15)(a,b)=(2,4)→ x≡14 (mod 15)ⅵ) a-b=-3のとき2s≡-3 (mod 3)2s≡0s=3nx=5(3n)+bx =15n+bこのとき，b=3,4 だから，(a,b)=(0,3)→ x≡3 (mod 15)(a,b)=(1,4)→ x≡4(mod 15)ⅶ) a-b=-4のとき2s≡-4 (mod 3)s≡-2s≡-2+3s≡1 (mod 3)s=3n+1x=5(3n+1)+bx =15n+(b+5)このとき，b=4 だから，(a,b)=(0,4)→ x≡9 (mod 15)表でまとめると，確かに15通りに1対1対応する． (a,b) 0 1 2 3 4 0 0 6 12 3 9 1 10 1 7 13 4 2 5 11 2 8 14 証明の考え方ある数を3でわった余りは， a=0,1,2ある数を5でわった余りは，b=0,1,2,3,43×5-1=14 で，0から14の15個の数の中に，例えば，3でわった余りが1, かつ 5でわった余りが2 になるような数が２つあると仮定しよう．実際には、0～14の数で，3でわった余りが1になる数は，1,4,7,10,13で，5でわった余りが2になる数は，2,7,12だから，7の一つしかない．(0～29 だったら，7と22 の２つある)この２つの数をxとyにします．3でわった余りが1になる数をxとyは，x=3k+1,y=3k’+1 となります．5でわった余りが2になる数をxとyは，x=5s+2, y=5s’+2 となります．x-y=3(k-k’) であるので，３の倍数です．また，x-y=5(s-s’) であるので，5の倍数です．したがって，x-y は15の倍数になります．(22-7=15 であるということ）しかし，0～14 の中には，最大値が14であるので，15の倍数はありません．これは矛盾です．以上の考え方にそって証明します．＜証明＞pでわった余りがa, qでわった余りがbである整数が，0からpq-1 まで２つあると仮定する．それらをx,y とする（x≠y)k,k’,s,s’を整数としてx=pk+a,y=pk’+ax=qs+b,y=qs’+bと表すことができる．x-y=p(k-k’) より x-y≡0 (mod p)また，x-y=q(s-s’)より x-y≡0 (mod q)pとqは互いに素であるので，x−y≡0 （mod pq)x≠yであるので，x-y=z を満たすzは，pqの倍数であり，これは，pq以上の数 である．このzは，0≦z≦pq-1 であることと矛盾する． したがって，背理法により0からpq-1 まで1つしかない．＜一般論＞p,qは互いに素 x≡a (mod p)x≡b (mod q)を満たすx の求め方qs≡1 (mod p)pt≡1 (mod q)を満たす s,t についてx≡a(qs)+b(pt) (mod pq)でｘが求まる．なぜならばx≡a(qs)+b(pt) (mod p)≡a･1+0≡a x≡a(qs)+b(pt) (mod q)≡0+b･1≡bが成り立っているからだ．具体例x≡2(mod 3)x≡4(mod 5)のとき5s≡1 (mod 3)2s≡12s≡1+32s≡4s≡23t≡1 (mod 5)3t≡1+53t≡6t≡2よってx≡a×(5×2)+b×(3×2)≡2×10+4×6≡20+24≡44 (mod 15)≡14で一致している．
