ユークリッドの互除法を使って最大公約数を求めます

 『学び直し講座』序盤の山場です。初等数論の花形ともいえる ユークリッドの互除法 について学びましょう! 本当に初歩的な算数の知識だけで、実に見事な理論が展開されます。楽しんでください!

ユークリッドの互除法

 72 と 56 の最大公約数を求めます。
 最大公約数を 2 次元で視覚化してみましょう。

 ユークリッドの互除法説明図

 横が 72, 縦が 56 の長方形です。作業は簡単です。
 まず、この長方形からなるべく大きな正方形ができるように切込みを入れます。
 1辺の長さ 56 の青い正方形が1つとれましたね。
 もとの長方形の辺の長さを、この青い正方形の1辺を使って表すと、

72 = 56 × 1 + 16

となります。今度は青い正方形を切り離してしまって、右側の細長い長方形からなるべく大きな正方形がとれるように切込みを入れます。1辺の長さ 16 赤い正方形が 3 つとれます。式で表すと、

56 = 16 × 3 + 8

です。残ったのは1辺の長さ 16 の緑色の長方形で、これは

16 = 8 × 2

と 2 つに分けることができます。もとの長方形は1辺が 8 の正方形タイルできれいに敷き詰めることができます。つまり 72 と 56 の最大公約数は 8 だということです。これが最大公約数の図形的な意味です。上の計算式をまとめて書いてみます。

  72 = 56 × 1 + 16

  56 = 16 × 3 + 8

  16 = 8 × 2  ∴ 8 が最大公約数

 もう少し簡略化して書くと、

  72 ÷ 56 = 1 [余り 16]

  56 ÷ 16 = 3 [余り 8]

  16 ÷ 8 = 2  [余り 0]  ∴ 8 が最大公約数

というように計算します。除数(割る数)を余りで割ることの繰返しですね。それでは問題でいくつか練習してみましょう。

問題①

 460 と 380 の最大公約数を求めてください。

問題①の解答

 「割る数」を余りで割っていくのです。

  460 ÷ 380 = 1 [余り 80]

  380 ÷ 80 = 4  [余り 60]

  80 ÷ 60 = 1  [余り 20]

  60 ÷ 20 = 1  [余り 0]  ∴ 20 が最大公約数

 最後に割り切れたときの除数が最大公約数 です。間違えないように!

問題②

 1890 と 150 の最大公約数を求めてください。

問題②の解答

  1890 ÷ 150 = 12 [余り 90]

  150 ÷ 90 = 1   [余り 60]

  90 ÷ 60 = 1   [余り 30]

  60 ÷ 30 = 2   [余り 0]  ∴ 30 が最大公約数

 大きな数ほど ユークリッドの互除法 は威力を発揮します。割り算の練習にもなりますので、最大公約数を求める問題に出会ったときは、とりあえずユークリッドの互除法で計算して訓練を積んでください。

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。