最大公約数を効率的に求めるユークリッドの互除法：仕組みとJava実装

2026年3月25日 2026年3月25日山崎講師

山崎講師

こんにちは。ゆうせいです。

ユークリッドの互除法とは

数学において、2つの整数の最大公約数を求める手法として古くから知られているのがユークリッドの互除法です。最大公約数とは、2つの数字を共に割り切ることができる最大の整数のことを指します。

通常、最大公約数を探すには、それぞれの数字を素因数分解して共通の要素を抜き出す必要があります。しかし、数字が非常に大きくなると、素因数分解には膨大な時間がかかります。ユークリッドの互除法は、割り算を繰り返すだけで確実に答えにたどり着けるため、計算効率が極めて高いアルゴリズムとして知られています。

アルゴリズムの基本的な考え方

この手法の根幹にあるのは、2つの整数 a と b （a > b）について、a を b で割った余りを r としたとき、a と b の最大公約数は b と r の最大公約数に等しいという性質です。

これを高校生にも分かりやすい比喩で説明します。

縦が a、横が b という大きさの長方形を、できるだけ大きな正方形で隙間なく埋め尽くす場面を想像してください。このとき、最も大きな正方形の一辺の長さが最大公約数にあたります。

まず、長方形の中に一辺が b の正方形を詰められるだけ詰めます。
最後に余った細長い長方形（縦が b、横が r）に注目します。
次は、この余った長方形をさらに小さな正方形で埋めていきます。
最終的に余りがなくなったときの正方形のサイズが、最初の大きな長方形を埋める正方形と同じサイズになります。

ユークリッドの互除法のメリットとデメリット

このアルゴリズムをプログラムに組み込む際の利点と注意点を整理します。

メリット

計算速度が速い：数字の桁数が増えても、計算回数はそれほど劇的に増加しません。
記憶容量を消費しない：過去の計算結果を大量に保持する必要がなく、少ないメモリで動作します。
実装が容易：後述するコードの通り、非常に短い行数で記述できます。

デメリット

整数以外には適用できない：小数が含まれる計算には直接利用できません。
負の数の扱い：一般的には絶対値を用いて計算する必要がありますが、プログラム上での条件分岐が必要になります。

Javaによる実装

ユークリッドの互除法を Java で記述する場合、再帰呼び出しという手法を用いると構造が明確になります。再帰呼び出しとは、メソッドの中で自分自身を再び呼び出す処理のことです。

public class EuclideanAlgorithm {
    public static void main(String[] args) {
        int a = 1071;
        int b = 1029;
        int result = gcd(a, b);
        System.out.println(result);
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

このコードでは、変数 b が 0 になった瞬間に変数 a の値を返します。これは、割り切れた瞬間の割る数が最大公約数であるという数学的事実に基づいています。

数学的背景

このアルゴリズムが成立する背景には、以下の関係式があります。

a と b の最大公約数を gcd(a, b) と表記し、a を b で割った商を q、余りを r とすると、以下の等式が成り立ちます。

$a = bq + r$

このとき、以下の関係が維持されることが証明されています。

$\gcd(a, b) = \gcd(b, r)$

この操作を、余りが 0 になるまで繰り返すことで、最終的な解を導き出します。

まとめ

ユークリッドの互除法は、一見複雑に見える問題を、より小さな問題へと分解して解決する分割統治の思想を体現したアルゴリズムです。

今後の学習ステップとしては、以下の順序で理解を深めることを推奨します。

負の整数が入力された際にも正しく動作するよう、絶対値処理を加えたコードへの改良。
3つ以上の整数の最大公約数を求めるための、アルゴリズムの拡張方法の検討。
拡張ユークリッドの互除法を学び、一次不定方程式の解を求める応用への挑戦。

セイ・コンサルティング・グループでは新人エンジニア研修のアシスタント講師を募集しています。

投稿者プロフィール

山崎講師代表取締役

セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。

学生時代は趣味と実益を兼ねてリゾートバイトにいそしむ。長野県白馬村に始まり、志賀高原でのスキーインストラクター、沖縄石垣島、北海道トマム。高じてオーストラリアのゴールドコーストでツアーガイドなど。現在は野菜作りにはまっている。