【ユークリッドの互除法】について”わかりやすく”解説!不定方程式の解き方も!

「ユークリッドの互除法」について”わかりやすく”解説!数学A

今回は、「ユークリッドの互除法」を用いた最大公約数の求め方や、
\(49x-23y=1\) のような不定方程式の解き方について、
なるべくわかりやすいように解説しています。


第3章では、「ユークリッドの互除法」の証明もしています。
興味のある人はぜひご覧ください。


スポンサーリンク

1. ユークリッドの互除法

「ユークリッドの互除法」とは

「ユークリッドの互除法」はいつ使うか

ユークリッドの互除法」は、最大公約数を求めるときに使います。


例えば、「\(24\)と\(36\)の最大公約数」は簡単に求めることができると思います。

\(24\)の約数は、\(\{1,2,3,4,6,12,24\}\)

\(36\)の約数は、\(\{1,2,3,4,6,9,12,18,36\}\)

なので、「\(24\)と\(36\)の最大公約数」は\(12\)です。



では、「\(1638\)と\(2100\)の最大公約数」はいくつでしょうか?

先程のように約数を全て求めるというのはなかなか大変だと思います。



そこで登場するのが「ユークリッドの互除法」です。

「ユークリッドの互除法」は数が大きくなっても、簡単に最大公約数を求めることができます。


では、次は「ユークリッドの互除法」の使い方を学んでいきしょう。


「ユークリッドの互除法」の意味

次の定理が「ユークリッドの互除法」です。


ユークリッドの互除法

\(a,b\)を自然数とし、\(a>b\)とする。

\(a,b\) の最大公約数は、次のようにして求めることができる。

  1. \(a\) を \(b\) で割った余り \(r_1\) を求める
  2. \(b\) を \(r_1\) で割った余り \(r_2\) を求める
  3. \(r_1\) を \(r_2\) で割った余り \(r_3\) を求める

以下同様に繰り返し、\(r_{n-1}\) を \(r_n\) で割った余り \(r_{n+1}\) が \(0\) となるとき、\(r_n\) は \(a,b\) の最大公約数に等しい。



何言ってるか全然わかんないよ!!

という人のために、もう少しわかりやすく考えてみましょう。


\(a\)を\(b\)で割った商が\(q_1\)、余りが\(r_1\)のとき、

$$a=b\times q_1 + r_1$$

という関係式が成り立ちますね?


「\(17\)を\(3\)で割った商が\(5\)、余りが\(2\)」 \(\Leftrightarrow \hspace{1em} 17=3\times 5+2\)


同じように、\(b\) を \(r_1\) で割った商を \(q_2\)、余りを \(r_2\) とすると、

$$b=r_1\times q_2+r_2$$

\(r_1\) を \(r_2\) で割った商を \(q_3\)、余りを \(r_3\) とすると、

$$r_2=r_1\times q_3+r_3$$

となります。


これを続けていくと、次のようになります。

  • \(a=b\times q_1+r_1\)  \((0\leq r_1<b)\)
  • \(b=r_1\times q_2+r_2\)  \((0\leq r_2<r_1)\)
  • \(r_1=r_2\times q_3+r_3\)  \((0\leq r_3<r_2)\)
  • \(r_2=r_3\times q_4+r_4\)  \((0\leq r_4<r_3)\)
  • \(\hspace{1.5em}\vdots\)
  • \(r_{n-2}=r_{n-1}\times q_n+r_n\)  \((0\leq r_n<r_{n-1})\)
  • \(r_{n-1}=r_n\times q_{n+1}+0\)


同じことを繰り返しているだけということがわかりますか?


そして、「最終的に余りが \(0\) となったときの、割る数 \(r_n\) が \(a,b\) の最大公約数となる」というのが「ユークリッドの互除法」のです。


まだよくわかんない、、、

という人も多いと思うので、例題をときながら確認してみましょう。


例題

例題1

\(3432\)と\(1482\)の最大公約数を求めよ。


 例題1の解説 

まずは、2つの数を割って、余りを出しましょう。

$$3432 \div 1482 = 2 \ldots 468$$

なので、\(3432\)を\(1482\)で割った余りは\(468\)です。

\(\ldots\)の後ろに余りを書くことにするよ!

商は気にしなくていいんだね!

そしたら、次は\(1482\)を\(468\)で割りましょう。

$$1482 \div 468 = 3 \ldots 78$$

なので、\(1482\)を\(468\)で割った余りは\(78\)です。



さらに、\(468\)を\(78\)で割りましょう。


すると、

$$468 \div 78 = 6$$

となり、余りが\(0\)になりました。


このとき、最後に割った\(78\)が\(3432\)と\(1482\)の最大公約数になります。


(例題1終わり)



