整数の性質|ユークリッドの互除法について

数学A

ユークリッドの互除法

ユークリッドの互除法とは、割り算と最大公約数の間に成り立つ定理を利用して、2つの自然数 $a \ , \ b$ の最大公約数を求める方法のことです。先程の定理を実際に利用する方法と考えると良いでしょう。

ユークリッドの互除法では、$a$ と $b$ の最大公約数は、$b$ と $r$ の最大公約数に等しくなることを利用して、割り算を繰り返し行います。

ユークリッドの互除法

$a \div b$ から余り $r$ を求めたら、次は $b \div r$ から余りを求めます。このように割り算を余りが0になるまで繰り返します。

たとえば、24と9の最大公約数を求めてみましょう。まず24÷9を計算します。余りが6になるので、次は9÷6を計算します。余りが3になるので、さらに6÷3を計算します。余りが0になるので、これで割り算を終了します。余りが0になるときの割る数(除数)3が24と9の最大公約数になります。

ユークリッドの互除法を使った計算

この計算で分かるのは、最大公約数を求めるために、24と9から直接求めるのではなく、できるだけ小さな2つの自然数(ここでは6と3)に置き換えて間接的に求めているということです。これは割り算と最大公約数の間に成り立つ定理があるからできることです。

24と9の最大公約数は、6と3の最大公約数を求めれば良い。
(24と9の最大公約数)
= (9と6の最大公約数)
= (6と3の最大公約数)

難しく感じるかもしれませんが、式を書いていくと、2つの数が横にスライドするだけだと分かります。ですから、要領さえ掴んでしまえば、あとは機械的に計算することができるようになります。

また、実際に筆算して解くこともできます。後で学習する不定方程式には使いにくいですが、単に最大公約数を求めるだけなら筆算の方が解きやすいでしょう。

ユークリッドの互除法の計算(筆算)

24÷9を計算して余りを求めます。余り6で9を割るので、9の左側に6を書き、9÷6の余りを求めます。余り3で6を割るので、6の左側に3を書き、6÷3の余りを求めます。余りが0になるので、このときの割る数(除数)3が24と9の最大公約数になります。

この筆算では、余りが次の割り算の割る数(除数)になるので、左から右へ割り算していきます。

例では2つの自然数がわりと小さな数でしたが、実際はもっと大きな数を扱うので、筆算での求め方をマスターしておいた方が良いでしょう。

次はユークリッドの互除法を扱った問題を実際に解いてみましょう。

ユークリッドの互除法を扱った問題を解いてみよう

次の問題を解いてみましょう。


270と42の最大公約数をユークリッドの互除法を用いて求めよ。

問の解答・解説

最大公約数の求め方には、2つの数をそれぞれ素因数分解して求める方法を学習しましたが、問ではユークリッドの互除法で解くように指定されています。素因数分解せずに、ユークリッドの互除法を用いて解きます。

問の解答例
\begin{align*}
&270 \div \underline{42} = 6 \ \text{余り $\underline{\underline{18}}$} \\[ 5pt ]
&\underline{42} \div \underline{\underline{18}} = 2 \ \text{余り $\underline{6}$} \\[ 5pt ]
&\underline{\underline{18}} \div \underline{6} = 3 \ \text{余り $\underline{\underline{0}}$} \\[ 5pt ]
&\text{よって、$270$ と $42$ の最大公約数は $6$}
\end{align*}

割る数(除数)を次の割り算の割られる数(被除数)に、余りを次の割り算の割る数(除数)にして割り算を繰り返します。余りが0になったときの割る数(除数)が270と42の最大公約数です。

解答例から分かるように、270と42の最大公約数を直接求めるのではなく、6と3の最大公約数から間接的に求めています。

270と42の最大公約数は、18と6の最大公約数を求めれば良い。
(270と42の最大公約数)
= (42と18の最大公約数)
= (18と6の最大公約数)

また、筆算で解くと以下のようになります。余りが次のわり算の割る数(除数)となるので、最初のわり算をできるだけ右側に記述しましょう。数題解けば要領を掴めるので、集中的に演習をこなしましょう。

