中国の剰余定理単語

チュウゴクノジョウヨテイリ
3.3千文字の記事
  • 2
  • 0pt
掲示板へ

中国の剰余定理とは、ある数学の問題とそれに関連した定理の事である。

概要・例題

中国大陸の時代、推定3~4世紀ごろに出版された算術書『孫子算経』に、「物不知数」という問題が記載されている。これが問題として成り立つ背景、もしくはこの問題の構造自体を説明したものが、中国の剰余定理である。「孫子」と言うが、一般的に孫子として有名な孫武より時代が大分新しいので別人であるらしい。

その問題の要旨は、未知の整数Nに対し、Nを自然数で割ったあまりの情報だけが与えられたとき、Nをできるかぎり復元すると言うものである。記載されていた問題を現代で書くと次のようになる。

ある整数Nを3で割ったら余りが2、5で割ったら余りが3、7で割ったら余りが2であった。
Nは何か。

例題の地道な解法

連立方程式を立てる。

  1. N=3x+2
  2. N=5y+3
  3. N=7z+2

以下のように合同式で書くことも多い。

  1. N2 (mod 3)
  2. N3 (mod 5)
  3. N2 (mod 7)

3変数が媒介変数でどのように表されるかをめると言う方針。解及び変数整数に限られることを利用する。

1.2.より 3x+2=5y+3.

整理して両辺2倍すると 6x=10y+2. (2倍することでxの係数6が5の倍数+1となった)

4. x=5(-x+2y)+2=5w+2. (ただし -x+2y=w とおいた)

1.3.より 3x=7z.

これに4.を代入し 3(5w+2)=15w+6=7z. (wの係数15が7の倍数+1となった)

5. w=7(z-2w)-6=7(z-2w-1)+1=7v+1. (ただし z-2w-1=v とおいた)

1.に4.5.を代入し N=3x+2=3(5w+2)+2=3(5(7v+1)+2)+2=105v+23.

(vが全ての整数値をとることが別途示されるが省略。)

以上より、Nは 105の倍数+23 という形に表される全ての整数である。即ち N23 (mod 105) である。

実際、23は3で割ると2、5で割ると3、7で割ると2余る。105は3,5,7の最小倍数である。

定理(一般の整数の場合)

今のは具体的な数をめる問題だったが、「定理」と呼ばれるのは、以下のように他の整数にまで一般化したものである。定理の構造は例題と同じで、自然数で割った余り情報が与えられている場合、解の補Nをある法の下で一意にめることができるというものである。

m1, m2, …, mnがどの2つも互いに素な自然数である時、(←の最小倍数はm1m2…mnであり、)
任意の整数の列a1, a2, …, anに対して

Na1 (mod m1),
Na2 (mod m2),
…,
Nan (mod mn)

を満たすNがm1m2…mnを法として一意に存在する。

証明

n=2の場合

m1, m2が互いに素ならユークリッドの互除法より適当整数x2, x1が存在してm1x2+m2x1=1。
これを合同を使って変形していく。

(m1x2 + m2x1 ) m2x1 1 (mod m1)
(m1x2 + m2x1 ) m1x2 1 (mod m2)

a1m2x1 a1 (mod m1)
a2m1x2 a2 (mod m2)

a1m2x1 + a2m1x2  a1 (mod m1)
a1m2x1 + a2m1x2  a2 (mod m2)

となり、N'=a1m2x1 + a2m1x2 と置けばこれがめたい整数の1つとなる。また、合同算術の性質から、一般の解Nが NN' (mod m1m2) を満たす全ての数であることも示せる(解は法のもとで一意である)。

n>2の場合

数学的帰納法を用いた明もあるが、記事が長くなってしまうので、ここでは一度に直接解をめることのできる明を紹介する。コツはn個の数m1, m2, …, mnを1つとそれ以外に分けて考えることである。iは1≦i≦nとする。mi以外の数の総積を Ji=m1m2…mn/mi と書こう。m1, m2, …, mnが互いに素なら、mi と Ji も互いに素である。ユークリッドの互除法より適当整数 ■, xiが存在してmi■+J1xi=1 [1]。先程と同様に合同を使って、

(mi■ + J1xi ) Jixi 1 (mod mi)

aiJixi ai (mod mi)

である。最後の式の左辺をn種類用意し、その総和を取れば

a1J1x1 + a2J2x2 + … +anJnxn aiJixi ai (mod mi)

