ユークリッドの互除法とは｜手順・証明と4言語の実行結果・回数の実測

互除法は「割り算の余り」だけを使う、約2300年前から知られている手順です。素因数分解をしなくても、どんなに大きな数でも少ない回数で最大公約数が求まります。流れは次のとおりです。

flowchart TD
    S[a と b を受け取る] --> Z{b は 0 か}
    Z -->|はい| E[a が最大公約数]
    Z -->|いいえ| R[r = a ÷ b の余り]
    R --> M[a に b、b に r を入れる]
    M --> Z

よく調べられることの答えを先にまとめます。

確認環境：Ubuntu 24.04.5 LTS の上で、Python 3.13.18、Node.js v22.23.4、OpenJDK 21.0.12.1（javac 21.0.12.1）、gcc／g++ 13.3.0（C は -O2、C++ は -std=c++17）を使い、記事に載せた計算・手順の表・実行結果はすべて手元で実行して出力をそのまま写しました。ステップ数は Python で数え上げ（1以上10000以下のすべての組 50,005,000 通りなど）、実行時間は各言語で同じ計算を100万回繰り返して3回ずつ測りました。math.gcd・math.integer の仕様は Python の公式ドキュメント（3.15 系）、% と BigInt は MDN、BigInteger は Oracle の Java SE 21 API ドキュメント、std::gcd は cppreference、高校数学での扱いは文部科学省の学習指導要領解説、試験での扱いは IPA の公開資料で確かめました。図は mermaid 11.16.0 で描画を確かめています（確認日 2026年10月29日）。

ユークリッドの互除法とは（最大公約数を割り算だけで求める方法）

この節では、ユークリッドの互除法が何をする方法で、どんな場面で使われるのかが分かります。

ユークリッドの互除法（Euclidean algorithm）は、2つの整数の最大公約数（gcd：greatest common divisor）を、割り算の余りを繰り返し使って求める方法です。「互いに除する（割り合う）」ことから互除法と呼ばれます。古代ギリシャの数学者ユークリッド（エウクレイデス）の『原論』に載っていることからこの名前があり、英語版 Wikipedia は、整数の版が第7巻、線分の長さの版が第10巻にあると紹介しています。

• 最大公約数：2つの数のどちらも割り切れる数（公約数）のうち、いちばん大きいもの。1071と462の公約数は 1・3・7・21 で、最大公約数は21です（手元で約数をすべて書き出して確かめました）。
• 互いに素：最大公約数が1になる2つの数。例えば 55 と 34。
• 記号：gcd(1071, 462) = 21 のように書きます。

互除法の手順（1071と462で一歩ずつ）

この節では、互除法の手順を、具体的な数で1行ずつ追いながら理解できます。

やることは「割り算をして、割る数と余りを1つずつ左へずらす」の繰り返しだけです。 1071 と 462 で進めます。

同じ計算を表にすると、「割る数」と「余り」が1段ずつ左下へずれていく様子が見えます。

手順を表示する Python のプログラムと、その出力です。どの組でも同じ手順で答えが出ます。

def trace(a, b):
    print(f"gcd({a}, {b}) の手順")
    step = 0
    while b != 0:
        q, r = divmod(a, b)          # 商と余り
        step += 1
        print(f"  {step}: {a} = {b} × {q} + {r}")
        a, b = b, r                  # 割る数と余りを左へずらす
    print(f"  → 最大公約数 {a}（割り算 {step} 回）")
    return a

gcd(1071, 462) の手順
  1: 1071 = 462 × 2 + 147
  2: 462 = 147 × 3 + 21
  3: 147 = 21 × 7 + 0
  → 最大公約数 21（割り算 3 回）
gcd(462, 1071) の手順
  1: 462 = 1071 × 0 + 462
  2: 1071 = 462 × 2 + 147
  3: 462 = 147 × 3 + 21
  4: 147 = 21 × 7 + 0
  → 最大公約数 21（割り算 4 回）
gcd(160, 48) の手順
  1: 160 = 48 × 3 + 16
  2: 48 = 16 × 3 + 0
  → 最大公約数 16（割り算 2 回）
gcd(12, 0) の手順
  → 最大公約数 12（割り算 0 回）

