ユークリッドの互除法の原理をわかりやすく解説！【互除法の活用２選アリ】

2019年11月24日2022年2月21日

こんにちは、ウチダです。

突然ですが、皆さんは

ユークリッドの互除法のやり方がわからない…。
なぜユークリッドの互除法が成り立つのか、その原理がわからない…。

こういった悩みを抱えてはいませんか？

整数の性質における最大の鬼門。

それが「ユークリッドの互除法」だと思います。

よって本記事では、「なぜユークリッドの互除法が成り立つのか」その原理から、ユークリッドの互除法の活用方法 $2$ 選、さらに裏ワザや図形的解釈まで

東北大学理学部数学科卒業
教員採用試験に１発合格　→　高校教諭経験アリ

の僕がわかりやすく解説します。

ユークリッドの互除法の原理をわかりやすく解説します【最大公約数に注目！】

ユークリッドの互除法の原理を一言でまとめるならば…

$GCD( \ a \ , \ b \ )=GCD( \ b \ , \ r \ )$、つまり最大公約数が動かない！

これに尽きます。

※ $GCD( \ a \ , \ b \ )$ で「 $a$ と $b$ の最大公約数」を表します。

ただ、これだけだとわかりづらいと思うので、図解して説明します。

割り算の等式 $a=bq+r$ を繰り返して考えていくことによって、値はどんどん小さくなっていきます。

よって、最初はわかりづらかった $GCD( \ a \ , \ b \ )$ であっても、

\begin{align}GCD( \ a \ , \ b \ )&=GCD( \ b \ , \ r \ )\\&=GCD( \ r \ , \ R \ )\\&=…\end{align}

と繰り返していけば、必ずいつかは簡単に求めることができる、という原理なわけです。

[ふきだし set=”悩む男性”]割り算を繰り返すことで最大公約数が求まることはわかったよ！ただ、なんで $GCD( \ a \ , \ b \ )=GCD( \ b \ , \ r \ )$ が成り立つのかがわからないなあ…。[/ふきだし]

[ふきだし set=”ウチダ”]では次に、$GCD( \ a \ , \ b \ )=GCD( \ b \ , \ r \ )$ がどうして成り立つのか、考えていきましょうか。[/ふきだし]

互除法の原理の証明

等式 $GCD( \ a \ , \ b \ )=GCD( \ b \ , \ r \ )$ を示すコツとして、

$GCD( \ a \ , \ b \ )≧GCD( \ b \ , \ r \ )$
$GCD( \ a \ , \ b \ )≦GCD( \ b \ , \ r \ )$

の $2$ つに分ける、という発想があります。

[ふきだし set=”ウチダ”]最大公”約数”、つまり”約数”なわけですから、大小関係がつきやすいんですよ。また、「～以上であり、かつ～以下」が言えれば、値は等しくなるしかありませんね。等式の証明でよく使うテクニックです。[/ふきだし]

この発想は、知らないと中々出てこないと思います。

ということで、証明ついでに押さえておきましょう。

【証明】

一々書くのが面倒なので、$GCD( \ a \ , \ b \ )=G$，$GCD( \ b \ , \ r \ )=G’$ と定義し直す。

①　$G≦G’$ を示す。

$a$ と $b$ の最大公約数が $G$ であるから、ある互いに素な自然数 $k$，$l$ を用いて

$$a=Gk \ , \ b=Gl$$

と表すことができる。

≫参考記事：最大公約数と最小公倍数の求め方とは？【ヒント：素因数分解】

これを等式「 $a=bq+r$ 」に代入すると、$Gk=Glq+r$ となり、$r$ についてまとめると

$$r=G(k-lq)$$

ここで、$k-lq$ は整数なので $G$ は $r$ の約数となり、$G$ は $b$ の約数でもあるので、$b$ と $r$ の公約数になる。

よって、$b$ と $r$ の”最大“公約数が $G’$ であることから、$G≦G’$ が成り立つ。

②　$G’≦G$ を示す。

ほとんど同じ方針で示すことができるので省略します。

式だけ書くと、ある互いに素な自然数 $m$，$n$ を用いて

$$a=G'(mq+n)$$

を導くことができればOKです。

したがって①，②より、$G≦G’$ かつ $G≧G’$ なので、$G=G’$ が成り立つ。

