「ユークリッドの互除法」で最大公約数（gcd）を簡単に求める方法を教えてほしい！
最大公約数（gcd）の計算のやり方がイマイチ分からない・・・
こういったお悩みを解決します。
教科書に載っているような「ユークリッドの互除法」で 最大公約数（$\gcd$）を求めるやり方は
ややこしいうえに書く量が多いので、計算ミス・記述ミスが起こりやすい です。
右から左に書いていく筆算（簡便法）もありますが、ちょっと 見た目がダサい ですよね。
そこで今回は、「ユークリッドの互除法」で最大公約数（$\gcd$）をサクッと簡単に求める方法 を解説します。
早く解けてミスも減るやり方なので、ぜひマスターしましょう！
【ユークリッドの互除法】最大公約数（gcd）の基本原理
「ユークリッドの互除法（ごじょほう）」に入る前に、最大公約数（$\gcd$）の計算をおさらいしましょう。
最大公約数（gcd）の表し方
一般に、自然数 $a, \ b $ の 最大公約数 を
と表します。
※ $\gcd$：$Greatest \, Common \, Divisor$（最大公約数）
この書き方は教科書には載っていませんが、最大公約数の計算がラクになるので覚えておきましょう。
【例】$15$ と $ 21 $ の最大公約数 は
$ $ $ \gcd(15, \, 21) $
$ = \gcd(\color{red}{3}×5, \, \color{red}{3}×7) $ ← 素因数分解
$ = \color{red}{3} $
こんなイメージです。
ユークリッドの互除法の原理（gcdの性質）
最大公約数 $\gcd$ の性質として
$ \gcd \left(小, \, 大 \right) $
$= \gcd \left(小, \, \left[ 大を小で割った余り \right] \right) $
というものがあります。（ユークリッドの互除法の原理）
この性質を利用して、$\left[ 大を小で割った余り \right] $ が $\bbox[#E2F0D9, 2pt, border:]{0}$ になるまで計算していく（小さくしていく）と 最大公約数 が求められます。
【例】$15$ と $ 21 $ の最大公約数 は
$ $ $ \gcd(15, \, 21) $
$ = \gcd \left(15, \, 15× 1 + \bbox[#F4E2E2, 2pt, border:]{6} \right) $ → $21÷15$ の余りは $ \bbox[#F4E2E2, 2pt, border:]{6}$
$ = \gcd \left(15, \, \bbox[#F4E2E2, 2pt, border:]{6} \right) $
$ = \gcd \left(6× 2 + \bbox[#F4E2E2, 2pt, border:]{3} , \, 6 \right)$ → $ 15÷6$ の余りは $ \bbox[#F4E2E2, 2pt, border:]{3}$
$ = \gcd \left( \bbox[#F4E2E2, 2pt, border:]{3} , \, 6 \right) $
$ = \gcd \left( \color{red}{3}, \, \color{red}{3}×2 +\bbox[#E2F0D9, 2pt, border:]{0} \right) $ → $ 6÷3$ の余りは $ \bbox[#E2F0D9, 2pt, border:]{0}$
$ = \color{red}{3} $
慣れてきたら、以下のように簡略化してもOK。
【例】$15$ と $ 21 $ の最大公約数 は
$ $ $ \gcd(15, \, 21) $
$ = \gcd \left(15, \, \bbox[#F4E2E2, 2pt, border:]{6} \right) $
$ = \gcd \left( \bbox[#F4E2E2, 2pt, border:]{3} , \, 6 \right) $
$ = \color{red}{3} $
こんな感じでスッキリ書けます。
なお、これを普通の「ユークリッドの互除法」で書くと
【例】$15$ と $ 21 $ の最大公約数
$ 21 = 15× 1 + \bbox[#F4E2E2, 2pt, border:]{6} $
$ 15 = 6× 2 + \bbox[#F4E2E2, 2pt, border:]{3} $
$ 6 = \color{red}{3}× 2 + \bbox[#E2F0D9, 2pt, border:]{0} $
よって、最大公約数は $\color{red}{3}$
さっきの簡略化した書き方と見比べてもらうと、どっちがスッキリしているか一目瞭然ですね。
【ユークリッドの互除法】最大公約数（gcd）の求め方
さて、本題に入りましょう。
【例題】$ 2438 $ と $ 3763 $ の最大公約数 を求めよ。
素因数分解して最大公約数を求めるのはちょっと大変そうですね。
というわけで、「ユークリッドの互除法」を使って解いてみます。
まずは、教科書に載っているような普通のやり方で求めると
【解答1】
$ 3763 = 2438 × 1 + \bbox[#F4E2E2, 2pt, border:]{1325} $
$ 2438 = 1325 × 1 + \bbox[#F4E2E2, 2pt, border:]{1113} $
$ 1325 = 1113 × 1 + \bbox[#F4E2E2, 2pt, border:]{212} $
$ 1113 = 212 × 5 + \bbox[#F4E2E2, 2pt, border:]{53} $
$ 212 = \color{red}{53} × 4 + \bbox[#E2F0D9, 2pt, border:]{0} $
よって、最大公約数は $\color{red}{53}$
となりますね。
これを $ \gcd(a, \, b) $ の書き方にすると
ユークリッドの互除法の原理 より
【解答2】
$ 2438 $ と $ 3763 $ の最大公約数 は
$ $ $ \gcd (2438, \, 3763 ) $
$= \gcd \left(2438, \, 2438 × 1 + \bbox[#F4E2E2, 2pt, border:]{1325} \right) = \gcd \left(2438, \, \bbox[#F4E2E2, 2pt, border:]{1325} \right) $
$= \gcd \left(1325 × 1 + \bbox[#F4E2E2, 2pt, border:]{1113}, \, 1325 \right) = \gcd \left( \bbox[#F4E2E2, 2pt, border:]{1113}, \, 1325 \right) $
$ = \gcd \left(1113, \, 1113 × 1 + \bbox[#F4E2E2, 2pt, border:]{212} \right) = \gcd \left(1113, \, \bbox[#F4E2E2, 2pt, border:]{212} \right) $
$= \gcd \left(212× 5 + \bbox[#F4E2E2, 2pt, border:]{53} , \, 212 \right) = \gcd \left( \bbox[#F4E2E2, 2pt, border:]{53}, \, 212 \right) $
$= \gcd \left(\color{red}{53}, \, \color{red}{53}×4 + \bbox[#E2F0D9, 2pt, border:]{0} \right) = \color{red}{53} $
簡略化すると
【解答2’】
$ 2438 $ と $ 3763 $ の最大公約数 は
$ $ $ \gcd(2438, \, 3763) $
$ = \gcd \left(2438, \, \bbox[#F4E2E2, 2pt, border:]{1325} \right) $
$ = \gcd \left( \bbox[#F4E2E2, 2pt, border:]{1113}, \, 1325 \right) $
$ = \gcd \left(1113, \, \bbox[#F4E2E2, 2pt, border:]{212} \right) $
$ = \gcd \left( \bbox[#F4E2E2, 2pt, border:]{53}, \, 212 \right) $
$ = \color{red}{53} $
こんな感じです。
【ユークリッドの互除法】最大公約数（gcd）の練習問題
実際に「ユークリッドの互除法」で最大公約数（$\gcd$）を求める練習問題をやってみましょう。
【問題】$ 714 $ と $ 6732 $ の最大公約数を求めよ。
- 【解答】を見る
-
【解答】
$ 714 $ と $ 6732 $ の最大公約数 は
$ $ $ \gcd (714, \, 6732 ) $
$= \gcd \left(714, \, 714 × 9 + \bbox[#F4E2E2, 2pt, border:]{306} \right) = \gcd \left(714, \, \bbox[#F4E2E2, 2pt, border:]{306} \right) $
$= \gcd \left(306 × 2 + \bbox[#F4E2E2, 2pt, border:]{102}, \, 306 \right) = \gcd \left( \bbox[#F4E2E2, 2pt, border:]{102}, \, 306 \right) $
$ = \gcd \left(\color{red}{102}, \, \color{red}{102} × 3 + \bbox[#E2F0D9, 2pt, border:]{0} \right) = \color{red}{102}$
以上です。お疲れ様でした！
【まとめ】「ユークリッドの互除法」最大公約数の求め方
最後にまとめです。
最大公約数 $\gcd$ を求めるための「ユークリッドの互除法の原理」は
$ \gcd \left(小, \, 大 \right) $
$ = \gcd \left(小, \, \left[ 大を小で割った余り \right] \right) $
$\left[ 大を小で割った余り \right] $ が $\bbox[#E2F0D9, 2pt, border:]{0}$ になるまで小さくしていくと 最大公約数 がサクッと簡単に求められます。
質問・要望があれば気軽にコメントください👍