• 小さい方を先に渡しても答えは同じです。 gcd(462, 1071) は1回目が「462 = 1071 × 0 + 462」となり、2つの数が入れ替わるだけで、回数が1回増えました。プログラムで大小を比べる処理は要りません。
• 片方が0なら、もう片方がそのまま答えです（12 と 0 の最大公約数は12）。0 はどんな数でも割り切れるためです。

長方形を正方形で埋める図で見る

互除法は、「縦 462・横 1071 の長方形を、できるだけ大きな正方形で敷き詰め、残りをまた正方形で埋める」作業と同じです。最後に隙間なく埋まった正方形の一辺が最大公約数です。

正方形の個数（2・3・7）は、割り算の商と一致します。一辺21の正方形で1071×462の長方形全体も隙間なく埋まり、21より大きな正方形では埋まりません。

練習問題（答えは実行して確かめた値）

391 と 323 は、素因数分解で 391 = 17 × 23、323 = 17 × 19 と気づかないと手が止まりやすい組ですが、互除法なら割り算4回で17が出ます。

なぜ最大公約数が求まるのか（互除法の証明をやさしく）

この節では、互除法で本当に最大公約数が求まる理由が、割り算の式1本から分かります。

証明の芯は「a = b × q + r のとき、a と b の公約数と、b と r の公約数は、まったく同じ集まりになる」という1点です。 公約数の集まりが同じなら、そのいちばん大きいもの（最大公約数）も同じです。

左右を合わせると、「a と b の公約数」と「b と r の公約数」は1つも過不足なく一致します。式で書くと gcd(a, b) = gcd(b, a mod b) です（a mod b は a を b で割った余り）。1071と462で確かめると、両方とも公約数は 1・3・7・21 でした。

1071 と 462 の公約数 : [1, 3, 7, 21]
462 と 147 の公約数  : [1, 3, 7, 21]
1〜300 のすべての組 90000 通りで「a,b の公約数の集まり」と「b, a mod b の公約数の集まり」を比べた結果 : 不一致 0

必ず終わる理由

余りは割る数より必ず小さいので、b → r → 次の余り…と、0以上の整数がどんどん小さくなります。0以上の整数は無限に小さくなり続けることはできないため、いつか必ず余りが0になります。余りが0のとき gcd(d, 0) = d なので、最後に割った数 d が答えです。

gcd(1071, 462) = gcd(462, 147) = gcd(147, 21) = gcd(21, 0) = 21

証明を書くときは、「公約数の集まりが一致する」ことと「必ず有限回で終わる」ことの2点をそろえると、筋の通った説明になります。

最大公約数の求め方3つの比較（素因数分解・すだれ算・互除法）

この節では、最大公約数の求め方として学校で習う3つの方法の違いと、どれを使えばよいかが分かります。

数が小さく素因数がすぐ分かるなら素因数分解やすだれ算、数が大きい・素因数が分かりにくいなら互除法が速く確実です。 同じ 1071 と 462 で比べます。

手元で、プログラムにしたときの手間を比べました（Python 3.13、1回あたりの平均）。

999999000001 は素数で、999998000001 は 999999 の2乗でした（試し割りで分解した結果）。素数を含む12桁の組では、素因数分解は割る数を約100万まで試すため、互除法と比べて約48万倍の時間がかかりました。素因数分解は「大きな数ほど急に遅くなる」、互除法は「桁数に比例する程度しか増えない」のが違いです。

最小公倍数との関係（lcm = a ÷ gcd × b）

この節では、最大公約数から最小公倍数を求める式と、プログラムで計算するときの順番の注意が分かります。

2つの正の整数 a・b では「最大公約数 × 最小公倍数 = a × b」が成り立つので、最小公倍数は a × b ÷ gcd(a, b) で求まります。 1071 と 462 なら 1071 × 462 ÷ 21 = 23562 です。

• 素因数分解で見ると、最大公約数は「共通する素因数を小さい方の指数で」、最小公倍数は「すべての素因数を大きい方の指数で」掛けたものです。1071 = 3² × 7 × 17、462 = 2 × 3 × 7 × 11 なので、最小公倍数は 2 × 3² × 7 × 11 × 17 = 23562。
• すだれ算では、左に並んだ割った数（3 と 7）と、下に残った数（51 と 22）を全部掛けます。3 × 7 × 51 × 22 = 23562。
• Python の math.lcm(1071, 462) も 23562 を返しました。