(証明終了)

これで、「なぜ最大公約数がずっと変化しないか」についても理解できたので、安心してユークリッドの互除法を使うことができますね！

ユークリッドの互除法の活用２選

さて、原理は理解できたので、次に考えるのは活用方法です。

ユークリッドの互除法の活用は、主に

最大公約数を求める問題
【重要】一次不定方程式の特殊解を求める問題

の $2$ つですので、順に解説していきます。

最大公約数を求める問題

問題.　次の最大公約数を求めなさい。
(1)　$6499$ と $1261$
(2)　$1073$ と $527$

まあ、ユークリッドの互除法の原理の中に最大公約数が出てきたので、活用としても当然出てきますよね。

もし素因数分解ができるのであれば、最大公約数は簡単に求めることができました。

ただこの問題のように、素因数分解が難しい場合、ユークリッドの互除法を使うしかありません。

【解答】

(1)　互除法を使ってどんどん割っていくと、

$6499=1261×5+194$

$1261=194×6+97$

$194=97×2$

したがって、$GCD(6499 \ , \ 1261)=GCD( \ 194 \ , \ 97 \ )=97$ と求まる。

(2)　互除法を使ってどんどん割っていくと、

$1073=527×2+19$

$527=19×27+14$

$19=14×1+5$

$14=5×2+4$

$5=4×1+1$

したがって、$GCD( \ 1073 \ , \ 527 \ )=GCD( \ 4 \ , \ 1 \ )=1$、つまり互いに素である。

(解答終了)

(2)の場合、$GCD( \ 19 \ , \ 14 \ )=1$ の時点でわかるので、そこで止めても構いません。

ただ、余りが $1$ になるまで互除法を行ったのには深いわけがあります。

それは…次の重要な応用問題につながってくるからです！！

【重要】一次不定方程式の特殊解を求める問題

問題.　次の不定方程式の整数解を $1$ つ求めなさい。
(1)　$6499x+1261y=97$
(2)　$1073x+527y=1$

方程式を満たす $1$ 組の簡単な解のことを「特殊解（とくしゅかい）」と呼びます。

ここでは、さっきの「最大公約数を求める問題」で行ったユークリッドの互除法を用いて、(1)(2)それぞれを満たす特殊解を求めていきましょう。

【解答】

(1)　互除法を逆の順番で書き、かつ両辺を入れ替えて、かつ移項すると、

$$97×2=194 \ ⇔ \ 97=194-97　…①$$

\begin{align}194×6+97=1261 \ ⇔ \ 97=1261-194×6　…②\end{align}

\begin{align}1261×5+194=6499 \ ⇔ \ 194=6499-1261×5　…③\end{align}

この $3$ つの式から、

\begin{align}97&=194-97\\&=194-(1261-194×6)\\&=194×7-1261\\&=(6499-1261×5)×7-1261\\&=6499×7-1261×36\end{align}

よって、$x=7$，$y=-36$ が整数解の $1$ つ（特殊解）である。

(2)　互除法を逆の順番で書き、かつ両辺を入れ替えて、かつ移項すると、

$$5=4×1+1 \ ⇔ \ 1=5-4×1　…①$$

$$14=5×2+4 \ ⇔ \ 4=14-5×2　…②$$

$$19=14×1+5 \ ⇔ \ 5=19-14×1　…③$$

\begin{align}527=19×27+14 \ ⇔ \ 14=527-19×27　…④\end{align}

\begin{align}1073=527×2+19 \ ⇔ \ 19=1073-527×2　…⑤\end{align}

この $5$ つの式から、

\begin{align}1&=5-4×1\\&=5-(14-5×2)×1\\&=5×3-14\\&=(19-14×1)×3-14\\&=19×3-14×4\\&=19×3-(527-19×27)×4\\&=19×111-527×4\\&=(1073-527×2)×111-527×4\\&=1073×111-527×226\end{align}

よって、$x=111$，$y=-226$ が整数解の $1$ つ（特殊解）である。

(解答終了)

…やっていることは理解できましたか？

ユークリッドの互除法を使うことで

(1)　…　$97$ → $194$ → $1261$ と $6499$
(2)　…　$1$ → $4$ → $5$ → $14$ → $19$ → $527$ と $1073$

のように、地道な道のりですが数字を変換していくことができるのです！

