はじめに
ユークリッドの互除法は整数問題を解く上で避けることができないテーマです。
ユークリッドの互除法の使い方をマスターすることで、2つの数の最大公約数を簡単に求めることができるようになります。
この記事でユークリッドの互除法を使いこなせるようにしましょう。
目次
ユークリッドの互除法とは
ユークリッドの互除法とは、2つの自然数の最大公約数を求めるための方法で、
というものです。
具体例とともにまとめると以下のようになります。
最大公約数とは、公約数のうち最大の数のことですね。例えば、21と35の最大公約数は7であり、221と169の最大公約数は13となります。
この最大公約数を求める時に、ユークリッドの互除法を使えば、221と169という大きな数でも最大公約数は13であるというように、最大公約数を求めることができます。
小さな数であれば素因数分解をすることで求めることができますが、大きな数になるとユークリッドの互除法に頼る方が圧倒的に早くなります。
素因数分解を用いる最大公約数の求め方が不安な人は、こちらの記事を見てください。
ユークリッドの互除法のやり方は以下のようになります。具体例と一緒に確認して覚えましょう！
- 2つの数のうち小さい数で大きい数を割り、その余りを求める
- 元の小さい数を(1)で求めた余りで割る
- 2を余りが0になるまで繰り返して最後の余りが最大公約数
このように余りを求める計算を繰り返していくことで、2つの数の最大公約数を求めることができます。
ユークリッドの互除法の証明
整数問題の証明は少し抽象的になって難しいですが、ユークリッドの互除法の証明は2次試験が記述試験でない限り必要ないでしょう。
そのため、2次試験で数学を使わない人は覚えなくても大丈夫です。
しかし、数学を得点源にしたい人はこの機会に理解して覚えてしまいましょう。
ユークリッドの互除法の証明をわかりやすく
最終的に証明したいのは、(a,b)の最大公約数と(b,r)の最大公約数が等しいことです。(rはaをbで割った余り)
そこで、(a,b)の最大公約数が(b,r)の最大公約数以下であり、かつ以上であることを証明します。
(a,b)の最大公約数を\(G_1\)、(b,r)の最大公約数を\(G_2\)とする。
\(a=bp+r\)と表せることより
\(a=a’G_1,b=b’G_1\)と表すことができ
\(r=a-bp=G_1(a’-b’p)\)より
\(G_1\)はbとrの公約数となる。
よって、aとbの最大公約数がbとrの公約数であることが言えるため、
\(G_1≦G_2\)・・・(1)
また、\(b=b’G_2,r=r’G_2\)と表すことができ
\(a=G_2(b’p+r’)\)となる。
よって、\(G_2\)はaとbの公約数となる。
よって、bとrの最大公約数がaとbの公約数であることが言えるため、
\(G_1≧G_2\)・・・(2)
(1),(2)より、\(G_1=G_2\)が成り立つ。
よって、(a,b)の最大公約数と(b,r)の最大公約数が等しい。
これより、紹介した方法を繰り返すと、いずれ余りが0になるのでユークリッドの互除法が成り立ちます。
ユークリッドの互除法の一次不定方程式への応用
「ユークリッドの互除法は最大公約数を見つけるのに便利な手法である」と紹介しましたが、入試で問われることが多いのは一次不定方程式と呼ばれる問題への応用です。
１次不定方程式とは次のような方程式です。
\(ax+by=d\)
例えば、「\(3x+5y=1\)を満たす整数x,yの組を求めよ」といった問題です。
この問題の答えは\((x,y)=(-5k+2,3k-1)(kは整数)\)となります。
つまり、任意の整数kに対して\((x,y)=(-5k+2,3k-1)\)が成り立つということです。
(7,-4)(2,-1),(-3,2)など、特定の整数の組が成り立つことを上のように表現するので覚えておきましょう。
それでは実際に問題を解いてみましょう。
ユークリッドの互除法を用いて不定方程式を解く
ユークリッドの互除法を用いて\(29x-17y=1\)を満たす整数のx,yの組を求めます。
まずこの問題を解くためにこれを満たす整数の組を1つ見つけます。
この組を求めるためにランダムに数字を入れて確かめても良いのですが、数字が大きいと見つけるのは大変なので互除法を利用します。
まず、ユークリッドの互除法を割る数が1になるまで繰り返します。
29=17×1+12
17=12×1+5
12=5×2+2
5=2×2+1
そしてこれを並び変えて
12=29-17×1
5=17-12×1
2=12-5×2
1=5-2×2
を出します。次にそれぞれ下から代入していきます。
1=5-2×2に対して、上の2=12-5×2を代入するので
1=5-(12-5×2)×2=5×5-12×2となります。
次にこれに上の5=17-12×1を代入します。すると、
1=(17-12×1)×5-12×2=17×5-12×7となります。
最後に12=29-17×1を代入します。すると、
1=17×5-(29-17×1)×7=17×12-29×7
よってこれより、(x,y)=(-7,-12)が解の組の1つであることがわかります。
これを代入すると
29(-7)-17(-12)=1
となります。元の式から引くと
29(x+7)-17(y+12)=0となり、整理すると
29(x+7)=17(y+12)となります。
ここで、29と17は互いに素（1以外に公約数を持たない）ので、
x+7=17k(kは整数)と表すことができます。なぜなら右辺より29(x+7)は17の倍数であり、29は17の倍数ではないためです。
よって、x=17k-7
また、29×17k=17(y+12)より
y=29k-12
よって求める整数x,yの組は
(x,y)=(17k-2,29k-12)(kは整数)
と求めることができました。
この問題を解くためのポイントは「方程式をみたす値を見つけること」と、「互いに素であることを利用して文字を用いてx,yを表すこと」です。
運が良ければユークリッドの互除法を利用する前に値を見つけることができますが、値が大きな場合はユークリッドの互除法を利用しましょう。
おわりに
ユークリッドの互除法そのものはそんなに難しいわけではないですが、整数問題は受験生が苦手とする分野で攻略しにくいので注意が必要です。
不定方程式のような馴染みがない問題も出題されますが、演習を繰り返して当たり前のように解けるようにしていきましょう。
約数の個数・総和の求め方についての記事もあわせてご覧くださいね。
