ページの最終校正年月日 :

　その他、古代の数学で互いに類似していること
文献
  1. B.L.van der Waerden, Geometry and Algebra in Ancient Civilizations, 1983, Springer Verlag (ISBN 3-540-12159-5)
  2. ユークリッド原論、中村幸四郎など訳・解説、共立出版
  3. L. E. Dickson, History of the Theory of Numbers, I, II, III, Chelsea (原書 1919, 1920, 1923 からのリプリント)
  4. C. F. Gauss, Disquisitiones Arithmeticae, Springer-Verlag (英訳)
  5. ボイヤー, 数学の歴史, 朝倉書店
ユークリッド互除法

九章算術は紀元前 1 世紀から紀元後 2 世紀に至るまで加筆修正された本で、 263 年に注釈を加えた劉徽によると、秦の始皇帝 (221-206 B.C.) の 焚書坑儒によって失われた本を再度集大成したものである。

第一章は日本語の Wiki では

方田 - 主に田畑の(年貢のための)面積計算と分数の計算
とあり、分数の計算を扱っている。

ファン・デル・ヴェルデンの本によると その中で分数を簡約する話が扱われ、 実例として 49/91 が取り上げられ、 まず次のように計算し (大きい数から小さい数を引いている。)

4949777777
914242352821147

更に、分母分子を 7 で割ることを指示している。これは 49, 91 の 最大公約数である。

ユークリッド原論では分数は登場しないが、比は登場する。 ユークリッド原論の巻 7 で比 m : n を最も簡単な比にする方法が 述べられており、基本的には九章算術と同じである。次の事実を繰り返し適用して より小さい数の最大公約数を求めることに帰着している。

a＞b＞0 が整数であれば gcd(a, b) = gcd(a-b, b)

証明　　a, b の公約数は a-b, b の公約数で、逆に a-b, b の公約数は a, b の公約数となる。 従って、このような数の中で最大のものは一致する。

今日、ユークリッド互除法 (あるいはユークリッドのアルゴリズム) と呼ばれる方法は、何度も引き算をするのではなく 交互に割り算をするが、基本的には同じである。 a, b の最大公約数を求めるのには次のようにする。 q i は商、ri は余りである。 最終的に割り切れたときの rn が a, b の最大公約数である。

ユークリッド互除法
a =q 1b + r1(0<r1<b)
b =q 2r1 + r2(0<r2<r1)
r1=q 3r2 + r3(0<r3<r2)
... ...
rn-2=q nrn-1 + rn  (0<rn<rn-1)
rn-1=q n+1rn

ユークリッド互除法に関連して、次のことが基本的な事実であり、証明を加えておく。

ユークリッド互除法から導かれる事実
a, b の 最大公約数が d であれば、次を満たす整数 x, y が存在する。
a x + b y = d

証明　　ユークリッド互除法の最初の式から

r1 = a x1 + b y1
と書くことが出来る。(x1 = 1, y1 = -q 1) これを第 2 番目の式に代入して整理すると
r2 = a x2 + b y2
の形に整理できる。以上の r1, r2 を第 3 番目の式に代入して 整理すると
r3 = a x3 + b y3
これをずっと繰り返すと、最後に
rn = a xn + b yn
の形の式を得る。rn が a, b の最大公約数であるから結果を示すことが出来た。

以上の証明は、少し難しく思えるが、九章算術の (49, 91) の最大公約数を求める手順を振り返れば 明らかです。

実際の計算4949 7 7 .......
9142 42 35 .......
対応する式a a a-(b-a)a-(b-a) .......
b b-ab-a (b-a)-(a-(b-a)).......

つまり、交互に差を取っていけば、得られる数値は整理をすると必ず次の形となります。 

* a + * b　　　(* は整数)

従って、最大公約数もこのように書けることになります。 古代人が、この「ユークリッド互除法から得られる事実」を知っていたとしても不思議ではないのですが、 言葉ではうまく表現できなかったと思われます。 古代には負の数がなかったためです。(a, b の係数の一方が必ず正で、もう一方が負です。)

中国の剰余の定理
孫子算経

少しディクソンの「数論の歴史」からの抜粋をします。(II, p 57 - p 58)

孫子算経 (3 世紀頃の本) には

3 で割って 2 余り、 5 で割って 3 余り、7 で割って 2 余る数の決め方

が載っています。その方法は

5×7 の倍数で 3 で割って 1 余る数 = 70
3×7 の倍数で 5 で割って 1 余る数 = 21
3×5 の倍数で 7 で割って 1 余る数 = 15

を求めて

2×70 + 3×21 + 2×15 = 233

を計算し、更に 3×5×7 = 105 で割った余り 23 を最小解としています。 この事実は Alexander Wylie が 1853 年の Shanghai Almanac (上海年報とでも訳す ?) に 掲載した英文の記事 (or 論文) でヨーロッパに紹介され、部分的にドイツ語にも翻訳されます。 しかし誤訳があったため、カントールに間違いであると批判されてしまいます。 しかし、すぐに L. Matthiessen はガウスの「整数論」に述べられている、 次の事実と同じであることを指摘しました。

m1, m2, m3, ... が互いに素で、 m = m1 m2 m3 ... とする。もしも
αi ≡ 0 mod m/mi, 　αi ≡ 1 mod mi 　　(i = 1, 2, 3,... )
であれば x = α1 r1 + α2 r2 + ... は
x ≡ r1 mod m1,　x ≡ r2 mod m2,....
の一つの解である。