プログラムでは「a ÷ gcd × b」の順に計算します。 先に a × b を計算すると、答えが型に収まるのに途中で桁あふれすることがあります。Java の int（上限 2147483647）で 100000 と 99999 の最小公倍数を求めた結果です。

lcm int a*b/g = 1409965408  a/g*b long = 9999900000

正しい答えは 9999900000 で、int の上限を超えるため long で計算しました。int のまま a * b とした左側は、桁あふれした値 1409965408 になっています。C でも同じ値になりました（C の符号つき整数の桁あふれは未定義動作のため、手元では符号なしで掛けた結果を表示しています）。Java の型ごとの上限は、関連記事「Javaデータ型一覧｜基本型8種の範囲・最大値とオーバーフロー」で扱っています。

3つ以上の数の最大公約数・最小公倍数

3つ以上の数は、2つずつ順に計算します。gcd(84, 36, 60) = gcd(gcd(84, 36), 60) = gcd(12, 60) = 12 です。Python 3.9 以降の math.gcd・math.lcm は引数をいくつでも受け取れます。

>>> import math
>>> math.gcd(12, 18, 30), math.gcd(84, 36, 60)
(6, 12)
>>> math.lcm(4, 6), math.lcm(4, 6, 10)
(12, 60)

拡張ユークリッドの互除法（ax + by = gcd の係数を求める）

この節では、互除法の途中の式を逆にたどって、1071x + 462y = 21 を満たす整数 x・y を求める方法が分かります。

互除法で出てきた式を下から順に代入していくと、最大公約数を「a の何倍＋b の何倍」で表せます。 これを拡張ユークリッドの互除法と呼び、整数の方程式（一次不定方程式）や、割り算の余りの世界での逆数（モジュラ逆数）を求めるのに使います。

手で逆にたどる

1. 2回目の式 462 = 147 × 3 + 21 から、21 = 462 − 147 × 3
2. 1回目の式 1071 = 462 × 2 + 147 から、147 = 1071 − 462 × 2
3. 2 を 1 に代入：21 = 462 − (1071 − 462 × 2) × 3 = 462 × 7 − 1071 × 3
4. よって 1071 × (−3) + 462 × 7 = 21。x = −3、y = 7

確かめ：1071 × (−3) = −3213、462 × 7 = 3234、合計 21。

表で上から求める（プログラム向き）

各行の r を「1071 × x + 462 × y」の形で持ちながら割り算を進めると、逆にたどらずに x・y が出ます。次の行の x・y は「2行前 − 商 × 1行前」です。

表の値は、プログラムで各行の「1071x + 462y」を計算し直して確かめました。最後の行の 22 と −51 は、1071 ÷ 21 = 51、462 ÷ 21 = 22 の関係から出てくる値です。

def egcd(a, b):
    """(g, x, y) を返す。a*x + b*y == g == gcd(a, b)"""
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

print(egcd(1071, 462))   # (21, -3, 7)
print(egcd(17, 5))       # (1, -2, 7)

egcd(1071,462) (21, -3, 7)
egcd(17,5) (1, -2, 7)

解はほかにもある・解が無い場合もある

• ほかの解：x = −3 + 22t、y = 7 − 51t（t は整数）もすべて解です。t = 1 で x = 19、y = −44 となり、1071 × 19 + 462 × (−44) = 20349 − 20328 = 21 でした。
• 右辺が最大公約数の倍数なら解がある：1071x + 462y = 42 は、両辺を2倍して x = −6、y = 14。
• 倍数でなければ整数解は無い：1071x + 462y = 10 は、左辺が必ず21の倍数になるため整数の解がありません。

モジュラ逆数（5 × x を17で割ると1余る x）

egcd(17, 5) = (1, −2, 7) は 17 × (−2) + 5 × 7 = 1 を意味し、5 × 7 = 35 を17で割ると1余ります。つまり 7 が「17 を法とした 5 の逆数」です。Python では pow(5, -1, 17) で直接求まり、手元でも 7 が返りました。最大公約数が1でない組では逆数が無く、エラーになります。

