ガウスとユークリッドと中国人の剰余定理〜江戸時代の合同算術とは？

　フェルマーの最終定理をテーマにブログを書いてますが､a≡b(mod p)という数式(剰余式)がちょくちょく登場します。
　これは､a−bがpで割り切れる(又は､aをpで割った余りがb)事を示してますが､数学的記述では､”aはpを法(mod)としてbと合同”となります。因みに､Moduleとは"余り"という意味ですね。
　整数論では､この余り(mod)の世界で議論する事がよくあります。
　整数や実数や複素数という(数の)世界で､”この方程式を解く事はできるのか？”というのが代数学上の重要な疑問であった様に､剰余(余り)の世界にても､合同式を解く事ができるのか？というのは大きな問題です。

　例えば､ax≡b(mod c)という合同式は､bがaとcの最大公約数の倍数である時に解け､特にaとcが互いに素(最大公約数が1)であれば､bがどんな数であっても解ける事が判ります。
　

一次方程式の剰余定理

　もう､この時点で”アウトォー”という人も多いでしょうが､私もその1人なんで心配いりませぬ。
　元々数学という学問は､解らなくて当前の学問です。故に､色んな定義や定理を駆使して､難関をクリアするんですね。
　そこで､｢フェルマーの最終決着~番外編｣でも少し述べた､ディオファントスの方程式の出番です。
　1次のディオファントス方程式とは､ax+by=cの形の方程式(a,b,c整数)で､整数解x,yが存在するかを調べるものです。この様に方程式の数よりも解の数が多いものを､”不定方程式”と呼びます。
　例えば､2x+3y=1ー①ではx=2,y=−1など解は無限に存在し､その解は任意の整数をtとすれば､x=2+3t, y=−1−2tー②という形(パラメータ表示)になる。これは､x=a+bt,y=c+dtを①に代入し､係数を比較すれば②が導けます。
　一方で､2x+6y=1には解は存在しない。
　以下､｢江戸時代の合同式と剰余定理｣を参考に一部紹介します。

　ガウスは､x−2が3で割り切れる(3の倍数)である事をx≡2(mod 3)と書き､”xと2は3を法にして合同”と呼んだ。
　1次(不定)方程式のax+by=cが解を持つ為の必要十分条件は､”cがaとbの最大公約数d=(a,b)の倍数”である事です。
　この時､ax≡c(mod b)､by≡c(mod a)の2つの合同式が成り立ちます。前者のax≡c(mod b)はd=1の時､x≡p(mod b)という形の解があり､d>1の時はx≡q(mod c/d)という形の解がある。

江戸時代の剰余定理

　つまり江戸時代の数学者たちは既に､ガウスがやった様に剰余(mod)というツールを使い､1次方程式の解の構造を定めたんですね。
　そこで､上の①式の2x+3y=1はa=2,b=3,c=1より､cはa,bの最大公約数d=1で解を持つ。
　この時､2x≡1(mod 3)､3y≡1(mod 2)となり､d=1より､x≡p(mod 3)という形の解になる。
　故に､x=p+3n(n整数)となり､p=2の時に②のx=2+3tを満たし､x=...−7,−4,−1,2,5,8,11,...の全てが解となります。

　例として､2x≡1(mod 3)という合同式を考えます。2×2=4≡1(mod 3)より､x=1+3nの形の数全てが解になり､x≡1(mod 3)と書き換える事が出来る。
　しかし､3x≡1(mod 3)という式には解が存在しない。左辺は3の倍数で､右辺とは合同にならないからです。
　故に､ax≡b(mod c)は､bがaとcの最大公約数の倍数である(合同が成立する)時に解け､aとcが互いに素(最大公約数が1)であれば､bがどんな数でも解けるとは､そういう事ですね。

　次に､15x≡21(mod 33)を考えます。15と33の最大公約数は3で21は3の倍数より､解が存在する。この方程式は15x−21=33nの事ですが､両辺が3で割れ､5x−7=11nとなり､5x≡7(mod 11)と同じ式となる。
　この解は､7に11ずつ足し､5の倍数を探します。7+11×3=40が5の倍数より5x≡40(mod 11)から､x≡8(mod 11)が解となる。
　この解はx=8+11nの形より､元の(mod 33)で書き換える(0≤x<33)と､x≡8(mod 33)､x≡19(mod 33)､x≡30(mod 33)の3つの解がある事が判る。
　以上､江戸の数学からでした。

　更に､単式ではなく複式の連立合同方程式と行きたいが､ここで中国人(孫子)が発見した剰余定理について述べたいと思います。

中国人の剰余定理