スポンサーリンク

2. ユークリッドの互除法と不定方程式

ユークリッドの互除法を使うことで、次のような不定方程式を解くこともできます。


例題2

次の方程式の整数解\(x,y\)を一つ求めよ。

$$49x-23y=1$$

2019年のセンター試験の問題だよ!


 例題2の解説 

まず、\(49\)と\(23\)にユークリッドの互除法を使います。


すると、次のようになります。


  • \(49=23\times 2 +3\)
  • \(23=3\times 7 +2\)
  • \(3=2\times 1 + 1\)


3回目で余りが\(1\)となり、不定方程式の右辺と等しくなりました。


そしたら今度は、ユークリッドの互除法で得た式を、左辺が余りの項だけになるように移行します。


例えば、「\(3=2\times1 +1\)」は、余り\(1\)についての式に変形すると、

$$1=3-2\times 1$$

になります。


他の2式についても同様の操作をすると、

  • \(1=3-2\times 1\)
  • \(2=23-3\times 7\)
  • \(3=49-23\times 2\)

という3つの式が得られます。




そしたら、順番に代入していきましょう。


まず「\(1=3-2\times 1\)」に「\(2=23-3\times 7\)」を代入すると、

$$1=3-(23-3\times 7)\times 1$$

整理すると、

$$1=3\times 8 -23$$

となります。

ここで、\(3\times 8\)は計算せずにそのままにしておこう!


次に「\(3=49-23\times 2\)」を代入します。


すると、

$$1=(49-23\times 2)\times 8 -23$$

となります。


式を整理しますが、\(49\)と\(23\)は計算せずに、そのまま残しておくようにしましょう。


すると、

$$1=49\times 8 -23\times 16 -23$$

すなわち、

$$1=49\times 8 -23\times17$$

となります。



よって、

$$x=8,y=17$$

は不定方程式

$$49x-23y=1$$

の整数解\(x,y\)の一つであることがわかりました!



(例題2終わり)



例題2では、

$$49x-23y=1$$

の解の一つとして、

$$x=8,y=17$$

を得ることができましたが、実際には解は無数にあります。


では、解を全て求めるためにはどうすれば良いのでしょうか?


次の例題を考えてみましょう。


例題3

次の方程式の整数解\(x,y\)を全て求めよ。

$$49x-23y=1$$


 例題3の解説 

「\(49x-23y=1\)」の全ての整数解を求めるためには、まず整数解を一つ見つける必要があります。


例題2で、「\(49x-23y=1\)」の整数解の一つとして、\(x=8,y=17\)を見つけましたね。


つまり、「\(49\times 8 -23\times 17=1\)」となります。


そしたら、2式を引きます。


すると、右辺が打ち消しあって、

$$49(x-8)-23(y-17)=0$$

という式が得られます。



移行すると、

$$49(x-8)=23(y-17)$$

となりますね。


ここで、\(49\)と\(23\)は互いに素なので、

\(x-8\)が\(23\)の倍数

\(y-17\)が49の倍数

とならないと等式が成り立たないですね。


つまり、整数\(k\)を用いて、

\(x-8=23k\) , \(y-17=49k\)

と表せます。


実際に「\(49(x-8)=23(y-17)\)」に \(x-8=23k\) , \(y-17=49k\) を代入すれば、
左辺と右辺が\(49\times 23k\)となり、等しくなることが確認できると思います。


あとは最後に \(x-8=23k\) , \(y-17=49k\) を移行して、

\(x=23k+8\) , \(y=49k+17\)

とすれば、全ての解を表すことができました!

(例題3終わり)



ちなみに、例題3の解の表し方は一通りではありません。


例えば、\(k\) を \(k-1\) に置き換えると、

\(x=23k-15\) , \(y=49k-32\)

となりますが、これも正しい答えです。

\(k\)が全ての整数を動くとき、\(k+1\)や\(k-1\)も全ての整数を動くことができるからだよ!


3. ユークリッドの互除法の原理

この章では、「ユークリッドの互除法の原理」について解説します。

「ユークリッドの互除法の原理」を使えば、「ユークリッドの互除法」の証明をすることもできます。


記号:gcd

ここからは、「\(a\)と\(b\)の最大公約数」を、記号を用いて、

$$\gcd(a,b)$$

で表すことにします。


「\(24\)と\(36\)の最大公約数は\(12\)」 \(\Leftrightarrow\hspace{1em}\gcd(12,36)=12\)

「\(3432\)と\(1482\)の最大公約数は\(78\)」 \(\Leftrightarrow\hspace{1em}\gcd(3432,1482)=78\)

gcdは、最大公約数「greatest common devisor」の頭文字をとっています。

この記号は高校では普通習わないので、覚えなくても大丈夫です。


