中国の剰余定理とは、ある数学の問題とそれに関連した定理の事である。
概要・例題
中国大陸で晋の時代、推定3~4世紀ごろに出版された算術書『孫子算経』に、「物不知数」という問題が記載されている。これが問題として成り立つ背景、もしくはこの問題の構造自体を説明したものが、中国の剰余定理である。「孫子」と言うが、一般的に孫子として有名な孫武より時代が大分新しいので別人であるらしい。
その問題の要旨は、未知の整数Nに対し、Nを自然数で割ったあまりの情報だけが与えられたとき、Nをできるかぎり復元すると言うものである。記載されていた問題を現代語で書くと次のようになる。
例題の地道な解法
連立方程式を立てる。
- N=3x+2
- N=5y+3
- N=7z+2
以下のように合同式で書くことも多い。
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.
以上より、Nは 105の倍数+23 という形に表される全ての整数である。即ち N≡23 (mod 105) である。
実際、23は3で割ると2、5で割ると3、7で割ると2余る。105は3,5,7の最小公倍数である。
定理(一般の整数の場合)
今のは具体的な数を求める問題だったが、「定理」と呼ばれるのは、以下のように他の整数にまで一般化したものである。定理の構造は例題と同じで、自然数で割った余りの情報が与えられている場合、解の候補Nをある法の下で一意に求めることができるというものである。
m1, m2, …, mnがどの2つも互いに素な自然数である時、(←の最小公倍数はm1m2…mnであり、)
任意の整数の列a1, a2, …, anに対してN≡a1 (mod m1),
N≡a2 (mod m2),
…,
N≡an (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が N≡N' (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)
である。最後の式の左辺をn種類用意し、その総和を取れば
a1J1x1 + a2J2x2 + … +anJnxn ≡ aiJixi ≡ ai (mod mi)
となる。なぜならば、第i項以外は、j≠i とすると Jjはmiの倍数であることにより ajJjxj ≡ 0 (mod mi) となって消えるのである。よって N'=a1J1x1 + a2J2x2 + … + anJnxn と置けば求めたい整数の1つとなる。一般の解が N≡N' (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を選ぶ。
即ち、1≡Jixi (mod mi) となるような整数x1,x2,…,xnを選ぶということである。今は
1≡35x1 ⇔ 1≡-1x1 ⇔ x1≡-1 (mod 3) より x1=2,
1≡21x2 ⇔ 1≡1x2 ⇔ x2≡1 (mod 5) より x2=1,
1≡15x3 ⇔ 1≡1x3 ⇔ x2≡1 (mod 7) より x3=1 を選んだということ。 - N≡a1J1x1+a2J2x2+…+anJnxn (mod m1m2…mn) に代入。このNは N≡ai (mod mi) を満たすので解となる。
N≡2×(35×2)+3×(21×1)+2×(15×1)=233=105×2+23≡23.
したがって求める解は N≡23 (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に対して、を満たすAの元xが、I1∩I2∩…∩Inを法として一意に存在する。
この定理から、105で割ったあまりと3,5,7それぞれで割ったあまり(の直積)の構造が環として一致し、105で割ったあまりpを任意に指定すれば対応する3,5,7で割ったあまりq1,q2,q3が、q1,q2,q3を任意に指定すれば対応するpが必ず求まる、という事がわかる。詳しくは環論へ。
関連項目
脚注
- 2
- 0pt