　一般に､ax≡b(mod c)という形の合同方程式は､解が存在する時はx≡s(mod t)との形になるので､次にx≡a(mod m)かつx≡b(mod n)という形の連立合同方程式の解がどうなるか？が大きな問題となる。
　この解が存在する必要十分条件は､mとnの最大公約数をdとした時､a≡b(mod d)となる事です。特に､d=1(mとnが互いに素)の時､解はx≡p(mod mn)という形になる。　
　一般的に､s個の連立合同式x≡a₁(mod m₁),x≡a₁(mod m₂),･･･,x≡aₛ(mod mₛ)の解は､これを繰り返す事でx≡q(mod m₁m₂...mₛ)という形になる。これを”中国式剰余定理”と呼ぶ。
　以下､ウィキより一部抜粋です。

　この中国式剰余定理(Chinese remainder theorem)は､中国の算術書｢孫子算経｣(写真)に由来する整数剰余に関する定理で､中国人の剰余定理や”孫子の定理”とも呼ばれる。
　3～5世紀頃成立したとされる｢孫子算経｣には､”3で割ると2余り､5で割ると3余り､7で割ると2余る数は何か？”という問題とその解法が書かれてる。
　解法には､”3で割ると2余る数として140と置く。5で割ると3余る数として63と置く。7で割ると5余る数として30と置く。
　これらを足し合わせ233を得る。これから210を引き､答えの23を得る。
　一般に､3つずつにして物を数え､1余るとその度に70と置く。5で割った余りに21をかける。7で割った余りに15をかける。106以上ならば105を引く事で答えを得る”とある。

　そこで､x≡2(mod 3)とx≡3(mod 5)とx≡2(mod 7)の連立合同方程式を考え､上の”孫子の宿題”を解いてみる。
　まず､(3,5×7)と(5,3×7)と(7,3×5)はそれぞれ互いに素より､”ユークリッドの互除法”から(m, n)=(3, 35),(5, 21),(7, 15)のそれぞれについて､不定方程式mx+ny=1の整数解(x,y)が計算できる。
　つまり､3×12+35×(−1)=1､5×(−4)+21×1=1､7×(−2)+15×1=1となり､以下の3つ合同式が成立する。
　−35≡1(mod 3)､21≡1(mod 5)､15≡1(mod 7)。
　すると連立合同式x≡a(mod 3)､x≡b(mod 5)､x≡c(mod 7)の1つの解がx=−35a+21b+15cである事が容易に判る。しかも､”中国式剰余定理”より､解は3×5×7=105を法として一意的であるから､a=2,b=3,c=2より､x=−70+63+30=23なる解を得る。
　また､全ての解はkを任意の整数として､−35a+21b+15c+105kと表されるのがわかる。故に､x≡−35a+21b+15c (mod 105)がこの問題の一般解となる。

　勿論､直接計算で解く方法もあります。
　まず､上の3つの連立合同方程式を同時に満たす整数xを求める。
　x≡2(mod 3)より､x=3m+2と表せるから､これをx≡3(mod 5)に代入し､両辺から2を引くと､3m≡1(mod 5)を得る。
　この両辺に2をかけると､左辺=6m=5m+m≡5m+m (mod 5)≡m(mod 5)とみなせば､m≡2(mod 5)を得る。
　故に､m=5n+2と表せ､これにより､x=3m+2=15n+8を得る。
　更に､これをx≡2(mod 7)に代入すると､15n+8≡2(mod 7)。この式の両辺から8を引き､また15n=14n+n≡14n+n (mod 7)≡n(mod 7)である事に注意すると､n≡−6(mod 7)。
　これは､−6≡1(mod 7)より､n≡1(mod 7)と書き直せ､n=7L+1と表せ､これよりx=105L+23 を得る。つまり､x≡23(mod 105)なる解が求まる(但し､m,n,L:整数)。
　計算が煩雑になるとの欠点があるが､連立合同式の法が互いに素とならない状況､つまり中国の剰余定理が適用できない場合にても利用できる。

　因みにこの問題は､｢孫子算経｣と共に日本にも伝わり､後に和算の隆盛した江戸時代に､”百五減算”として知られた。
　13世紀､南宋末の数学家秦九韶は､一次合同式を”ユークリッドの互除法”と同等の方法で解く事で､中国の剰余定理と同等の結果を得ていた。これは､宣教師により19世紀のヨーロッパにも伝えられ､ガウスの方法と同等のものである事が確かめらてます。
　