>>> pow(5, -1, 17)
7
>>> pow(462, -1, 1071)
ValueError: base is not invertible for the given modulus

Pythonで互除法を書く（再帰・反復・math.gcd）

この節では、Python で最大公約数を求める3通りの書き方と、標準ライブラリの math.gcd の振る舞いが分かります。

使うだけなら math.gcd を使い、仕組みを学ぶときは while の反復版を書くのがおすすめです。

import math

def gcd_rec(a, b):            # 再帰版：gcd(a, b) = gcd(b, a % b) をそのまま書く
    return a if b == 0 else gcd_rec(b, a % b)

def gcd_it(a, b):             # 反復版：変数を入れ替えながら回す
    while b:
        a, b = b, a % b
    return abs(a)

print(gcd_rec(1071, 462), gcd_it(1071, 462), math.gcd(1071, 462))   # 21 21 21

math.gcd に、0・負の数・小数・大きな数を渡した結果です（Python 3.13.18）。

>>> math.gcd(1071, 462), math.gcd(-1071, 462), math.gcd(1071, -462)
(21, 21, 21)
>>> math.gcd(0, 0), math.gcd(12, 0), math.gcd(0, -12), math.gcd()
(0, 12, 12, 0)
>>> math.lcm(0, 5), math.lcm(-4, 6), math.lcm()
(0, 12, 1)
>>> math.gcd(12.0, 18)
TypeError: 'float' object cannot be interpreted as an integer
>>> math.gcd(2**200 * 3, 2**150 * 9)
4281743078117879643174857908348485409148239872

• math.gcd は Python 3.5 で追加され、3.9 で3つ以上の引数に対応し、math.lcm も 3.9 で追加されました（公式ドキュメント）。
• 2026年10月29日時点の公式ドキュメント（3.15 系）では、整数用の関数をまとめた math.integer モジュールが 3.15 で追加され、math.gcd・math.lcm はその別名として「soft deprecated（使い続けられるが新しい書き方を勧める）」と書かれています。手元の 3.13 には math.integer は無いため、3.13 以前でも動くコードは math.gcd のままにします。
• Python の % は割る数と同じ符号になります（-1071 % 462 は 315）。このため、自分で書いた互除法は負の数を入れると答えの符号が変わることがあります（よくある間違いの節）。

関数が0や負の数で正しく動くかを確かめるテストは、関係する値の境目（0・1・負・大きな数）を選ぶと抜けが減ります。テストケースの選び方は、関連記事「同値分割・境界値分析｜テストケース表とpytestコード例で解説」で扱っています。

JavaScript・Java・Cで互除法を書く（BigInt・BigInteger・std::gcd）

この節では、JavaScript・Java・C（C++）での最大公約数の書き方と、言語ごとの落とし穴が、実行結果で分かります。

標準の gcd 関数があるのは、4言語のうち Java（BigInteger.gcd）と C++17（std::gcd）です。JavaScript と C は自分で書きます。

JavaScript（Node.js 22）

function gcd(a, b) {
  a = Math.abs(a); b = Math.abs(b);
  while (b !== 0) { [a, b] = [b, a % b]; }
  return a;
}
function gcdBig(a, b) {             // BigInt 版：大きな整数を正確に扱う
  if (a < 0n) a = -a;
  if (b < 0n) b = -b;
  while (b !== 0n) { [a, b] = [b, a % b]; }
  return a;
}
const lcm = (a, b) => (a === 0 || b === 0 ? 0 : Math.abs(a / gcd(a, b) * b));

gcd(1071, 462) = 21  rec = 21
lcm(1071, 462) = 23562
-1071 % 462 = -147  1071 % -462 = 147
gcd(0, 0) = 0  gcd(12, 0) = 12
Number(F91) = 4660046610375530000  safe? false
gcd(Number) = 2048  gcdBig = 1n
gcdBig(2n**200n*3n, 2n**150n*9n) = 4281743078117879643174857908348485409148239872n
TypeError: Cannot mix BigInt and other types, use explicit conversions

