最大公約数（GCD・GCF）

最大公約数を求めたい整数を、カンマ（,）区切りで2個以上入力してください。3個以上もまとめて計算でき、それぞれの数の素因数分解と共通する素因数も表示します。

最大公約数を求めたい整数（カンマ区切り）

1以上の整数だけをカンマ（,）で区切って入力してください（例：12, 18）。0・負の数・小数は使えません。

計算結果

左の入力欄に整数をカンマ区切りで入れて「計算する」を押すと、ここに結果が表示されます。

このページでできること
この計算は何の役に立つ？
使い方
式
用語・記号の解説
- 記号
- 用語
前提として理解しておくといいこと
Excelで計算する方法
Googleスプレッドシートで計算する方法
Pythonで計算する方法
数式記述言語（LaTeX等）での書き方（コピペ可）
ChatGPTに聞いて計算してもらう方法
計算ドリル（演習問題）
DataChefの特徴
関連機能
NumberChef 機能一覧

このページでできること

カンマ区切りで整数を入れるだけで、最大公約数（英語ではGCD・GCFと呼ばれます）がその場でわかります
2個だけでなく、「16, 88, 104」のように3個以上の整数の最大公約数もまとめて計算できます
それぞれの整数の素因数分解と、共通する素因数もあわせて表示するので、答えの求め方・確かめ方まで学べます
式のやさしい解説・Excel/Googleスプレッドシート/Python用のコピペ数式・計算ドリル（演習問題）もこのページにまとまっています

対象は1以上の整数（正の整数）だけです。0・負の数・小数の最大公約数は扱いません。

この計算は何の役に立つ？

分数の約分（一番身近な出番）

\(\frac{12}{18}\) を約分するとき、分子と分母を最大公約数の 6 で割れば、1回で \(\frac{2}{3}\) まで簡単にできます。
2で割って3で割って…と小さい数で何回も割らなくても、最大公約数を使えば一発で一番簡単な形（既約分数）になります。小学校の算数から大人の実務まで、最大公約数の出番として最も多い使い方です。

ものを余りなく等しく分ける（イベント・配布物の準備）

お菓子24個とジュース36本を、余りを出さずにできるだけ多くの袋に同じ内容で分けたい——作れる袋の数の最大は \(\gcd(24, 36) = 12\) 袋（1袋あたりお菓子2個とジュース3本）です。
学校行事やイベントの景品分け、備品のセット組みなど、「種類の違うものを同じ組に等しく分ける」場面の定番の計算です。

タイル張り・紙の裁断（DIY・設計）

縦330cm×横450cmの床を、正方形のタイルで隙間も余りもなく敷き詰めたいとき、使える最大のタイルは \(\gcd(330, 450) = 30\)（30cm角）です。
長方形を最大の正方形で割り付けるこの計算は、床や壁の施工、大きな紙から同じサイズのカードを無駄なく切り出すときなどに使われています。

歯車の設計（機械・時計）

かみ合う2つの歯車は、歯数の最大公約数が大きいと同じ歯同士が何度も当たり、摩耗が偏りやすくなります。そこで機械設計では、歯数をなるべく互いに素（最大公約数が1）に近づけるのが基本とされています。
自動車や時計の中の歯車の歯数にも、この「最大公約数を小さくする」工夫が生きています。

インターネットの安全を支える暗号技術

ネット通販やネットバンキングで使われるRSA暗号では、鍵を作る過程で「2つの数が互いに素かどうか」の判定が必要で、そこでユークリッドの互除法が使われています。
紀元前に生まれた最大公約数の求め方が、2000年以上たった今、世界中の通信の安全を支えている——数学の息の長さを実感できる応用例です。

式

素因数分解で求める（基本の求め方）

数学表記（一般的な数式）

\(\gcd(a,\ b)\) \(=\) \(p_1 \times p_2 \times \cdots\)

日本語表記（記号を日本語に置き換えた式）

② \(a\) と \(b\) の最大公約数 \(\gcd(a, b)\) \(=\) ① 共通する素因数をすべて掛けたもの

式を日本語で読むと

① 2つの数をそれぞれ素因数分解して、共通する素因数 \(p_1, p_2, \ldots\) をすべて掛け合わせると