ユークリッドの互除法を扱った問題の別解例

最大公約数の求め方としては、素因数分解を利用する解法が一般的かもしれません。ただ、整数問題では余りに注目する問題が意外と多いので、余りに関わる解法の1つとしてユークリッドの互除法も使えるようにしておきましょう。

Recommended books

整数の性質を扱った問題は、難関大なら必修でしたが、センター試験でも扱われるようになりました。

難しく感じる人もいるかもしれませんが、複雑な公式や図形を扱うことがないので、その気になれば得点源にできる単元です。単元別の問題集で集中的に取り組んでマスターしましょう。

これから紹介する教材で気になるものがあれば、ぜひ一読してみて下さい。気に入ったら最後まで徹底的にこなしましょう。

オススメその1

『[affi id=53]』は、教科書レベルから始めて大学入試の実戦レベルまで、最大効率で習得できる問題集です。新課程の整数問題に対応しています。問題数が47題なので、短期間でこなしたいなら候補に入れて良いでしょう。

【教科書編】
問題数16題。新課程版教科書「整数の性質」の項目に沿って配置。
教科書編項目:約数と倍数/約数の個数と総和/最大公約数と最小公倍数/剰余による分類/ユークリッドの互除法とディオファントス方程式/p進法/循環小数/合同式/部屋割り論法

【実戦問題のレベル別編】
初級編20題、中級編5題、上級編6題。
難関大学の整数問題に十分対処できるようにすることを目標として作成。
できる限り数学1・数学Aの範囲にとどめるように問題を選択。
ただし、二項定理・高次の多項式の因数分解・数列の問題あり。

数学1・Aの範囲内にとどめるように配慮されているおかげで、数学1・Aの学習直後から取り組めます。学習したてなら苦手意識がつく前なので、スムーズに取り組めるでしょう。

[affi id=54]

オススメその2

『[affi id=55]』は、頻出かつ重要な問題について、例題だけでなく、類題もあるので演習量をこなせる問題集です。解答例や解説は、高校までに学んだ知識だけで理解できるように配慮されているので、数学が苦手な人にも取り組みやすくなっています。

また、力試しの問題も収録されているので、最後の仕上げに取り組むと良いでしょう。定石を身に付けつつ、入試を想定した問題を解いてみたいのなら候補に入れて良いでしょう。

[affi id=56]

オススメその3

『[affi id=57]』は、教科書レベルから難関大学対策までに対応した参考書兼問題集です。基本事項では、具体例をあげながら解説されているので、イメージしやすいでしょう。文系で数学を必要とする人にも向いています。

また、大学入試レベルの問題では、実際に解くときの考察手順が詳細に記載されているので、自分のアプローチのやり方と比較することができます。整数についての知識が足りなくて、問題を解くには早いと考えているのなら候補に入れて良いでしょう。

[affi id=58]

オススメその4

『[affi id=59]』は、初歩・基本のレベルから発展的レベルまでを幅広く解説した参考書兼問題集です。4部構成ですが、大学受験対策としては、第3部を重点的に取り組むと良いでしょう。

第1部:中学上位生~高1・2年生が興味をもって無理なく取り組める系統別の問題演習。
第2部:整数、場合の数それぞれの重要手法のイメージ化に重点をおいて詳しく解説。
第3部:大学受験問題の系統だった解説。
第4部:興味深い問題・発展演習。

少し難易度の高い教材ですが、難関大を目指す理系志望者なら候補に入れて良いでしょう。

[affi id=60]

さいごにもう一度まとめ

  • 整数を商と余りを使って表せるようになろう。
  • 2つの自然数の最大公約数と、割る数(除数)と余りの最大公約数に等しいことを理解しよう。
  • ユークリッドの互除法は、できるだけ小さな2数を使って最大公約数を求めるための方法。
  • ユークリッドの互除法は、1次不定方程式にも応用されるので、手順をマスターしておこう。