最大公約数(GCD)計算ツール

最大公約数(GCD)計算ツール

成長中 AI Skill PRO

計算を入力してください

公式

gcd⁡(A,B)=gcd⁡(B,AmodB)\gcd\left(\text{A},\ \text{B}\right) = \gcd\left(\text{B},\ \text{A} \bmod \text{B}\right)
計算手順を表示 (1)
  1. 最小公倍数(LCM)(GCDから算出)

    lcm=|A|×|B|gcd⁡(A,B)\text{lcm} = \frac{\left|\text{A}\right| \times \left|\text{B}\right|}{\gcd\left(\text{A},\ \text{B}\right)}

    最小公倍数は、積を最大公約数(GCD)で割ることで求められます。

利用統計

広告

結果

最大公約数
12
GCD(48, 36)
最大公約数(GCD) 12
最小公倍数(LCM) 144

このページの誤りを報告

最大公約数(GCD)とは?

最大公約数(GCD:Greatest Common Divisor)とは、2つの整数の両方をあまりなく割り切れる、最も大きい正の整数のことです。英語圏では「HCF(highest common factor=最大公因数)」とも呼ばれますが、意味は同じです。たとえば48と36の最大公約数は12です。これは、両方を割り切れる数の中で12が最も大きいためです。この計算ツールを使えば、その値を瞬時に求められるだけでなく、最小公倍数(LCM)も同時に確認できます。

重なり合う2つの約数の集合で、共通の約数が中央に強調表示されている図
最大公約数は、両方の数に共通する最大の約数です。

使い方

「A」と「B」の欄に整数を1つずつ入力すると、結果がすぐに表示されます。入力された数値はそれぞれ絶対値として扱われるため、マイナスの数を入れても正しく計算されます。どちらか一方に0を入力した場合、最大公約数はもう一方の数と等しくなります(どんな整数でも0を割り切れるため)。

ユークリッドの互除法のしくみ

この計算ツールは、現在も広く使われている最古のアルゴリズムの1つ「ユークリッドの互除法」を採用しています。原理は次のシンプルな関係式に基づいています:$$\gcd\left(a,\ b\right) = \gcd\left(b,\ a \bmod b\right)$$。大きいほうの数を、2つの数を割ったときのあまりに置き換える操作をくり返し、あまりが0になるまで続けます。最後に残った0でない除数が最大公約数です。この方法なら素因数分解をする必要がなく、桁数の大きな数でも非常に高速に計算できます。

広告
余りが0になるまで割り算と値の置き換えを繰り返すユークリッドの互除法を示すフローチャートのループ
ユークリッドの互除法は、余りが0になるまで \((a,\ b)\) を \((b,\ a \bmod b)\) に置き換え続けます。

計算例

\(\gcd(48,\ 36)\) を求めてみましょう:

$$48 \bmod 36 = 12 \rightarrow \gcd(36,\ 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12,\ 0) = \mathbf{12}$$

最小公倍数(LCM)は $$\frac{\left|48 \times 36\right|}{12} = \frac{1728}{12} = \mathbf{144}$$ となります。

よくある質問(FAQ)

GCDとHCFの違いは? 違いはありません。同じ値を指す2つの呼び方です。「greatest common divisor(最大公約数)」は主にアメリカで、「highest common factor(最大公因数)」は主にイギリスで使われます。日本ではどちらも「最大公約数」と訳されます。

互いに素な2つの数の最大公約数は? 必ず1になります。たとえば8と15のように、1以外に共通の約数を持たない数は「互いに素(コプライム)」と呼ばれます。

最大公約数が小さいほうの数より大きくなることはある? ありません。最大公約数が2つの数のうち小さいほうを超えることは決してありません。小さいほうの数が大きいほうを割り切れるとき、最大公約数はちょうどその小さいほうの数と等しくなります。

最終更新:

数学と統計で人気の電卓

数学と統計の電卓をすべて見る