• Number で大きな整数を扱うと、答えがずれます。 4660046610375530309 と 2880067194370816120（隣り合うフィボナッチ数で、最大公約数は1）を Number にすると下の桁が丸められ、gcd が 2048 になりました。Number.MAX_SAFE_INTEGER（9007199254740991）を超える整数は BigInt（末尾に n）で扱います。
• BigInt と Number を混ぜると TypeError: Cannot mix BigInt and other types, use explicit conversions になりました。
• JavaScript の % は割られる数と同じ符号になります（MDN）。-1071 % 462 は −147 でした。

Number の小数で計算すると答えが崩れる理由は、関連記事「JavaScriptの小数計算誤差と丸め｜toFixedの落とし穴と正しい対処法」で扱っています。

Java（OpenJDK 21）

コードは中心の部分の抜粋で、出力は確認用の行を足した全体のプログラムを実行したものです（C も同じ）。

import java.math.BigInteger;

public class Gcd {
    static int gcd(int a, int b) {
        while (b != 0) { int r = a % b; a = b; b = r; }
        return Math.abs(a);
    }
    public static void main(String[] args) {
        System.out.println(gcd(1071, 462));                                   // 21
        BigInteger x = new BigInteger("4660046610375530309");
        BigInteger y = new BigInteger("2880067194370816120");
        System.out.println(x.gcd(y));                                         // 1
        System.out.println(BigInteger.valueOf(5).modInverse(BigInteger.valueOf(17)));  // 7
    }
}

gcd(1071, 462) = 21  rec = 21
-1071 % 462 = -147  Math.floorMod(-1071, 462) = 315
gcdRec(1071, -462) = -21  gcd(1071, -462) = 21
gcd(0, 0) = 0  gcd(12, 0) = 12
gcd(Integer.MIN_VALUE, 0) = -2147483648
BigInteger.gcd = 1  21  0
modInverse 5 mod 17 = 7
ArithmeticException: BigInteger not invertible.
12 % 0 -> ArithmeticException: / by zero

• BigInteger.gcd は「abs(this) と abs(val) の最大公約数、両方0なら0」を返します（Oracle の API ドキュメント）。手元でも −1071 と 462 で21、0 と 0 で0でした。
• modInverse は逆数が無いと ArithmeticException: BigInteger not invertible. を投げました。
• Math.abs(Integer.MIN_VALUE) は負のまま（−2147483648）です。int の最小値は正にすると int に収まらないため、gcd(Integer.MIN_VALUE, 0) が負の数になりました。long か BigInteger で計算します。

Java の % の符号と0で割ったときの挙動は、関連記事「Java 割り算の小数・切り捨て・余りまとめ｜整数除算と0除算の挙動」で扱っています。

C（gcc 13）と C++17 の std::gcd

#include <stdio.h>

long long gcd(long long a, long long b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) { long long r = a % b; a = b; b = r; }
    return a;
}

int main(void) {
    printf("gcd(1071, 462) = %lld\n", gcd(1071, 462));
    printf("-1071 %% 462 = %d\n", -1071 % 462);
    return 0;
}

gcd(1071, 462) = 21  rec = 21
-1071 % 462 = -147  1071 % -462 = 147
gcd_rec(1071, -462) = -21  gcd(1071, -462) = 21
gcd(0, 0) = 0  gcd(12, 0) = 12
gcd_u(F91, F90) = 1
std::gcd(1071, 462) = 21  std::gcd(-1071, 462) = 21  std::lcm(1071, 462) = 23562  std::gcd(0, 0) = 0

• C の標準ライブラリには gcd がありません。C++ は C++17 から <numeric> の std::gcd・std::lcm が使え、両方0なら0、それ以外は |m| と |n| の最大公約数を返します（cppreference）。
• C の % も割られる数の符号になります（−147）。
• 64ビットの unsigned long long なら、19桁のフィボナッチ数の組も正しく1になりました。

4言語の違いのまとめ

再帰と反復の違い（RecursionErrorの実物と4言語の実行時間）

この節では、互除法を再帰で書くか反復（ループ）で書くかの違いと、実際の速さが分かります。

再帰版は式 gcd(a, b) = gcd(b, a mod b) をそのまま書けて読みやすく、反復版は呼び出しの深さの上限を気にせずに済みます。 普通の大きさの数なら、どちらも結果は同じです。