② 最大公約数 \(\gcd(a, b)\) になる

簡単な例

12 と 18 の最大公約数は（12 = 2 × 2 × 3、18 = 2 × 3 × 3 と素因数分解でき、共通する素因数は 2 が1個と 3 が1個）

12 と 18 の最大公約数 \(=\) 共通する素因数（2 と 3）を掛けたもの

\(12 = 2 \times 2 \times 3,\quad 18 = 2 \times 3 \times 3\)

\(\gcd(12,\ 18) = 2 \times 3 = 6\)

考え方のポイント

素因数とは、整数を素数だけの掛け算に分解したときの1つ1つの素数のことです。同じ素因数が両方に何回も現れるときは、「少ない方の回数」だけ掛けます。例えば 8 = 2 × 2 × 2 と 12 = 2 × 2 × 3 では、2 が8には3回・12には2回現れるので、共通するのは少ない方の2回分。よって \(\gcd(8, 12) = 2 \times 2 = 4\) です。

ユークリッドの互除法（大きい数に強い求め方）

数学表記（一般的な数式）

\(\gcd(a,\ b)\) \(=\) \(\gcd(b,\ a \bmod b)\)

日本語表記（記号を日本語に置き換えた式）

② \(a\) と \(b\) の最大公約数 \(\gcd(a, b)\) \(=\) ① 「小さい方 \(b\)」と「\(a\) を \(b\) で割った余り」の最大公約数

式を日本語で読むと

① 大きい方を小さい方で割って余りを求め、2つの数の組を「小さい方 \(b\)」と「割った余り \(a \bmod b\)」の組に置き換えても

② 最大公約数 \(\gcd(a, b)\) は変わらない。数がどんどん小さくなっていき、余りが 0 になったときの「割る数」が最大公約数

簡単な例

48 と 18 の最大公約数は（48 ÷ 18 = 2 余り 12 なので）

48 と 18 の最大公約数 \(=\) 「18」と「余り 12」の最大公約数

\(48 = 18 \times 2 + 12\)

\(18 = 12 \times 1 + 6\)

\(12 = 6 \times 2 + 0\)

\(\gcd(48,\ 18) = 6\)

考え方のポイント

素因数分解は、数が大きくなると急に大変になります（134221 のような数を素因数分解するのは骨が折れます。実は 79 × 1699 です）。ユークリッドの互除法なら「割って余りを出す」をくり返すだけで、どんなに大きい数でも確実に最大公約数にたどり着けます。紀元前3世紀ごろのユークリッドの著書「原論」に載っている方法で、「世界最古のアルゴリズム」とも呼ばれます。

3つ以上の数の最大公約数

数学表記（一般的な数式）

\(\gcd(a,\ b,\ c)\) \(=\) \(\gcd(\) \(\gcd(a,\ b)\) \(,\) \(c\) \()\)

日本語表記（記号を日本語に置き換えた式）

③ 3つの数の最大公約数 \(\gcd(a, b, c)\) \(=\) \(\gcd(\) ① まず求めた \(a\) と \(b\) の最大公約数 \(,\) ② 残りの数 \(c\) \()\)

式を日本語で読むと

① まず2つの数の最大公約数 \(\gcd(a, b)\) を求め

② その結果と残りの数 \(c\) の最大公約数をもう一度求めると

③ 3つの数の最大公約数 \(\gcd(a, b, c)\) になる

簡単な例

16 と 88 と 104 の最大公約数は（まず 16 と 88 の最大公約数を求めると 8）

16 と 88 と 104 の最大公約数 \(=\) \(\gcd(\) 16 と 88 の最大公約数（8） \(,\) 残りの数（104） \()\)

\(\gcd(16,\ 88) = 8\)

\(\gcd(8,\ 104) = 8\)

\(\gcd(16,\ 88,\ 104) = 8\)

考え方のポイント

整数が何個あっても、「2つずつ順番に」最大公約数を求めていけば全体の最大公約数になります。4個以上でも同じで、計算する順番を入れ替えても答えは変わりません。このページの計算機も、内部ではこの式のとおり2個ずつ順番に計算しています。

最小公倍数（LCM）との関係