ユークリッドとガウスの剰余定理
　
　中国の剰余定理の基本形は､次の様になる。
　”与えられた2つの整数m,nが互いに素ならば､任意の整数a,bに対し､連立合同方程式x≡a(mod m),x≡b(mod n)を満たす整数xがmnを法として一意的に存在する”
　証明は､2つの整数m,nが互いに素なら､”ユークリッド互除法(拡張版)”により適当な整数解(u,v)が存在し､mu+nv=1と書ける。
　この時､mu=−nv+1,nv=−mu+1より､mu≡1(mod n)､nv≡1(mod m)となり､そこでx=anv+bmuとおくと､x=a(1−mu)+bmu=a+(b−a)mu≡a(mod m)。また､x=anv+b(1−nv)=b+(a−b)nv≡b(mod n)となる。故に､xは上で与えられた連立合同式の解となる事が証明できる。
　解の一意性ですが､任意の解yがあると仮定する。x−yはx−y≡0(mod m)､x−y≡0(mod n)を満たす。故に､x−yはmとnとの公倍数であるが､mとnとは互いに素なので､それらの最小公倍数(m,n)の倍数となり､x−y≡0(mod mn)。
　すなわち､xとyは法mnに関して合同(x≡y)となり､一意性が証明できる。

　因みに､”ユークリッド互除法”とは大きな数同士の最大公約数を素早く計算する方法で､aをbで割り､余りcを出し､更にbをcで割り､以下割り切れるまで繰り返し､aとbの最大公約数を求めます。
　例えば､1071と1029 の最大公約数を求める時､まず1071を1029で割った余りは42となり､次に1029を42で割った余りは21。更に42を21で割った余りは0となる。故に､最大公約数は21となりますね。

　”与えられたs個の整数m₁,m₂,...,mₛがどの2つも互いに素ならば､任意の整数a₁a₂,...,aₛに対し､s個の連立合同式x≡a₁(mod m₁),x≡a₁(mod m₂),･･･,x≡aₛ(mod mₛ)を満たす整数解xがm₁m₂...mₛを法として一意的に存在する”
　この一般形の証明は､数学的帰納法と上の基本形を使えば､ずっと簡単です。
　まずs=1の時､x=a₁が解となる。
　次にs=kの時､成り立つと仮定すれば､b≡a₁(mod m₁),b≡a₁(mod m₂),･･･,b≡aₖ(mod mₖ)を満たす整数bが法m₁m₂...mₖに関して一意的に存在する。
　この時､積m₁m₂...mₖとmₖ₊₁が互いに素とすると､上の基本定理より､x≡b(mod m₁m₂...mₖ)､x≡aₖm₁m₂...mₖ(mod mₖ₊₁)を満たす整数xが法m₁m₂...mₖ₊₁に関して一意的に存在する。
　よって､k+1の時も成り立する(証明終)。
　
　一方で”数学の巨人”ガウスは､｢算術講究｣(1801)以下の様な証明を書いてます。
　ガウスは､法m₁m₂...mₖに関して､それぞれに対応する解法を示します。
　まず､解の存在の証明ですが。
 整数m₁,m₂,...,mₖがどの2つも互いに素ならば､M=m₁m₂...mₖ､m₁M₁=m₂M₂=...=mₖMₖとおくと､各mᵢとMᵢとは互いに素なので､基本定理により､i=1,2,…,kに対し､Mᵢtᵢ≡1(mod mᵢ)なるtᵢが存在する。
　この時､x≡a₁m₁M₁+a₂m₂M₂+...+aₖmₖMₖ(mod M)は､与えられた連立合同式の解になる。 
　例えば､xの第1項の法m₁に関する剰余は a₁に合同であり､第2項から第k項はM₂から Mₖがm₁の倍数となるので､xは法m₁に関してa₁と合同になる。i=2,3,…,k に関しても同様にして､x≡aᵢ(mod mᵢ)を満たす事がわかる。

　次に解の一意性の証明ですが､yを任意の解とすると､x−yは､x−y≡0(mod m₁)､x−y≡0(mod m₂)…x−y≡0(mod mₖ)を満たす。
　故に､x−yは法m₁m₂...mₖで割り切れる。m₁,m₂,...,mₖは互いに素より､x−yは法の最小公倍数Mで割り切れる。よって､x−y≡0(mod M)。
　すなわち､xとyとは法Mに関して合同になる(証明終)。

最後に

　単純な1次方程式の剰余定理だけを紹介しましたが､かなりの計算力を要しますね(-_-;)
　しかし､ガウスは2次の剰余定理をも公式化します。
　x²≡a(mod p)が解を持つ時(a,p互いに素)､aはpを法として”平方剰余”と呼び､解の判定法を平方剰余の”相互法則”と呼びました。
　ルジャンドル記号(a/p)を使い､(a/p)=1の時は解を持ち､(a/p)=−1の時は解を持たない(非平方剰余)と定義します。
　これは元々オイラーが発見したもので､”オイラーの基準”とも呼ばれ､ガウスにより証明されました。
　更に､3次や4次の法則はヤコビやアイゼンシュタインが独立に与えます。

　これだけの計算を彼ら偉大な数学者達は､一瞬の暗黙で行うんですよね。
　本来なら､ガウスの平方剰余まで紹介したかったんですが､5千字を大きく超えたので､ここら辺にしときます。