家庭教師が教える、やさしすぎる高校数学　～ユークリッドの互除法～　

私は家庭教師としては、小中学生を教えることが多い。ただ、妹は現在高1なので、たまに高校の勉強を見ることがある。受験勉強をやっていた時代は遥か4年前なので、もはや忘れかけているが、時々思い出してみるのもよい頭の体操になるものだ。

さて、「ユークリッドの互除法」というのをご存じだろうか。ユークリッドの互除法は最大公約数を求める手法だ。妹の試験勉強の範囲になっていたという安直な理由で、今回はこれを誰でも簡単にわかるように説明してみたいと思う。

公約数とは、2つ以上の自然数を選んだ時に、それらを共通に割れる数であり、最大公約数とは、公約数の中で最大なものだ。ちなみに公約数は英語で Common Divisor であり、その中で最大=Greatな最大公約数は、Great Common Divisor である。だから最大公約数はGCDと略されることがよくある。なんかかっこいいよね。

ユークリッドの互除法はとっても簡単。ただただ余りを計算していくだけだ。ここでは例として、39と15のGCDを考えてみよう。

まず2つの数のうち小さい方で大きい方を割ってみる。

39÷15=2 余り 9

そうしたら、割る数だった15を割られる数にして、余りの9で割る。

15÷9=1 余り 6

また、割る数だった9を割られる数にして、余りの6で割る。

9÷6=1 余り 3

また、割る数だった6を割られる数にして、余りの3で割る。

6÷3=2 あまり 0　

余りが0になったら終了だ。

この時、最大公約数は0の手前で出ていた余り=3になる。

ちょっと複雑に思えるかもしれないが、実はそんなに難しくない。手を動かして計算してみると、そのうち慣れてくる。同じ操作を繰り返しているだけなのだ。こういうのを再帰的（英語ではRecursive）という。プログラミングをやっている人にはなじみ深いだろう。

では、なぜこの方法で最大公約数が求められるのだろうか。色々証明があるのだが、なかなか「誰でもわかる」というのは難しい。

今回は厳密ではないかもしれないが、イメージしやすい方法で説明を試みてみよう。

例として用いた39と15の場合で考える。

39と15の最大公約数を□とすると、15は□の倍数なので、もちろん30も□の倍数だ。39も□の倍数だから39-30=9 も□の倍数だ。

ここがわかりにくければ、九九を考えてみるとよい。例えば、4×3=12と4×7=28はどちらも4の倍数なので、28-12=16も4の倍数になる。同様に□の倍数同士の差は□の倍数になるのだ。

ここまでで、9が□の倍数だという事がわかったが、この9は実は、39÷15の余りだ。39のなかに15は2つ入っていて、その残りが9になっているというわけだ。

このことから、15も9も□の倍数なので、そのような□は15と9の公約数だといえる。その中で最も大きいものが最大公約数なので、39と15の最大公約数=15と9の最大公約数となるのだ。これがユークリッドの互除法の本質である。

続いて、15と9についても同様に、15-9=6も□の倍数となる（15の中に9は1つだけ入るのでこれでよい）。なので、9も6も□の倍数であり、□は9と6の公約数だ。9と6の最大公約数が、求めたい39と15の最大公約数になっている!

同様に、9-6=3も□の倍数となる（9の中に6は1つだけ入るのでこれでよい）。なので、6も3も□の倍数であり、□は6と3の公約数だ。6と3の最大公約数が、求めたい39と15の最大公約数になっている!

こうなれば、最後は6は3で割り切れる。ということは、6と3の最大公約数は3である。3の約数のうち、最も大きいものは3自身なので、これが3より大きい6の約数ならば、3がすなわち6と3の最大公約数になるのだ。

ただ余りを出して割っていくだけで自動的に最大公約数が求められるユークリッドの互除法。良ければ紙とペンを用意して、その面白さを体験してはどうだろうか。

