中学の数学 (11) ユークリッドの互除法の証明

2024年4月21日 17:25

今日学ぶこと

ユークリッドの互除法がなぜ成り立つか説明できる。

a を b で割るとき，次のように書くことができます。

$$
a = b \times p + r
$$

p が商，r が余りです。

a, b の最大公約数は，b , r の最大公約数と同じです。

ユークリッドの互除法はこの性質を利用して，a, b の最大公約数を探す方法です。

しかし，なぜ，a, b の最大公約数が，b , r の最大公約数と同じといえるのでしょうか？

まず，a, b の最大公約数を m とします。

$$
a = b \times p + r
$$

すると，a は m で割り切れます。a とイコールである $${b \times p + r}$$ も m で割り切れるのですから，b や r も m で割り切れるはずです。

とすると，b も r も m を約数にもつはずです。

b と r の最大公約数をnとおくと，m と n の関係は次のようになります。

$$
m \leq n
$$

b と r は約数に m をもっていますが，それが最大の約数であるかどうかはわかりません。しかし，n が m より小さいことはあり得ませんから，今のところ，次のように書くことができます。

$$
m \leq n
$$

$${a = b \times p + r}$$ を移項すると次のように書けます。

$$
r = a - b \times p
$$

b と r の最大公約数を n とおきました。ですから，rは n で割ることができます。

n とイコールである $${a - b \times p}$$も n で割ることができます。a や b も n で割ることができる，つまり，a や b は約数に n をもちます。

$$
n \leq m
$$

n が m より大きいことはありません。m は a と b との最大公約数です。n が m より大きいと，r と b は共通の最大の公約数をもたないことになってしまうからです。

ここで　n と m について二つの関係式が得られました。

$$
m \leq n \\
n \leq m
$$

このふたつが共に成り立つ場合は，$${m = n}$$ のときです。

aとbの最大公約数m はbとr の最大公約数n と一致することがわかりました。

うーん，むずかしい。もっと簡単に説明する方法がありそうなものだ。