[ふきだし set=”ウチダ”]実は一次不定方程式は、特殊解を求めることができれば解けたも同然なんです！だから、ユークリッドの互除法はとても重宝するんですね～。[/ふきだし]

また、ここで仮に「 $1073x+527y=2$ 」という一次不定方程式の特殊解について考えてみると、(2)より

$$1073×111-527×226=1$$

なので、両辺を $2$ 倍することで

$$1073×222-527×452=2$$

となり、$x=222$，$y=452$ と特殊解がすぐに求まります。

以上より、こんなことも判明してしまいます。

【ユークリッドの互除法と一次不定方程式】
$a$，$b$，$c$ は自然数とする。
このとき、不定方程式 $ax+by=c$ は、$a$ と $b$ が互いに素であれば必ず整数解を持つ。

[ふきだし set=”考える女性”]なるほど！「～ $=1$ 」の特殊解さえ見つけることができれば、「～ $=2$ 」や「～ $=3$ 」は両辺を $2$ 倍，$3$ 倍することですぐに求められるのね！[/ふきだし]

ここまで理解できると、いろんな知識が結びついてきて面白いのではないでしょうか＾＾

あとの話は「一次不定方程式の解き方とは？【応用問題３選もわかりやすく解説します】」の記事で詳しく解説しておりますので、興味のある方はぜひあわせてご覧ください。

ユークリッドの互除法の裏ワザ・図形的な解釈とは？

さて、ユークリッドの互除法についての重要な部分の解説は終わりました。

あとはコラム的なお話です。

具体的には

筆算で解く互除法
互除法と長方形

この $2$ つについて解説します。

筆算で解く互除法って？（裏ワザ）

さきほど、ユークリッドの互除法を実際にやってみて、

計算がめんどくさいな…

と多くの方が感じたと思います。

でもご安心ください。僕もそう感じていますので。(笑)

そこで、書く量をもう少し抑えるために、筆算を用いるやり方を考えてみましょう。

何にも変なことはしていません。

割り算を、筆算の形で計算しただけです。

筆算の方が

書く量が少なくて済む
ノートに書いたときに見やすい

ので、慣れてきたらこの裏ワザを使ってみるのもオススメです♪

[ふきだし set=”ウチダ”]当たり前ですが、あくまで裏ワザなので成り立つ原理は同じです。原理を理解しないで使える裏ワザなど、この世に存在しません。[/ふきだし]

互除法と長方形の関係って？（図形的な解釈）

問題.　縦が $377 \ (cm)$、横が $319 \ (cm)$ の長方形の中を、同じ正方形を使ってすきまなく敷き詰める。このとき、条件を満たす正方形のうち、最大のものを求めなさい。

もちろん、$1$ 辺が $1 \ (cm)$ の正方形であれば、$377×319$ 個使って敷き詰めることができますが、ここで聞かれているのは「最大の正方形」です。

実はこの問題は、ユークリッドの互除法で計算することに対応しているのです！

【解答】

なるべく大きな正方形をどんどん除いていく方針で考えていこう。

すると、以下のアニメーションのようになる。

※スライドは計 $4$ 枚あります。

つまりこの操作は、

$377=319×1+58$

$319=58×5+29$

$58=29×2+0$

と、ユークリッドの互除法の作業と一致する。

よって、$377$ と $319$ の最大公約数が $29$ であることがわかったので、条件を満たす正方形で最大のものは、$1$ 辺が $29 \ (cm)$ の正方形である。

(解答終了)

代数的な計算が、図形と結びつく瞬間はたまらなく気持ちいいですね！

ユークリッドの互除法に関するまとめ

本記事の要点を改めて $3$ つまとめます。

$GCD( \ a \ , \ b \ )=GCD( \ b \ , \ r \ )$、つまり最大公約数が動かないことこそが、互除法の原理である。
活用法は、素因数分解が困難な「最大公約数」と「一次不定方程式」
筆算や図形的解釈も押さえておくと、より理解が深まります♪

ユークリッドの互除法をしっかり理解して、整数マスターになろう！！

リンク

「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!

終わりです。

よかったらシェアしてね！

URLをコピーしました！

URLをコピーしました！

ユークリッドの互除法の原理をわかりやすく解説！【互除法の活用２選アリ】