数学表記（一般的な数式）

\(\gcd(a,\ b)\) \(\times\) \(\mathrm{lcm}(a,\ b)\) \(=\) \(a \times b\)

日本語表記（記号を日本語に置き換えた式）

① 最大公約数 \(\gcd(a, b)\) \(\times\) ② 最小公倍数 \(\mathrm{lcm}(a, b)\) \(=\) ③ もとの2つの数の積 \(a \times b\)

式を日本語で読むと

① 最大公約数 \(\gcd(a, b)\) と

② 最小公倍数 \(\mathrm{lcm}(a, b)\) を掛け合わせると

③ いつでももとの2つの数の積 \(a \times b\) に一致する

簡単な例

12 と 18 では（最大公約数は 6、最小公倍数は 36）

最大公約数（6） \(\times\) 最小公倍数（36） \(=\) もとの2つの数の積（12 × 18）

\(6 \times 36 = 216\)

\(12 \times 18 = 216\)

考え方のポイント

この関係を使うと、最大公約数さえわかれば最小公倍数を \(\mathrm{lcm}(a, b) = a \times b \div \gcd(a, b)\) で計算できます（大きい数の最小公倍数は、倍数を書き出すよりこの方法が確実です）。ただし、この関係がそのまま成り立つのは「2つの数」のときだけで、3つ以上の数では一般に成り立たない点に注意してください。

最大公約数は「2つ以上の整数すべてを割り切れる、一番大きい正の整数」です。小さい数なら素因数分解で共通する素因数を掛け合わせ、大きい数なら「割った余りに置き換える」ユークリッドの互除法を使うのがコツです。

用語・記号の解説

記号

\(\gcd(a, b)\)	ジーシーディー	\(a\) と \(b\) の最大公約数を表す記号。英語の greatest common divisor（GCD）の頭文字です。英語圏では greatest common factor（GCF）とも呼ばれ、\(\mathrm{GCF}(a, b)\) と書かれることもありますが、意味はまったく同じです。
\(a \bmod b\)	エー・モッド・ビー	\(a\) を \(b\) で割った余り。（例：\(48 \bmod 18 = 12\) となります。48 ÷ 18 = 2 余り 12 だからです）
\(\mathrm{lcm}(a, b)\)	エルシーエム	\(a\) と \(b\) の最小公倍数を表す記号。英語の least common multiple の頭文字です。（例：\(\mathrm{lcm}(12, 18) = 36\)）
\(p_1, p_2, \ldots\)	ピーいち、ピーに、…	共通する素因数を順に並べたもの。右下の小さい数字（添え字）は「1番目・2番目…」という順番を表しているだけで、計算には使いません。
\(\cdots\)	てんてん（三点リーダー）	「同じ規則でまだ続く」ことを表す省略記号。素因数が何個あっても同じように掛け合わせる、という意味で使っています。

用語

約数	やくすう	ある整数を割り切ることができる正の整数。12の約数は 1, 2, 3, 4, 6, 12 の6個です。
公約数	こうやくすう	2つ以上の整数に共通する約数。12と18の公約数は 1, 2, 3, 6 です。公約数は必ず最大公約数（この例では6）の約数になっています。
最大公約数	さいだいこうやくすう	公約数のうち一番大きいもの。日本の学校ではこの呼び名で習いますが、英語圏ではGCD（greatest common divisor）またはGCF（greatest common factor）と呼ばれます。
素数	そすう	1とその数自身のほかに約数がない、2以上の整数。2, 3, 5, 7, 11, 13, … と続きます。1は素数に含めません。
素因数分解	そいんすうぶんかい	整数を素数だけの掛け算の形に直すこと。（例：\(12 = 2 \times 2 \times 3\)）分解に使われた1つ1つの素数を素因数といいます。
互いに素	たがいにそ	2つの整数の最大公約数が1であること（公約数が1しかないこと）。17と13のように、共通する素因数を1つも持たない関係です。
ユークリッドの互除法	ユークリッドのごじょほう	「大きい方を小さい方で割り、組を『小さい方と余り』に置き換える」をくり返して最大公約数を求める方法。高校の数学Aで習います。紀元前から知られる「世界最古のアルゴリズム」とも呼ばれます。
最小公倍数	さいしょうこうばいすう	2つ以上の整数に共通する倍数のうち、一番小さい正の整数。分数の通分で使います。2つの数では \(\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b\) の関係があります。