Python の再帰は約1000段で止まる

Python は再帰の深さに上限（既定 1000）があります。割り算の回数が999回になる、隣り合うフィボナッチ数（1001番目と1000番目、約209桁）で試しました。

recursionlimit 1000
900 1 ok
1000 RecursionError: maximum recursion depth exceeded
1000 iter 1 math 1
1200 RecursionError: maximum recursion depth exceeded
1200 iter 1 math 1

901番目と900番目の組は再帰でも計算できましたが、1001番目と1000番目では RecursionError になりました。同じ組でも反復版と math.gcd は1を返しています。ふつうの乱数で1000桁の組でも平均1940回の割り算が必要になる（次の節の実測）ため、大きな数を扱うプログラムでは反復版か組み込み関数を使います。Java の再帰が深すぎるときのエラーは、関連記事「Java StackOverflowErrorの原因と対処｜再帰と-Xss早見表」で扱っています。

100万回の実行時間（4言語）

gcd(1071, 462) と gcd(1072, 462) を交互に100万回計算し、3回測った値です（同じ機械。Java は JIT の暖まり方で揺れました）。

Python では、数が大きくなるほど組み込みの math.gcd と自作の差が開きました。どの言語でも、互除法そのものが速いため、ふつうのプログラムで gcd が遅さの原因になることはまずありません。

ステップ数の実測（フィボナッチ数で最悪になる理由）

この節では、互除法が何回の割り算で終わるのかと、いちばん回数が多くなる組がフィボナッチ数であることが、実測で分かります。

割り算の回数がいちばん多くなるのは、隣り合うフィボナッチ数（1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…）の組です。 商が（最後を除いて）いつも1になり、数が1回あたり最も少ししか減らないためです。

範囲ごとの最大回数と平均

1 ≦ b ≦ a ≦ N のすべての組を数え上げました。

最大になった組は、どの範囲でもその範囲で最も大きい「隣り合うフィボナッチ数」でした。上限が10倍になっても、最大の回数は4〜5回しか増えません。

---
config:
  xyChart:
    width: 480
    height: 300
---
xychart-beta
    title "N 以下の組での最大の割り算回数"
    x-axis "N" [10, 100, 1000, 10000]
    y-axis "回数" 0 --> 20
    bar [4, 9, 14, 18]

隣り合うフィボナッチ数での回数

k+1番目と k番目の組では、割り算の回数はちょうど k−1 回でした。55 と 34 の手順は次のとおりで、最後以外の商がすべて1です。

gcd(55, 34) の手順
  1: 55 = 34 × 1 + 21
  2: 34 = 21 × 1 + 13
  3: 21 = 13 × 1 + 8
  4: 13 = 8 × 1 + 5
  5: 8 = 5 × 1 + 3
  6: 5 = 3 × 1 + 2
  7: 3 = 2 × 1 + 1
  8: 2 = 1 × 2 + 0
  → 最大公約数 1（割り算 8 回）

ラメの定理（桁数の5倍以下）と平均の回数

• ラメの定理：割り算の回数は、小さい方の数の10進数での桁数の5倍を超えません（英語版 Wikipedia の Euclidean algorithm の項）。a ≦ 3000 のすべての組（4,501,500 通り）で確かめ、超えた組は0でした。
• 平均の回数：乱数の組で測ると、平均の回数は桁数にほぼ比例しました。理論上の近似（12 × ln2 ÷ π² × ln n、係数は約0.843。n は数の大きさ）と並べます。

桁数が10倍になると、回数もほぼ10倍。 数の大きさではなく桁数に比例するので、数百桁の数でも一瞬で終わります。これが、暗号のような大きな整数を扱う計算で互除法が使われる理由です。

よくある間違い（0・負の数・桁あふれ・小数）とエラー原文

この節では、互除法のプログラムでつまずきやすい場面と、そのとき実際に出たエラーや誤った値が分かります。

互除法の落とし穴は、計算の手順ではなく「入ってくる値」に集まっています。 0・負の数・型の上限・小数を、書く前に決めておきます。

C の落ちる例は、次のように「余りを先に計算してから while に入る」書き方で、b に0が来たときに起きました。

