2019年02月04日更新
ユークリッドの互除法の計算・証明・大学入試レベルの問題を徹底解説!
ユークリッドの互除法は大学入試の頻出テーマ、一次不定方程式の整数解を求める問題で欠かせない知識です。近年もセンター試験や医学部入試などで出題されているので、大学合格のためにも本記事で基本をマスターしてください!

ユークリッドの互除法って?

ユークリッドの互除法とは2つの自然数の最大公約数を求める手法です。


実際の手順を説明する前に『最大公約数』についておさらいしておきましょう。

最大公約数について理解しているのであれば、次項を読み飛ばしてもOKです。

最大公約数とは

最大公約数とは2つ以上の自然数に共通する最大の約数のことです。

約数はある数を割り切れる数を指しますね。


最大公約数の求め方は覚えていますか?

覚えていない方は次の例題をご覧ください。


【例題】

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


【解答】

まず、「6」を割り切れる数(=約数)を書き出します。

$$\begin{align}\bf \Rightarrow\left[1,2,3,6\right]\end{align}$$

次に、「9」を割り切れる数を書き出します。

$$\begin{align} \bf \Rightarrow\left[1,2,3,9\right]\end{align}$$

2つの数の約数を比較した時、公約数(共通する約数)は

$$\begin{align}\bf\left[1,2,3\right]\end{align}$$

ですね。

最大公約数は公約数のなかで一番大きい数なので、

6と9の最大公約数は「3」です。


一ケタか二ケタの数の最大公約数を求める問題であれば、今回のようにそれぞれの約数を書き出せば簡単に解けます。


しかし、「3231と2853の最大公約数」といったようにもとの数が大きい場合は約数を書き出す解き方だとかなり手間がかかりますよね?


その手間をかけずに大きい数字どおしの最大公約数を出せるのがユークリッドの互除法なんです。

ユークリッドの互除法の使い方

ユークリッドの互除法では商と余りの関係を利用します。

では、「3231」と「2853」の最大公約数をユークリッドの互除法で求めてみましょう。


【1】大きい数を小さい数で割る場合の商と余りの関係式を作る。

$$\begin{align}3231=2853\cdot1+378\end{align}$$

【2】割る数(2853)を余り(378)で割る場合の関係式を作る。

$$\begin{align}2853=378\cdot7+207\end{align}$$

【3】【2】と同様の計算を余りが出なくなる(割り切れる)まで続ける。

$$\begin{align}378=207\cdot1+171\end{align}$$
$$\begin{align}207=171\cdot1+36\end{align}$$
$$\begin{align}171=36\cdot4+27\end{align}$$
$$\begin{align}36=27\cdot1+9\end{align}$$
$$\begin{align}27=\color{red} {9}\cdot3\end{align}$$

【4】最後の式の「割る数」が2つの数の最大公約数となる。

最後の式の「割る数」は9なので、3231と2853の最大公約数は9です。

いかがでしょうか?

それぞれの約数を出していく方法よりもずっと簡単ですよね。


ひとつ前の式の「割る数」が次の式の「割られる数」、「余り」が「割る数」へと移動する手順を視覚的にとらえるとこんなかんじです。

視覚的に式の作り方を覚えておくと忘れづらくなるので、ユークリッドの互除法をマスターするまでは上の画像のように矢印を書いて問題を解く練習をするといいですよ。

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

ユークリッドの互除法を文字を使って表現すると、このように説明できます。


『2つの自然数A,B(A≧B)について、AをBで割った時の余りをrとすると

AとBとの最大公約数はBとrとの最大公約数に等しい


「aとbの最大公約数がbとrの最大公約数に等しい」という命題を証明できれば、ユークリッドの互除法が成り立つといえますね。


証明自体が大学入試で問われることはありませんが、どうやって証明していくか知ることはとて大切なので、以下の証明に目を通しておいてください。


拡張ユークリッドの互除法(一次不定方程式への応用)

ユークリッドの互除法が大学入試において一番活躍するのが一次不定方程式の問題です。


一次不定方程式の問題は大学入試でよく出題されますが、解き方がわからない生徒が意外と多く、大学によっては点差が分かれる問題とされています。