前提として理解しておくといいこと

このページの計算を「意味がわかって」使えるようになるために、前提として理解しておくといいことをまとめました。
つまずいたら、この表の内容に戻って復習するのが近道です。

九九・余りのある割り算（小学2〜3年）	「割り切れる」と「余りが出る」の区別がつくこと 48 ÷ 18 = 2 余り 12 のような、余りのある割り算ができること
約数と公約数（小学5年）	12の約数を 1, 2, 3, 4, 6, 12 とすべて書き出せること 2つの数に共通する約数（公約数）を見つけられること
分数の約分（小学5年）	分子と分母を同じ数で割っても、分数の大きさが変わらないとわかること
素数と素因数分解（中学1年）	素数（1とその数自身のほかに約数がない数）を見分けられること \(12 = 2 \times 2 \times 3\) のように、整数を素数の掛け算の形に分解できること

Excelで計算する方法

Excelファイルをダウンロード

式ごとにシートが分かれたExcelファイルです。貼り付け場所を気にせず、開いてすぐ使えます。

下の表を丸ごとコピーして、ExcelのA1セルに貼り付けるとそのまま使えます。

「2つの数の最大公約数」を求める表

1つ目の整数 a	12
2つ目の整数 b	18
最大公約数 gcd(a, b)	=GCD(B1,B2)

「3つ以上の数の最大公約数」を求める表

整数1	16
整数2	88
整数3	104
最大公約数	=GCD(B1:B3)

「ユークリッドの互除法」を確かめる表

大きい方 a	48
小さい方 b	18
a を b で割った余り（a mod b）	=MOD(B1,B2)
gcd(a, b)	=GCD(B1,B2)
gcd(b, 余り)（上と一致します）	=GCD(B2,B3)

「最大公約数×最小公倍数＝もとの2数の積」を確かめる表

1つ目の整数 a	12
2つ目の整数 b	18
最大公約数 gcd(a, b)	=GCD(B1,B2)
最小公倍数 lcm(a, b)	=LCM(B1,B2)
gcd × lcm	=B3*B4
a × b（上と一致します）	=B1*B2

Excelには最大公約数を求めるGCD関数が最初から用意されています。「=GCD(B1,B2)」は「B1とB2の値の最大公約数」という意味で、1つ目の表ならB3に 6 と表示されます。
2つ目の表のように「=GCD(B1:B3)」と範囲で指定すれば、3個以上の数もまとめて計算できます（B4に 8 と表示されます）。
3つ目の表はユークリッドの互除法の確認用で、MOD関数（割った余り）を使うと gcd(a, b) と gcd(b, 余り) が同じ値（どちらも6）になることを確かめられます。
4つ目の表では、gcd × lcm と a × b がどちらも 216 になり、最小公倍数との関係式を確かめられます。入力欄の数値を自分の整数に書き換えるだけでそのまま使えます。

Googleスプレッドシートで計算する方法

Excelファイルをダウンロード

上のExcelファイルをダウンロードし、Googleドライブにアップロードして開くと、そのままスプレッドシートとして使えます。

下の表を丸ごとコピーして、GoogleスプレッドシートのA1セルに貼り付けるとそのまま使えます。

「2つの数の最大公約数」を求める表

1つ目の整数 a	12
2つ目の整数 b	18
最大公約数 gcd(a, b)	=GCD(B1,B2)

「3つ以上の数の最大公約数」を求める表

整数1	16
整数2	88
整数3	104
最大公約数	=GCD(B1:B3)

「ユークリッドの互除法」を確かめる表

大きい方 a	48
小さい方 b	18
a を b で割った余り（a mod b）	=MOD(B1,B2)
gcd(a, b)	=GCD(B1,B2)
gcd(b, 余り)（上と一致します）	=GCD(B2,B3)

「最大公約数×最小公倍数＝もとの2数の積」を確かめる表