となる。なぜならば、第i項以外は、j≠i とすると Jjはmiの倍数であることにより ajJjxj 0 (mod mi) となって消えるのである。よって N'=a1J1x1 + a2J2x2 + … + anJnxn と置けばめたい整数の1つとなる。一般の解が NN' (mod m1m2…mn) であることも先程と同様。

例題の綺麗な解法

というわけで、これを踏まえた先程の例題の別解を見てみよう。孫子算経や日本劫記も、高速に解けるこちらの方法を載せている。というか、こちらしか載せていない。

  • まず Ji=m1m2…mn/miめる。(1≦i≦n、以下同)
    J1=5×7=35, J2=3×7=21, J3=3×5=15.
  • Jiの倍数で、miで割ると1余るようなものJixiを1つめる。何でもよい。
    例えば35の倍数として70を、21の倍数として21を、15の倍数として15を選ぶ。
    即ち、1Jixi (mod mi) となるような整数x1,x2,…,xnを選ぶということである。今は
    135x1 ⇔ 1-1x1 ⇔ x1-1 (mod 3) より x1=2,
    121x2 ⇔ 11x2 ⇔ x21 (mod 5) より x2=1,
    115x3 ⇔ 11x3 ⇔ x21 (mod 7) より x3=1 を選んだということ。
  • Na1J1x1+a2J2x2+…+anJnxn (mod m1m2…mn) に代入。このNは Nai (mod mi) を満たすので解となる。
    N2×(35×2)+3×(21×1)+2×(15×1)=233=105×2+2323.

したがってめる解は N23 (mod 105) である。

定理(一般の環の場合)

この定理整数だけではなく一般の可換環に対しても拡する事ができる。整数は可換環の一種である。

I1, I2, …, Inが環Aのイデアルで、どのi,jに対しても1∈Ii+Ijであるとき、
( I1∩I2∩…∩In=I1I2…Inであり、)次の同が成り立つ。

A/(I1∩I2∩…∩In)≅A/I1×A/I2×…×A/In

このままでは抽的すぎて何を言っているか分からないので、大雑把だが解説する。

  • イデアルとは倍数や素数といった概念一般化したものである。
  • 1∈Ii+IjはIiとIjが「互いに素」であることを示している。
  • I1∩I2∩…∩In=I1I2…Inは、互いに素な数の最小倍数が単なる積と一致することに対応する。
  • A/IはイデアルIによるAの剰余類であり、Iを法とした合同関係を考えることに対応している。
  • A/I1×A/I2×…×A/Inは、各数を法とした合同関係の式を複数用意する事に対応している。
  • A/(I1∩I2∩…∩In)は各数の最小倍数を法とした合同関係に対応している。
  • A/(I1∩I2∩In)≅A/I1×A/I2×…×A/Inとは両辺の集合の構造が一致しているということに対応している。

以上を踏まえてよく見べてみると、整数に対する定理と基本的な構造はだいたい同じであることが分かる。

この定理の同等な表現はいろいろあり、整数の場合に近い表現は以下のようになる。

環AのイデアルI1, I2, …, Inはどの2つも互いに素であるとする。
Aの元を任意にn個用意する。選んだ元a1, a2, …, anに対して、

x ai (mod Ii) (1≦i≦n)

を満たすAの元xが、I1∩I2∩…∩Inを法として一意に存在する。

この定理から、105で割ったあまりと3,5,7それぞれで割ったあまり(の直積)の構造が環として一致し、105で割ったあまりpを任意に定すれば対応する3,5,7で割ったあまりq1,q2,q3が、q1,q2,q3を任意に定すれば対応するpが必ずまる、という事がわかる。詳しくは環論へ。

関連項目

脚注

  1. *■も整数を表す記号のつもりである。解の構成に全く使わないので具体的なアルファベットを与えないことにした。

【スポンサーリンク】

  • 2
  • 0pt
記事編集 編集履歴を閲覧

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

中国の剰余定理

1 ななしのよっしん
2019/01/02(水) 23:19:00 ID: c2HtA4GJRs
なるほどにゃんね~
部分分数分解との関係についても加筆しとくにぇ~
👍
高評価
0
👎
低評価
0
2 ななしのよっしん
2019/01/12(土) 12:08:00 ID: c2HtA4GJRs
この定理から有理式の部分分数分解明ができるかと思ったが、ちょっとわかんなくなってきたので止しておく
普通に互除法から直接行ったほうが良さそう
👍
高評価
0
👎
低評価
0