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

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

突然ですが、皆さんは

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

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

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

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

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

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

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

スポンサーリンク
スポンサーリンク
目次

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

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

$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}

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

数学太郎のアイコン画像数学太郎
割り算を繰り返すことで最大公約数が求まることはわかったよ!ただ、なんで $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選

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

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

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

の $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$

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

ウチダのアイコン画像ウチダ
実は一次不定方程式は、特殊解を求めることができれば解けたも同然なんです!だから、ユークリッドの互除法はとても重宝するんですね~。

また、ここで仮に「 $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$ が互いに素であれば必ず整数解を持つ。
数学花子のアイコン画像数学花子
なるほど!「 ~ $=1$ 」の特殊解さえ見つけることができれば、「 ~ $=2$ 」や「 ~ $=3$ 」は両辺を $2$ 倍,$3$ 倍することですぐに求められるのね!

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

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

スポンサーリンク

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

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

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

具体的には

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

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

筆算で解く互除法って?(裏ワザ)

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

計算がめんどくさいな…

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

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

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

筆算で解く互除法って?(裏ワザ)

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

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

筆算の方が

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

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

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

互除法と長方形の関係って?(図形的な解釈)

問題. 縦が $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$ つまとめます。

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

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

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

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

終わりです。

遊ぶ数学公式LINEやってます!

遊ぶ数学管理人「ウチダショウマ」に数学を直接教わることができるオンライン家庭教師サービス”Play MATH”を開始しました。

その他にも

・ウチダショウマとお話がしたい
・勉強に関する悩みを相談したい

などでもOKですので、ぜひ気軽にご連絡ください。

↓友達追加はこちらから↓

友だち追加

スポンサーリンク

コメント

コメントする

目次
閉じる