しかし、解き方の手順さえ覚えてしまえば何も難しいことはないので、ぜひこの機会にマスターしてくださいね。


【例題】

$$\begin{align}11x+15y=1 を満たす整数(x,y)を1組求めてください。\end{align}$$

【解答】

まず、xとyの係数について互除法を使います。

$$\begin{align}15=11\cdot1+4…①\end{align}$$
$$\begin{align}11=4\cdot2+3…②\end{align}$$
$$\begin{align}4=3\cdot1+1…③\end{align}$$

次にそれぞれの式を余りについて整理します。

$$\begin{align}1=4-3\cdot1…③´\end{align}$$
$$\begin{align}3=11-4\cdot2…②´\end{align}$$
$$\begin{align}4=15-11\cdot1…①´\end{align}$$

ここから③´に②´、①´を順に代入していき、与式に近づけていきます。

$$\begin{align}1=4-\color{red} {3}\cdot1\end{align}$$
$$\begin{align}=4-\color{red}{(11-4\cdot2)}\cdot1\end{align}$$
$$\begin{align}=\color{blue}{4}\cdot3-11\end{align}$$
$$\begin{align}=\color{blue}{(15-11\cdot1)}\cdot3-11\end{align}$$
$$\begin{align}=-11\cdot3-11+15\cdot3\end{align}$$
$$\begin{align}=\bf 11\cdot(-4)+15\cdot3…☆\end{align}$$

与式のx,yの係数と同じ数字で式を整理できましたね。

与式にx=-4,y=3を代入すれば☆になるので、

$$\begin{align}答えは \bf (x,y)=(-4,3) になります。\end{align}$$

「ax+by=1を満たす(x,y)を求めよ」ときたら、


①x,yの係数について互除法を使う。

②余りについて式を整理する。

③②で作った最後の式に他の余りについての式を順に代入する。

④与式に近づける。


という手順を踏めば答えを求められることを覚えておきましょう。

何度か同じような問題を解けば、簡単にマスターすることができますよ!

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

では、実際に問題を解いていきましょう。


1問目はセンター試験の類似問題、2問目は医学部入試でも出題された問題の簡易版です。


どちらも自力で解けるようになったら、ユークリッドの互除法を使う問題で戸惑うことはなくなりますよ!

問題1

不定方程式

$$\begin{align}89x+189y=1\end{align}$$

を満たす整数x,yの組で、xの絶対値が最小のものを求めてください。

【解答】

まずはユークリッド互除法を使って整数x,yの組を1組求めます。

$$\begin{align}189=89\cdot2+11\end{align}$$
$$\begin{align}89=11\cdot8+1\end{align}$$

これらの式を余りについて整理すると

$$\begin{align}1=89-11\cdot8\end{align}$$
$$\begin{align}11=189-89\cdot2\end{align}$$

よって

$$\begin{align}1=89-11\cdot8\end{align}$$
$$\begin{align}=89-(189-89\cdot2)\cdot8\end{align}$$
$$\begin{align}=89-(189-89\cdot2)\cdot8\end{align}$$
$$\begin{align}=89+89\cdot16-189\cdot8\end{align}$$
$$\begin{align}=89\cdot17+189\cdot(-8)\end{align}$$

以上より、題意を満たすx,yの組は(x,y)=(17,-8)とわかりました。

次に、「xの絶対値が最小のもの」について考えていきましょう。


xの絶対値が最小のものを求めるには、まず整数x,yの一般解を求める必要があります。


一般解を求めるための式はこちら。


(与えられたx,yの式)-(1つの解を代入した式)


これはまるっとそのまま覚えておいてくださいね。

$$\begin{align}89x+189y=1…①(与えられたx,yの式)\end{align}$$
$$\begin{align}89\cdot17+189\cdot(-8)=1…②(1つの解を代入した式)\end{align}$$

①-②より

$$\begin{align}89(x-17)+189(y+8)=0…☆\end{align}$$

89と189は互いに素なので

$$\begin{align}x-17=189k,y+8=89k ※kは任意の定数\end{align}$$

とおくことができます。

$$\begin{align}x-17=189kより\end{align}$$
$$\begin{align}x=17+189k\end{align}$$