「ユークリッドの互除法の原理」とは

「ユークリッドの互除法の原理」の意味

ユークリッドの互除法の原理

整数\(a,b\)が整数\(q,r\)を用いて

$$a=bq+r$$

と表されるとする。このとき、

$$\gcd(a,b)=\gcd(b,r)$$

が成り立つ。


「\(51=6\times8+3\)」であるから、

$$\gcd(51,6)=\gcd(6,3)$$

51と6の最大公約数はすぐにはわからないけど、6と3の最大公約数なら、すぐに3ってわかるね!


「\(a=bq+r\)」は剰余の式の形をしていますが、この定理において、余り\(r\)は\(0\leq r<b\)を必ずしも満たす必要はありません。


例えば、

$$51=6\times8+3$$

とするところを、

\(51=6\times 7 +9\) や \(51=6\times 9 -3\)

としても、この定理は成り立ちます。


「ユークリッドの互除法の原理」の証明

\(\gcd(a,b)=g_1\) , \(\gcd(b,r)=g_2\) とする。


\(\gcd(a,b)=g_1\) より、\(a\) と \(b\) はともに \(g_1\)の倍数である。


\(a=bq+r\)より、\(r=a-bq\) である。


\(a\) , \(b\) がともに \(g_1\) の倍数で、\(q\) は整数であるから、

\(r=a-bq\) も \(g_1\) の倍数である。


つまり、\(b\) と \(r\) は \(g_1\) の倍数であるから、

言い換えると、\(g_1\)は \(b\) と \(r\) の公約数である。


\(b\) と \(r\) の公約数のうち、最大のものが \(g_2\) であるから、

$$g_1\geq g_2$$

が成り立つ。



一方、\(\gcd(b,r)=g_2\) より、\(b\) と \(r\) はともに \(g_2\)の倍数である。


\(b\) , \(r\) がともに \(g_2\) の倍数で、\(q\) は整数であるから、

\(a=bq+r\) も \(g_2\) の倍数である。


つまり、\(a\) と \(b\) は \(g_2\) の倍数であるから、

言い換えると、\(g_2\)は \(a\) と \(b\) の公約数である。


\(a\) と \(b\) の公約数のうち、最大のものが \(g_1\) であるから、

$$g_2\geq g_1$$

が成り立つ。


よって、「\(g_1\geq g_2\)」かつ「\(g_2\geq g_1\)」であるから、

$$g_1=g_2$$

すなわち、

$$\gcd(a,b)=\gcd(b,r)$$

が示された。

(証明終わり)


「ユークリッドの互除法」の証明

「ユークリッドの互除法の原理」を使うことで、「ユークリッドの互除法」を証明することができます。


「ユークリッドの互除法」を使うことで、次のような式が成り立つことは第1章で説明しました。

  • \(a=b\times q_1+r_1\)  \((0\leq r_1<b)\)
  • \(b=r_1\times q_2+r_2\)  \((0\leq r_2<r_1)\)
  • \(r_1=r_2\times q_3+r_3\)  \((0\leq r_3<r_2)\)
  • \(r_2=r_3\times q_4+r_4\)  \((0\leq r_4<r_3)\)
  • \(\hspace{1.5em}\vdots\)
  • \(r_{n-2}=r_{n-1}\times q_n+r_n\)  \((0\leq r_n<r_{n-1})\)
  • \(r_{n-1}=r_n\times q_{n+1}+0\)


このとき、余りに注目すると、

$$b>r_1>r_2>\cdots>r_{n-1}>r_n>\cdots\geq 0$$

となっていることがわかります。


つまり、ユークリッドの互除法の操作を繰り返すたび、余りは0に向かってどんどん小さくなります。


そして、このとき、「ユークリッドの互除法の原理」から、

\(\gcd(a,b)=\gcd(b,r_1)\)
\(\hspace{4em}=\gcd(r_1,r_2)\)
\(\hspace{4em}=\gcd(r_2,r_3)\)
\(\hspace{4em}=\gcd(r_3,r_4)\)
\(\hspace{5em}\vdots\)
\(\hspace{4em}=\gcd(r_{n-2},r_{n-1})\)
\(\hspace{4em}=\gcd(r_{n-1},r_n)\)
\(\hspace{4em}=r_n\)

となります。

\(r_{n-1}=r_nq_{n+1}\)だから、\(\gcd(r_{n-1},r_n)=r_n\)だね!

よって、\(\gcd(a,b)=r_n\)より、「ユークリッドの互除法」が証明されました。

数学A整数の性質
スポンサーリンク
OchibaAtsuoをフォローする
ますますmathが好きになる!魔法の数学ノート

コメント

タイトルとURLをコピーしました