int gcd_bad(int a, int b) {
    int r = a % b;            /* b が 0 だとここで落ちる */
    while (r) { a = b; b = r; r = a % b; }
    return b;
}

$ ./div0
Floating point exception
exit=136

負の数の答えは「0以上」にそろえる

数学では、最大公約数はふつう0以上の数として扱います。Python の math.gcd、Java の BigInteger.gcd、C++ の std::gcd は、負の数を渡しても0以上を返しました。自分で書く関数も、組み込み関数と同じく「絶対値で計算し、0以上を返す」にそろえると、言語を移しても結果が変わりません。

• 1b が0かを、割る前に確かめているwhile (b != 0) の形なら、gcd(12, 0) も gcd(0, 0) も落ちない
• 2答えを0以上にそろえている絶対値を取る。int の最小値だけは広い型で
• 3最小公倍数は a ÷ gcd × b の順0 が来たら0を返す（0で割らないため）
• 4型の上限を超える数は多倍長整数JS は BigInt、Java は BigInteger、Python は int のまま
• 5入力が整数かを確かめているNaN・小数・文字列は先に弾く

入試・基本情報技術者試験での出題のされ方

この節では、互除法が高校数学と IT の資格試験でどのように扱われているかが、公開されている資料の範囲で分かります。

高校数学では、文部科学省の学習指導要領解説（平成30年告示、数学編・理数編）で、数学Aの「数学と人間の活動」の中に「ユークリッドの互除法や二進法」が挙げられています。 整数の性質とあわせて、最大公約数を求める手順・一次不定方程式（ax + by = c の整数解）として学びます。

IT の試験では、IPA（情報処理推進機構）が公開している基本情報技術者試験の科目B のサンプル問題に、擬似言語で書かれた最大公約数を求める関数の空欄を選ぶ問題があります。 割り算ではなく差を使う形でした。ここでは問題文は転載せず、問われる力をまとめます。

過去の問題そのものは、IPA の公式サイトで公開されている問題冊子で確かめられます。引き算版の手順は、この記事の「最大公約数の求め方3つの比較」の注意書きにある回数の違いもあわせて押さえておくと、空欄の候補を絞りやすくなります。

判断表：最大公約数をどの方法・関数で求めるか

この節では、手計算とプログラムのそれぞれで、どの方法を選べばよいかが分かります。

迷ったら、上から順に当てはまるものを選びます。

1. 1言語に gcd 関数がある → それを使うPython は math.gcd（3.15 以降は math.integer.gcd も）、Java は BigInteger.gcd、C++17 は std::gcd
2. 2自分で書く → while の反復版0 と負の数の扱いを決め、答えを0以上にそろえる
3. 3型の上限を超える → 多倍長整数JS は BigInt、Java は BigInteger
4. 4x・y も要る → 拡張ユークリッドの互除法逆数だけなら Python の pow(a, -1, m)、Java の modInverse
5. 5手で計算する小さな数 → 素因数分解かすだれ算最小公倍数も同時に出せる
6. 6手で計算する大きな数・素数が混じる → 互除法391 と 323 のような組でも割り算4回

1920 と 1080 の最大公約数が120であることも、math.gcd(1920, 1080) で確かめています。

よくある質問

Q. ユークリッドの互除法を一言でいうと何ですか？ A. 「大きい数を小さい数で割り、割った数を余りで割る」を余りが0になるまで繰り返し、最後に割った数を最大公約数とする方法です。1071 と 462 なら3回で21が出ます。

Q. 小さい数を先に書いても計算できますか？ A. できます。gcd(462, 1071) は1回目が「462 = 1071 × 0 + 462」となり、2つの数が入れ替わるだけです。手元の実行では割り算が1回増えて4回になり、答えは同じ21でした。

Q. 余りが0になったら、何を答えにすればよいですか？ A. その割り算の「割る数」です。147 = 21 × 7 + 0 なら21が答えです。余りの0や商の7と取り違えやすいので注意します。

Q. 互除法の証明はどう書けばよいですか？ A. a = bq + r のとき「a と b の公約数は r も割り切る」「b と r の公約数は a も割り切る」の2つを示し、公約数の集まりが同じだから最大公約数も同じ、と結びます。加えて、余りが小さくなり続けるので必ず終わることを書きます。

