Up ユークリッドの互除法
更新: 2014-07-18


    整数比の2数は,試行錯誤的に物を操作して求めるしかないように,一見思われる。
    しかしそうではない。
    整数比を求める手順がある。
    言い換えると,分数を値とするきちんとした測定法がある。
    それが,「ユークリッドの互除法」である。

    以下に,この操作と,この操作の連分数表現を,並べて示す:

    (1) 分数で何倍か?

    (2) a1 が a2 にいくつ入るか?──2つ入って余り a3 がでる。

    (3) a3 が a1 にいくつ入るか──1つ入って余り a4 がでる。

    (4) a4 が a3 にいくつ入るか── 2 つ入って余りなし。

    (5) 最後の余り a4 が最初の a1, a2 にそれぞれいくつ入るかが,
      計算で求められる──3と8 :

    (6) 求める分数倍は 8/3。

    ユークリッドの互除法を使うと,つぎの両方が同時に得られる:
    • 二量の共約量(しかも最大共約量)
    • 分数の値(しかも既約分数)