kが0のとき、xの絶対値は最小となるので求めるx,yの組は

$$\begin{align}\bf (x,y)=(17,-8)\end{align}$$

とわかりました。

問題2

次の分数を約分して既約分数を求めてください。

$$\begin{align}\frac{899}{957}\end{align}$$

【解答】

「既約分数ってなんだっけ?」と思った方、要注意ですよ。


大学入試に向けて難しい問題ばかり解いていると基礎知識を忘れがちですが、既約分数を求める問題は大学入試でもたまに出ます。


既約分数は簡単に言えばこれ以上約分できない分数のことです。


そして、与えられた分数の数分母、分子の数が大きい場合はユークリッドの互除法を用いると簡単に既約分数を求めることができます。

分母・分子にユークリッド互除法を使うと

$$\begin{align}957=899\cdot1+58\end{align}$$
$$\begin{align}899=58\cdot15+29\end{align}$$
$$\begin{align}58=29\cdot2\end{align}$$

したがって

$$\begin{align}899=29\cdot2\cdot15+29=29(30+1)=29\cdot31\end{align}$$
$$\begin{align}957=29\cdot31\cdot1+58=29(31+2)=29\cdot33\end{align}$$
$$\begin{align}\frac{899}{957}=\frac{29\cdot31}{29\cdot33}=\frac{31}{33}\end{align}$$

31,33は互いに素なのでこれ以上約分することはできません。

よって、求める答えは

$$\begin{align}\bf \frac{31}{33}\end{align}$$

まとめ

ユークリッド互除法は最古のアルゴリズムといわれ、数学だけでなく、プログラミングの世界でも重要な知識です。


2020年以降に小学校でプログラミングが必修化される予定なので、ユークリッド互除法がらみの問題が出題される機会は今後増えてくるかもしれません。


どんな問題が出題されても対応できるよう、しっかり本記事で学んだ内容を自分のモノにしてくださいね!



この記事の執筆者
スタモ編集部
最高の学習をもっと身近に、どこでも。スタモ編集部は、大学受験や日々の勉強に役立つ記事を発信しています。予備校講師や塾講師の経験のある東大、京大、早慶の卒業者メンバーが中心に、どこよりも詳しく、どこよりも丁寧な内容をお届けいたします。
関連記事
数学的帰納法はこれでマスター!基本から大学入試レベルの問題の解き方まで徹底解説!
証明が苦手な方なら数学的帰納法はすごい難しいことをしているように見えるのではないでしょうか?しかし、その仕組みを理解すれば意外と簡単なんですよ。本記事では、数学的帰納法の基本や仕組み、問題の解き方について分かりやすく解説していきます。
反比例について徹底解説!基礎からからグラフの描き方まで初学者にもわかりやすく解説します
「反比例って苦手だったな…」「反比例のグラフの描き方忘れちゃった!」「日常生活で反比例の関係にあるものって?」本記事では反比例が苦手な方に向けて、今さら聞けない基本から徹底的に解説していきます。
0から分かる特性方程式!数列の漸化式の問題での使い方を詳しく解説
本記事では特性方程式の内容と証明、その使い方を詳しく解説していきます。特性方程式と、その元となる数列の漸化式(ぜんかしき)とは何かを理解し、さまざまな漸化式の問題をとおして特性方程式の使い方を身につけていきましょう。
0から分かる2倍角の公式!導出から公式を用いた計算まで徹底解説
この記事では、加法定理から2倍角の公式を導出します。また公式を用いた計算まで例題を解いて確認しましょう!
【等差数列】基礎から学んで3つの公式を使いこなそう!
等差数列は数列の基礎、土台です。数列は大学入試において頻出テーマなので、等差数列が苦手であっては大学合格は厳しいと言っても過言ではないでしょう。本記事では等差数列の3つの公式について分かりやすく解説していきます。
切片とは?傾き・2点の座標がわかっている時の求め方、切片の範囲についても解説!
切片とはなんでしょうか。切片とは直線に置いてy軸と交わっている点のことを指し、直線の式を求める際に傾きとともに最も大切な要素の一つです。本記事では切片とその求め方について解説します。
© 2018 スタモ.