Q. 0 と 0 の最大公約数はいくつですか？ A. プログラムでは0と決めているものが多く、Python の math.gcd、Java の BigInteger.gcd、C++ の std::gcd はいずれも0を返しました。どの数でも0を割り切れるため「最大」が決まらないので、0 と 0 は約束ごととして0にしています。

Q. 負の数の最大公約数はどうなりますか？ A. 絶対値の最大公約数として、0以上の数で答えるのが一般的です。gcd(−1071, 462) は21です。自分で書いた関数は −21 を返すことがあるので、絶対値を取ります。

Q. 互除法は何回くらいで終わりますか？ A. 小さい方の桁数の5倍以下です（ラメの定理）。手元の実測では、1万以下の組で最大18回、1000桁の乱数の組で平均1940.6回でした。いちばん回数が多いのは隣り合うフィボナッチ数の組です。

Q. 最小公倍数はどう求めますか？ A. a ÷ gcd(a, b) × b です。1071 と 462 なら 1071 ÷ 21 × 462 = 23562。プログラムでは割り算を先にして、桁あふれを避けます。

Q. 拡張ユークリッドの互除法とは何ですか？ A. 互除法の途中の式を逆にたどり、ax + by = gcd(a, b) を満たす整数 x・y を求める方法です。1071 × (−3) + 462 × 7 = 21。逆数（モジュラ逆数）や一次不定方程式に使います。

Q. 引き算だけの互除法と割り算の互除法はどう違いますか？ A. 割り算は引き算をまとめて行ったものなので、答えは同じです。ただし回数は大きく変わり、1000000000 と 7 では引き算142857148回、割り算3回でした。

Q. 再帰と反復はどちらで書くべきですか？ A. 学ぶときは式をそのまま書ける再帰版、使うときは反復版か組み込み関数がおすすめです。Python では再帰の深さが既定で1000段までで、約209桁の隣り合うフィボナッチ数で RecursionError になりました。

まとめ

• ユークリッドの互除法は「割った数を余りで割る」を余りが0になるまで繰り返し、最後に割った数を最大公約数とする方法。1071 と 462 は割り算3回で21。
• 成り立つ理由は、a = bq + r のとき a・b の公約数と b・r の公約数が同じになるから。余りは小さくなり続けるので必ず終わる。
• 最小公倍数は a ÷ gcd × b（23562）。拡張互除法で 1071 × (−3) + 462 × 7 = 21 のような x・y も求まる。
• Python は math.gcd（3.15 からは math.integer.gcd も）、Java は BigInteger.gcd、C++17 は std::gcd。JavaScript の大きな数は BigInt で、Number では答えが 2048 にずれた。
• 回数は桁数に比例し、最悪は隣り合うフィボナッチ数（1万以下で最大18回）。0・負の数・桁あふれ・NaN を先に決めておくと、プログラムでつまずかない。

参考・出典

確認日はいずれも 2026年10月29日です。

• Python「math — Mathematical functions」（gcd・lcm の追加版と soft deprecated の記載）：https://docs.python.org/3/library/math.html
• Python「math.integer — Integer-specific mathematics functions」（gcd・lcm の定義）：https://docs.python.org/3/library/math.integer.html
• MDN「剰余 (%)」：https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/Remainder
• Oracle「BigInteger（Java SE 21 & JDK 21）」：https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/math/BigInteger.html
• cppreference「std::gcd」：https://en.cppreference.com/w/cpp/numeric/gcd
• Wikipedia（英語版）「Euclidean algorithm」（ラメの定理・平均の回数の係数・『原論』での掲載箇所）：https://en.wikipedia.org/wiki/Euclidean_algorithm
• 文部科学省「高等学校学習指導要領（平成30年告示）解説 数学編 理数編」：https://www.mext.go.jp/content/20230217-mxt_kyoiku02-100002620_05.pdf
• IPA「基本情報技術者試験 科目B サンプル問題」：https://www.ipa.go.jp/shiken/syllabus/henkou/2022/gmcbt80000007cfs-att/fe_kamoku_b_set_sample_qs.pdf

株式会社RJC ― SI事業・SES事業・AI駆動開発。RJCは一緒に成長を楽しめる会社です。