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

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

突然ですが、皆さんは

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

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

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

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

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

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

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

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

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

これに尽きます。

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

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

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

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

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

数学太郎

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

ウチダ

では次に、$GCD( \ a \ , \ b \ )=GCD( \ b \ , \ r \ )$ がどうして成り立つのか、考えていきましょうか。

互除法の原理の証明

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

1. $GCD( \ a \ , \ b \ )≧GCD( \ b \ , \ r \ )$
2. $GCD( \ a \ , \ b \ )≦GCD( \ b \ , \ r \ )$

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

ウチダ

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

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

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

【証明】

一々書くのが面倒なので、$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×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)(2)それぞれを満たす特殊解を求めていきましょう。

【解答】

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

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

この $3$ つの式から、

よって、$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　…③$$

この $5$ つの式から、

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

(解答終了)

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

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

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

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

ウチダ

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

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

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

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

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

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

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

数学花子

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

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

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

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

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

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

具体的には

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

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

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

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

計算がめんどくさいな…

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

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

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

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

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

筆算の方が

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

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

ウチダ

当たり前ですが、あくまで裏ワザなので成り立つ原理は同じです。原理を理解しないで使える裏ワザなど、この世に存在しません。

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

もちろん、$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$ つまとめます。

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

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

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

あわせて読みたい

整数の性質とは？【高校数学Ａの解説記事総まとめ２５選】 「整数の性質」の総まとめ記事です。本記事では、整数の性質の解説記事全２５個をまとめています。「整数の性質をしっかりマスターしたい」「整数の性質を自分のものにしたい」という方は必見です。

終わりです。