ユークリッドの互除法の例題と証明：最大公約数を簡単に求める方法

ユークリッドの互除法は、2つの数の最大公約数を求める方法です。

例題

1080と312の最大公約数を求めなさい。

1080 ÷ 312 = 3 ... 144
312 ÷ 144 = 2 ... 24
144 ÷ 24 = 6 ... 0

→最大公約数は24

まず1080を312で割って余りを求めます。余りは144です。

次に312を144で割って余りを求めます。余りは24です。

つまり「前のステップで割ったものを、前のステップで得られた余りで割る」という手順をくりかえすのです。これを余りが0になるまでくりかえします。1080と312では24で割るところで余りが0になるので、最大公約数は24となります。

高校の教科書や参考書の説明は上の通りですが、ユークリッドの互除法は最大公約数を記号化することでよりわかりやすくなります。数学では最大公約数をカッコで表します。例えば24と36の最大公約数は次のように表します。

(24, 36)

24と36の最大公約数は12であり

(24, 36) = 12

となります。「24と36の最大公約数」と「36の24の最大公約数」は同じなので

(24, 36) = (36, 24)

となります。ひっくり返しても同じということです。これを最大公約数の交換法則といいます。以上を前提にして1080と312の最大公約数をユークリッドの互除法で求めてみましょう。

(1080, 312)
= (144, 312) ... ☆
= (312, 144)
= (24, 144) ... ☆
= (144, 24)
= 24

☆のところで1080を144、312を24にしていますが、これは割られるものを余りに置きかえているだけです。「割られるものを余りに置きかえて、交換法則を使ってひっくり返す」というステップをくりかえしていることがわかります。

3120と968の最大公約数を求めなさい。

3120 ÷ 968 = 3 ... 216

(3120, 968)
= (216, 968)
= (968, 216)
= (104, 216)
= (216, 104)
= (8, 104)
= 8

8が最大公約数です。

最初の例題で出てきた☆のステップが「ユークリッドの互除法」の本質です。

(1080, 312) = (144, 312) ... ☆

1080 ÷ 312 = 3 ... 144

次の命題を証明すればいいことになります。

(a, b) = (r, b)

a ÷ b = q ... r

aとbの公約数の集合がrとbの公約数の集合の等しいことを示す。そのために次の２つを証明する。

①aとbの公約数はすべて、rとbの公約数である

aとbの公約数をnとすると

a = cn
b = dn

という整数cとdがある。

r
= a - bq
= cn - dnq
= n(c - dq)

となるのでnはrの約数である。つまりaとbの公約数はすべて、rとbの公約数である。

②rとbの公約数はすべて、aとbの公約数である

rとbの公約数をmとすると

r = cm
b = dm

という整数cとdがある。

a
= b × q + r
= dmq + cm
= m(dq + c)

となるのでmはaの約数である。つまりrとbの公約数はすべて、aとbの公約数である。