1つ目の整数 a	12
2つ目の整数 b	18
最大公約数 gcd(a, b)	=GCD(B1,B2)
最小公倍数 lcm(a, b)	=LCM(B1,B2)
gcd × lcm	=B3*B4
a × b（上と一致します）	=B1*B2

GoogleスプレッドシートにもGCD・LCM・MOD関数がExcelと同じ名前で用意されているので、同じ式がそのまま使えます。
表を丸ごとコピーしてA1セルに貼り付け、入力欄の数値を自分の整数に書き換えてください。

Pythonで計算する方法

from math import gcd
from functools import reduce

numbers = [330, 75, 450, 225]  # 最大公約数を求めたい整数のリスト（何個でもOK）

greatest_common_divisor = reduce(gcd, numbers)  # 先頭から2個ずつ順番にgcdを計算する

print(f"{numbers} の最大公約数: {greatest_common_divisor}")

標準ライブラリだけで動きます。math.gcd が2つの整数の最大公約数を求める関数で、reduce が「2個ずつ順番に計算する」の部分を自動化しています。先頭のリストを自分の整数に書き換えて実行してください（この例では 15 と表示されます）。

数式記述言語（LaTeX等）での書き方（コピペ可）

素因数分解で求める（基本の求め方）

gcd(a, b) = p₁ × p₂ × ⋯

\gcd(a, b) = p_1 \times p_2 \times \cdots

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <msub><mi>p</mi><mn>1</mn></msub>
    <mo>&#xD7;</mo>
    <msub><mi>p</mi><mn>2</mn></msub>
    <mo>&#xD7;</mo>
    <mo>&#x22EF;</mo>
  </mrow>
</math>

gcd(a, b) = p_1 xx p_2 xx cdots

GCD[a, b]

igcd(a, b);

g = gcd(a, b);

gcd(a, b) = p_1 × p_2 × ⋯

ユークリッドの互除法（大きい数に強い求め方）

gcd(a, b) = gcd(b, a mod b)

\gcd(a, b) = \gcd(b,\ a \bmod b)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <mi>gcd</mi>
    <mo>(</mo><mi>b</mi><mo>,</mo>
    <mi>a</mi><mspace width="0.3em"/><mi>mod</mi><mspace width="0.3em"/><mi>b</mi>
    <mo>)</mo>
  </mrow>
</math>

gcd(a, b) = gcd(b, a mod b)

GCD[a, b] == GCD[b, Mod[a, b]]

igcd(a, b) = igcd(b, a mod b);

gcd(a, b) == gcd(b, mod(a, b))

gcd(a, b) = gcd(b, a mod b)

3つ以上の数の最大公約数

gcd(a, b, c) = gcd(gcd(a, b), c)

\gcd(a, b, c) = \gcd(\gcd(a, b),\ c)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>)</mo>
    <mo>=</mo>
    <mi>gcd</mi>
    <mo>(</mo>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>,</mo><mi>c</mi>
    <mo>)</mo>
  </mrow>
</math>

gcd(a, b, c) = gcd(gcd(a, b), c)

GCD[a, b, c]

igcd(igcd(a, b), c);

g = gcd(gcd(a, b), c);

gcd(a, b, c) = gcd(gcd(a, b), c)

最小公倍数（LCM）との関係

gcd(a, b) × lcm(a, b) = a × b

\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mi>lcm</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <mi>a</mi>
    <mo>&#xD7;</mo>
    <mi>b</mi>
  </mrow>
</math>

gcd(a, b) xx lcm(a, b) = a xx b

GCD[a, b]*LCM[a, b] == a*b

igcd(a, b)*ilcm(a, b) = a*b;

gcd(a, b)*lcm(a, b) == a*b

gcd(a, b) × lcm(a, b) = a × b

ChatGPT に聞いて計算してもらう方法

あなたは整数計算のアシスタントです。次の計算を、必ずPythonコードを実際に実行して行い、実行結果の数値だけを根拠に回答してください（暗算や推測で答えないでください）。

330, 75, 450, 225 の4つの整数について、次をそれぞれ求めてください。
1. 4つの整数の最大公約数
2. それぞれの整数の素因数分解
3. 4つの整数に共通する素因数

計算に使った式と、実行結果の数値を示してください。