ユークリッドの互除法 最大公約数計算ツール

計算を入力してください

値1

値2

結果

https://example.com

最大公約数

4

最大公約数（GCD・GCFとも呼ばれます）

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

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

最大公約数（GCF）は最大公約数（GCD）とも呼ばれ、2つの整数をどちらも割り切る最大の自然数のことです。英語では「greatest common factor」と「greatest common divisor」の2通りの言い方がありますが、いずれも日本語の「最大公約数」を指します。ユークリッドの互除法は、割り算の余りを繰り返し使ってこの値を求める、古代から伝わる非常に効率的な手法です。本ツールは任意の2つの整数の最大公約数を求め、すべての割り算ステップを表示するので、計算の流れを一目で追うことができます。

ユークリッドの互除法は長方形を可能な限り大きい同じ正方形で敷き詰める。その正方形の一辺が最大公約数。

使い方

値1と値2に整数を1つずつ入力してください。ツールは大きい方を割られる数（被除数）、小さい方を割る数（除数）として、余りが0になるまで割り算を繰り返します。最後に余りが0になったときの除数が最大公約数です。最大公約数は数の大きさだけで決まるため、入力する順番は関係なく、マイナスの符号も無視されます。

計算式の解説

各ステップでは、商と余りを次のように求めます。\(a = c \times b + R\)（ここで \(c = \lfloor a / b \rfloor\)、\(R = a \bmod b\)）。次に \(a\) を \(b\) に、\(b\) を \(R\) に置き換えて同じ計算を繰り返します。余りは必ず1つ前の除数より小さくなるため、この手順は必ず終わります。\(R = 0\) になったとき、そのときの除数が答えです。再帰の形で書くと、$$\gcd(a, b) = \gcd(b, a \bmod b),\quad \gcd(a, 0) = a$$ となります。

広告

計算例

GCF(816, 2260) を求めてみましょう。\(a = 2260\)、\(b = 816\) とします。

$$2260 = 2 \times 816 + 628$$ $$816 = 1 \times 628 + 188$$ $$628 = 3 \times 188 + 64$$ $$188 = 2 \times 64 + 60$$ $$64 = 1 \times 60 + 4$$ $$60 = 15 \times 4 + 0$$ 除数が4のときに余りが0になるので、GCF(816, 2260) = 4 です。

各ステップで (a, b) を (b, a mod b) に置き換え、余りが0になるまで続ける。最後の0でない除数が最大公約数。

よくある質問

GCFとGCDは同じものですか？ はい、同じです。英語の「greatest common factor」と「greatest common divisor」はどちらも日本語の「最大公約数」を意味する同義語で、本ツールはどちらの呼び方にも対応しています。

片方の入力が0のときは？ \(\gcd(a, 0) = a\) です。すべての数は0を割り切るためです。なお、両方とも0の場合、最大公約数は定義されません。

3つの数の最大公約数は求められますか？ 2つずつ順に適用すれば求められます。$$\gcd(x, y, z) = \gcd(\gcd(x, y), z)$$ となります。