以上がディクソンからの抜粋で、これが「中国の剰余の定理」の名前の由来のようです。 しかし、今日「中国の剰余の定理」と呼ばれるものは厳密には次の定理です。

中国の剰余の定理
m1, m2, m3, ... が互いに素な整数のとき 連立合同式
x ≡ r1 mod m1
x ≡ r2 mod m2
x ≡ r3 mod m3
　......
は M = m1 m2 m3 .... を法として一意的な解を持つ。

証明　　 式が 2 個の場合に示せば十分である。 同時に、解 x の求め方も紹介しよう。gcd(m1, m2) = 1 であるから ユークリッド互除法から

s m1 + t m2 = 1

となる整数 s, t を求めることができる。このとき

s m1 = t m2 - 1

は左辺の形から m1 で割り切れ、右辺の形から m2 で割ると余りが 1 となる数であることがわかる。また

t m2 = 1 - s m1

は左辺の形から m2 で割り切れる数で、右辺の形から m1 で割ると余りが 1 となる数である。そこで

N = r1 s m1 + r2 t m2

とすると、これが連立合同式の解の一つとなる。これに m1 m2 の 倍数を加えても連立合同式の解となることは明らかであろう。

ファン・デル・ヴェルデンによれば孫子算経の問題と全く同じ問題が ニコマコス (Nicomachus of Gerasa) の「算術入門」(100 年頃) に登場するが、 現存する 50 個近くの写本のうち、この問題が登場するのは 2, 3 個で 14 世紀にビザンチンの 僧侶の Isaac Argyros によって付け加えられたものでないだろうか、としています。 しかし、それにしても全く同じ問題が登場するのは何か理由があるかもしれません。(共通の起源 ?)

現代の「中国の剰余の定理」の証明及び、連立合同式の解法にはユークリッド互除法が 適用されますが、どのような形で歴史に登場するかをみるにはもう少し別な 準備が必要です。

ディオファントス方程式

2 変数以上の整係数の代数方程式の 整数階を求める問題を ディオファントス (Diophatus) 方程式、あるいは (解が一意的に定まらないため) 不定方程式 という。 ピタゴラス数を求める問題

x2 + y2 = z2

も、このディオファントス方程式の一つです。古来よく考えられたのは a, b, c が整数のとき

線形ディオファントス方程式
a x + b y = c

の整数解を求めることである。 これに関して整理をしておこう。

次が同値である。
  1. a x + b y = c が解を持つ。
  2. a, b の最大公約数が c を割り切る。

証明　　a, b の最大公約数は a x + b y = c の左辺を割り切るから、 右辺の c を割り切る。これで 1 から 2 が示せた。 2 から 1 を示そう。ユークリッド互除法を適用すれば、 d が a, b の最大公約数であれば

a x + b y = d
を満たす整数 x, y を求めることができる。両辺を整数倍すれば求める解が得られます。

a, b の最大公約数 d が 1 より大きければ、a x + b y = c の両辺を d で割り切っておけば よいので最大公約数が 1 の場合に考えればよい。また 1 つでも解 (x, y) = (x0, y0) が見つかれば一般解は次で与えられます (t は整数)。

x = x0 + b t
y = y0 - a t

また線形ディオファントス方程式を a x - c = by の形に書き直せば、 次の連立合同式の問題と同じであることがわかります :

N ≡ - c mod a
N ≡ 0 mod b
アリヤバータ

ここでようやく歴史の話に戻れます。 ファン・デル・ヴェルデンによればインドの天文学者アリヤバータ (Aryabhata, 476 - 550) は不定方程式

a x + c = b y　　　(*)

を次のようにして解きました (話を簡単にするために gcd(a, b) = 1 とします。)

アリヤバータの方法
b を a で割り算して、商を q, 余りを r とします :
b = q a + r
ここで
x = q y + z
と置き、これを (*) に代入する。
a (q y + z) + c = (q a + r) y
両辺から a q y が消えて
r y - c = a z
(*) と同じ形の式となりますが、係数が小さくなっています。これを何度も繰り返して 最終的に
1 v + c' = g w
の形の式に持ち込む。係数に 1 が出てくるのは、左辺の係数のみに着目すれば a, b にユークリッド互除法を適用していることになるからです。また c' は c もしくは -c です。

最後の式で w は任意に選べますが、通常は 0 に選び、 v を決めます。あとは今までの計算の 逆を実行すれば、最終的に (*) の解の一つが求まることになります。

参考
a, b の最大公約数が 1 のとき、a x + b y = 1 を満たす (x, y) を計算機で求めるには ユークリッド互除法を拡張した方法 (拡張されたユークリッド アルゴリズム) が使用されます。 しかし、上のアリヤバータの方法からも、このような (x, y) を計算機で求めることができ、 しかも手順が短いようです。但し、各ステップで出る商を記憶しておく必要があります。

アリヤバータ (あるいはその 100 年後のブラーマグプタ) は不定方程式を 天体の運行計算に利用したようです。ファン・デル・ヴェルデンに詳しい解説が ありますが、ちょっと私では説明できません。 ファン・デル・ヴェルデンは古代のインドの数学あるいは天文学が ヘレニズム文化に由来する可能性を指摘し、またディオファントス方程式を ユークリッド互除法から解くことは、本には書かれなかったが 古代ギリシャあるいはそれ以前から知られていたかもしれないといっています。 だから、これも共通の起源があるかもしれないことになります。