中国剰余定理～2000年の歴史～大阪大学 s.t.fake (@st_fake) 孫子算経 3～5世紀頃、中国の算術書「孫子算経」には次の問題が描かれていた。今有物、不知其数。三・三数之、剰二。五・五数之、剰三。七・七数之、剰二。問物幾何？意訳：今ここに、個数がわかっていないものがあります。３で割ると余りが２５で割ると余りが３７で割ると余りが２さて、これは全部でいくつ？まぁ皆さん考えてみましょう。あと10秒くらい。あと30秒くらい。 1分くらい。知ってるZE! という方は類題を… ７で割ると余り６９で割ると余り１１１で割ると余り１答えは。 23です。（類題：496） …気になるのは答えじゃなくて求め方ですよねー？孫子算経の解法 • 3で割ると2余る→ • 5で割ると3余る→ • 7で割ると2余る→ これらを全部足す。 210を引いて… 140 63 30 93 210 23 233 孫子算経の解法 • 一般に 3で割った時のあまり × 70 5で割った時のあまり × 21 7で割った時のあまり × 15 これらをすべて足しあわせて 105 を可能な限り引けば良い。ポイントは、105を引くところ！昔の人はなんとなく…でやっていたのかもしれませんが、これはとても重要なことなのれす！どういうこと？ 105で余りの組み合わせが1周する！ちょこっと数学的に。このことを数学的に記述しますとこうなります。 Z/105Z  (Z/ 3Z)  (Z/ 5Z)  (Z/ 7Z) 23mod105  (2 mod3,3 mod5,2 mod7) より一般に、次のようなことも成り立ちます。 Z / nZ  (Z / p Z )  (Z / pr Z ) m1 1 mr ただし　n  p1  pr m1 mr で、 p1 ,, prは互いに素ここで注意！とりあえず素因数分解しても、互いに素でなければこれは使えません。例えば有名な例だと Z / 4Z　! ( Z / 2Z )  ( Z / 2Z ) でしょうか。更に発展。これだけだと数学的なありがたみが殆ど無いわけです。まぁ暗号とかにはこのまま使われるらしいのですが。数学（主に代数）で使われるときには、イデアルの概念を用いて先の定理が描かれます。中国剰余定理（イデアル版） R：単位元を持つ可換環 I,J：Rのイデアル、互いに素（ I + J = R） a∈R とする。この時次の環準同型写像φ φ: R  ( R / I )  ( R / J) a  (a  I , a  J) は、次の同型を誘導する。 R / IJ  ( R / I )  ( R / J) 証明先に補題として、 I  J  IJ を示しておこう。ここでもイデアルが互いに素であることが生きてくる。 I  J  IJ は自明なので皆さんの練習問ｄ（ｒｙ証明証明 I  J  IJ である証明。 x  I , y  J　s.t.　x  y  1 従って　a  a( x  y)  ax  ay また、　ax  IJ , ay  IJ より a  ax  ay  IJ 証明証明 ②　Kerφ I  J ③　Imφ ( R / I )  ( R / J) 証明 ①　φ : R  ( R / I )  ( R / J) a　 (a  I , a  J) が準同型証明 φ(1)  (1  I ,1  J) ①　φ : R  ( R / I )  ( R / J ) φ(a  b)  (a  b  I , a  b  J)  I ,(baI ,J  a (a　 I , a(a  J)  b )　が準同型 J) φ(a) φ(b) φ(a  b)  (a  b  I , a  b  J)  (a  I , a  J)  (b  I , b  J) φ(a) φ(b) 証明証明 ①　φ : R  ( R / I )  ( R / J) a　 (a  I , a  J) が準同型証明 ②　Kerφ I  J 証明 x  Kerφとしよう。φ ( x)  (I , J)である。従って　x  I  I , x  J  J ゆえに　x  I , x  J 一方　x  I  J　とすると、 ②　J)  (I , J) φ( x)Ker  ( xφ  I ,Ix J ゆえに　x  Kerφ 証明証明 ②　Kerφ I  J 証明 ③　Imφ ( R / I )  ( R / J) 証明 y  (a  I , b  J)　に対して、 I  J  Rより i  j  1　なる i  I , j  J　が存在する。 x  aj  bi　とすれば、（中略） φ ( x)  y　が成立する。 ③　Imφ ( R / I )  ( R / J) 証明証明 ③　Imφ ( R / I )  ( R / J) 証明応用例 m, n : 互いに素な整数　とする。この時 Z / mnZ  (Z / mZ)  (Z / nZ) K : 体、 K [ X：] K係数1変数多項式環とする。 K [ X ] /( X 2  1)  K [ X ] /( X  1)  K [ X ] /( X  1)  RR 今日のまとめ。 3で割って◯余る 5で割って◯余る ←このタイプは105で一週する。 7で割って◯余る… 中国剰余定理でいう Z/105Z  (Z/ 3Z)  (Z/ 5Z)  (Z/ 7Z) の形となる。ご清聴、ありがとうございました。計算用紙。いわゆる余白。