ではここから、まだまだいけそうな方向けに、続きを書く。

最大公約数がわかったら、最小公倍数も求めたくなるだろう。

公倍数とは、2つ以上の自然数を選んだ時に、それらの共通の倍数であり、最小公倍数とは、公倍数の中で最小のものだ。ちなみに公倍数は英語で Common Multiple であり、その中で最小=Leastな最大公約数は、Least Common Multiple である。だから最大公約数はLCMと略されることがよくある。なんかかっこいいよね。（デジャヴ感）

実は、2つの自然数の場合、それらの積が、最大公約数と最小公倍数の積となる。なので、元の自然数同士を掛け算して、それを最大公約数で割れば、最小公倍数が求められる。

今回の例で言えば、

39×15=3×（最小公倍数）となっており、

最小公倍数＝39×15÷3=195 である。

では、なぜこうなるのだろうか。これも厳密ではないが、簡単に説明してみたい。

今回求めた最大公約数3を用いると、39と15は次のように表すことができる。

39=3×13
15=3×5

このとき大事なことは13と5には公約数が1しかないということだ。これを「13と5は互いに素である」と表現する。これは当たり前で、もしも13と5に1以外の公約数があったら、39と15の最大公約数は3ではなく、3にその約数をかけたものになっていなければならないからだ。

さて、最小公倍数は、39と15の公倍数の中で最小のものだ。ということは、何か「なるべく小さい数」を掛け算することで2つの数字を同じにしなければならない。

そうすると、39×5=15×13が見えてくるのではないだろうか。

つまり、

39×5=3×13×5
15×13=3×5×13

というわけだ。

頑張って探してみても、13と5には公約数が1以外ないので、これ以上小さい公倍数は存在できない！

よって最小公倍数は3×5×13=195なのだが、ここでもともとの2つの自然数、39と15の積である、

39×15=3×13×3×5

に注目だ。

この計算では、最小公倍数を求める計算と比べて、3が1つ余計にかけられていることがわかる。よって、この分を割ってやれば、最小公倍数が求められることがわかる。

ここでやっと、39×15÷3で最小公倍数が求められることが示せた！！

長くなったので今回はこの辺で。

最後に、プログラムの練習がてら、ユークリッドの互除法で最大公約数と最小公倍数を計算するプログラムを（今回は2つの自然数の場合を考えたが、複数対応で）作成したので添付しておく。（趣味枠、見る必要はありません）

言語はFortran90である。（研究室で使っているんだ、許せ！！）

program gcd_lcm
    implicit none
    integer::i,n
    integer(kind=8),allocatable::x(:)
    integer(kind=8)::temp,gcd,lcm 
    !I/O files
    open(1,file='input.txt')
    open(2,file='output.txt')
    read(1,*);read(1,*)n !計算する数値数を読み込み
    allocate(x(n))       !計算する数値数の配列を生成
    !全ての数値を読み込み
    read(1,*)
    do i=1,n
        read(1,*)x(i)
    end do
    gcd=x(1);lcm=x(1)
    do i=1,n-1
        !最大公約数計算
        call euclid(gcd,x(i+1)) 
        !最小公倍数計算
        temp=lcm
        call euclid(temp,x(i+1))
        lcm=lcm*x(i+1)/temp
    enddo
    !出力
    write(2,*)'最大公約数は',gcd
    write(2,*)'最小公倍数は',lcm
    close(1);close(2)
    stop
    
    contains
    
    subroutine euclid(a,c) !ユークリッドの互除法を行うサブルーチン
    implicit none
    integer(kind=8),intent(inout)::a !返すのはaの値だけ
    integer(kind=8),intent(in)::c
    integer(kind=8)::b,r
    b=c !intent(in)は値を変えられないのでbに置換
    do while (r/=0)
        r=mod(a,b)
        a=b
        b=r
    end do
    end subroutine euclid
    end program gcd_lcm