メインコンテンツへスキップ
CalcMax

最大公約数計算

計算結果

12

最大公約数

公約数
1, 2, 3, 4, 6, 12

最大公約数は、いくつかの数のすべてを余りなく割り切るいちばん大きな整数です。24、36、60なら12です。12より大きい数は3つとも割り切れず、3つとも割り切る数、つまり1、2、3、4、6、12がこの3つの公約数です。このページはその答えの両方の半分を印字します。いちばん大きな値だけでは述べるのは簡単でも確かめるのは難しく、公約数の一覧があればその値がどこから来たのかが見えるからです。答えに至る道は3つあり、どれも知っておく価値があります。1つ目は各数の約数を書き出し、共通する中でいちばん大きなものを残す方法で、下の表が24、36、60についてそれをしています。2つ目は各数を素因数分解し、共通して現れる素因数だけを、共通して現れる回数だけ残す方法です。24は2³ × 3、36は2² × 3²、60は2² × 3 × 5なので、3つに共通するのは2²と3が1つで、2² × 3 = 12です。素因数分解は、数が大きくても分解できるときの一押しの方法です。答えがなぜその値なのかを説明してくれるからです。3つ目はユークリッドの互除法で、2つの数のうち大きいほうを、小さいほうで割った余りに置き換える操作を繰り返します。1,071と462なら1,071 → 147 → 21となり、最後の0でない余りが答えの21です。素因数分解がまったく要らないので、目で分解できない大きさの数にも使える方法です。公約数が1だけの2つの数を互いに素と呼び、その最大公約数は1です。9と20は互いに素で、連続する2つの整数もつねに互いに素です。最大公約数は分数を約分するのに使います。24/36の分子と分母を12で割ると2/3になり、これは分母をできるだけ小さく書いた同じ数です。

既定の入力である24、36、60の約数と素因数分解

数素因数分解約数
242^3 * 31, 2, 3, 4, 6, 8, 12, 24
362^2 * 3^21, 2, 3, 4, 6, 9, 12, 18, 36
602^2 * 3 * 51, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

約数の列を上から下へ読むと、3つの行すべてに現れる数が共通する数です。1、2、3、4、6、12の6つで、その中でいちばん大きいものが答えです。素因数分解の列は同じことを別の言い方で示していて、拡張できるのはこちらのほうです。共通する素因数は2²と3で、2² × 3 = 12です。共通部分は共通する素因数のいちばん小さな冪であって、いちばん大きな冪ではないことに注意してください。36は3²を持ちますが24は3¹しか持たず、約数は24も割り切れなければならないので、3は1つだけ引き継がれます。60がほかの2つにはまったく無い素因数5を持ち込んでいて、それがそのまま答えから落ちることも見てください。約数はリストのすべての数を割り切らなければならず、どれか1つに無い素因数は答えにも無いからです。この表は入力した数には追随しません。上のパネルは入力に答え、この表は3つの方法が1つの例で出会うところを見せています。

公式

24 = 2³ × 3、36 = 2² × 3²、60 = 2² × 3 × 5 ⇒ gcf(24, 36, 60) = 2² × 3 = 12、3つの公約数（1, 2, 3, 4, 6, 12）

24, 36, 60
比べる数で、2個から10個まで、それぞれ1から1,000,000までの整数です。区切りは空白、コンマ、セミコロンで、24 36 60と24, 36, 60は同じ入力です。小数点や分数の線は丸めずに拒否し、0も拒否します。0と0の最大公約数には統一された約束事がなく、このページが代わりに選ぶことはしないからです
2³ × 3
24の素因数分解で、2が3つと3が1つです。1より大きい整数はどれもこの分解をちょうど1通りしか持たず、それが2つ目の方法の根拠になっています
2² × 3
3つの分解が一致する部分、つまり2が2つと3が1つで、4 × 3 = 12です。規則は共通する素因数のいちばん小さな冪を取ることで、いちばん大きな冪ではありません。約数はリストのすべての数を割り切らなければならないので、いちばん渋い数の許す量を超えることはできないからです
1, 2, 3, 4, 6, 12
すべての公約数を小さい順に並べたものです。最後の1つが最大公約数で、この一覧がその検算になります。12は24、36、60を余りなく割り切り、その1つ上の18は36しか割り切りません
gcf(a, b, c) = gcf(gcf(a, b), c)
3つ以上の数を扱う方法で、2つずつ、途中の答えを次の数に畳み込んでいきます。別の方法ではなく、2つの数の方法を繰り返し当てているだけです。だから3つの数でも、どの2つから始めてもこのページは同じ答えを出します
互いに素
公約数が1だけの組の呼び名で、最大公約数は1になります。9と20はどちらも素数ではありませんが互いに素で、連続する2つの整数はつねに互いに素です

いちばん身近な使い方は分数の約分です。24/36は分子と分母を12で割ると2/3になり、この手順はこのサイトの分数のページがどれも最初に行うものです。レシピや図を最小の整数比に縮めるのも同じ操作の別の姿です。24 : 36 : 60と書かれた配合は2 : 3 : 5と同じ配合で、ラベルに収まるのは後のほうです。算数の課題では最大公約数を直接尋ねられ、印字される公約数の一覧がその計算過程になります。当てずっぽうではなく約数を比べて答えを出したことが見えるからです。ほかにも2つの場面があります。長方形をできるだけ大きな正方形のタイルで敷き詰めるのは、姿を変えた最大公約数の問題で、答えがタイルの1辺の長さになります。数論では、2つの数が互いに素であることがいくつかの定理の成り立つ条件になっていて、RSA暗号の背景にある定理もその1つです。法は、使う指数と互いに素なときにだけ安全になるからです。数が扱いにくいとき、たとえば1,071と462では、手作業の素因数分解は現実的でなくなり、ユークリッドの互除法が引き継ぎます。このページの例はどちらの道でも同じ21になることを示しています。

計算例

  1. 24、36、60の最大公約数

    1. 24の約数：1, 2, 3, 4, 6, 8, 12, 24
    2. 36の約数：1, 2, 3, 4, 6, 9, 12, 18, 36
    3. 60の約数：1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
    4. 3つのリストすべてにある数だけを残す：1, 2, 3, 4, 6, 12
    5. その中でいちばん大きいのは12なので、最大公約数は12

    既定の入力で、下の表が最後までたどる例でもあります。代わりに素因数分解でやると、24は2³ × 3、36は2² × 3²、60は2² × 3 × 5で、3つが共有するのは2²と3が1つ、2² × 3 = 12です。価値があるのは公約数の一覧のほうです。8と9は3つのうち2つを割り切るだけで全部は割り切らないので、答えが共通の約数の1つではなく、いちばん大きいものであることを示せる出力はこれだけです。

  2. 扱いにくい数：1,071と462

    1. 1,071 ÷ 462 = 2、余りは147
    2. 462 ÷ 147 = 3、余りは21
    3. 147 ÷ 21 = 7、余りは0。余りが0になったので止める
    4. 最後の0でない余りは21なので、最大公約数は21
    5. 両方を素因数分解して確かめる：1,071 = 3 × 7 × 51、462 = 2 × 3 × 7 × 11なので、共通する部分は3 × 7

    この組こそ、このページにユークリッドの互除法がある理由です。どちらの数も一目では分解できず、約数を手で並べるのは遅くて間違いやすくなります。3回の割り算で決着します。答えの21は両方を割り切るいちばん大きな数でもあり、共通の一覧は1、3、7、21と短くなっています。2つの数に共通点が少ないときの、いつもの印です。

  3. 互いに素な数：9と20

    1. 9の約数：1, 3, 9
    2. 20の約数：1, 2, 4, 5, 10, 20
    3. 2つのリストが共有する約数は1だけ
    4. したがって最大公約数は1

    1という答えは、失敗ではなく正真正銘の答えです。この2つの数は互いに素です。素因数をまったく共有しないときに起きることで、めずらしくはありません。連続する2つの整数はつねに互いに素ですし、素数と、その倍数でない数との組もそうです。このページでは、互いに素な組は公約数の一覧がもっとも短い形、つまり1つだけの1になって返ってきます。

  4. 同じ数を並べた場合：36と36

    1. 36の約数：1, 2, 3, 4, 6, 9, 12, 18, 36
    2. リストの2つの数が同じなので、2つの約数リストは完全に一致する
    3. 共通する約数でいちばん大きいのは36そのもの

    答えが取りうる上限です。最大公約数はリストの中でいちばん小さい数を超えることはできず、いちばん小さい数がほかのすべてを割り切るときにちょうどその上限に届きます。36と36の最大公約数は36で、同じ数を繰り返し挙げても値は変わりません。12、24、36の最大公約数が12になるのも同じ理由です。

適用限界

それぞれの数は1から1,000,000までの整数で、個数は2個から10個までです。0は拒否しますが、これは見落としではなく判断です。0と5の最大公約数は多くの教科書では5ですが、定義しない扱いもあります。0と0の最大公約数は0とする本もあれば、まったく定義しない本もあります。そのどれかを印字すると、別の流儀に従っている読者にとっては誤りになります。だからこのページは正の数を求めます。負の数も同じ種類の理由で拒否します。負の24と36の最大公約数は多くの扱いで12ですが、符号の規則はこのページが述べていない別の約束事です。小数と分数は丸めずに拒否します。最大公約数は整数が整数を割り切るという話であり、2.5 ÷ 1.25は余りが出ないので、答えが意味を失うからです。区切りには空白、コンマ、セミコロンが使え、混ぜてもかまいません。それ以外は数の一部として扱われ、入力が読めなくなります。下の参考表は24、36、60で固定されていて、入力には追随しません。パネルは入力した数に答え、表は方法を示します。同じ数の繰り返しは許され、何も変わりません。答えは常に正確で、丸められることはありません。このページの値はすべて、機械が正確に扱える範囲に十分収まる整数です。

よくある質問

最大公約数を手で求めるにはどうすればよいか
それぞれの数の約数を書き出し、すべてに共通する中でいちばん大きいものを取ります。24、36、60では3つのリストとも12で終わるので、最大公約数は12です。大きい数にはユークリッドの互除法が速い道です。大きいほうを小さいほうで割り、大きいほうをその余りに置き換え、余りが0になるまで繰り返します。1,071と462なら3回の割り算で、答えは21です。どちらの道でも同じ数になり、どちらも上の例で示しています。
最大公約数が1になるとき、それは何を意味するのか
その2つの数が互いに素だということで、何かが失敗した印ではなくごく普通の答えです。9と20は素因数を1つも共有しないので、両方を割り切る数は1だけです。よくあることで、連続する2つの整数はつねに互いに素ですし、素数と、その倍数でない数との組もそうです。この場合、公約数の一覧は1つだけの1になって返ってきます。
0と負の数を拒むのはなぜか
答えがこのページに書いていない約束事に依存するからです。0と5の最大公約数は多くの教科書では5ですが、定義しない扱いもあります。0と0の最大公約数は0とする本もあれば、まったく定義しない本もあります。負の数は別の符号の規則を持ち込みます。どれか1つの流儀を選んで黙って印字するより、このページはすべての出典が一致する1以上の整数を求めます。
素因数分解による方法はどう働くのか
各数を素因数に分解し、すべての数に現れる素因数を、それぞれいちばん小さな冪で取ります。24、36、60なら2²と3なので、答えは12です。いちばん小さな冪でなければならないのは、約数がリストのすべての数を割り切る必要があるからです。36は3²を持ちますが24は3を1つしか持たないので、3をもう1つ足すと24の割り切りが崩れます。素因数分解は扱いにくい数ではユークリッドの互除法より遅いですが、答えを説明してくれます。
答えはリストの中でいちばん小さい数より大きくなることがあるか
ありません。リストの公約数はその中でいちばん小さい数を割り切らなければならないので、その数を超えることはできず、いちばん小さい数がほかのすべてを割り切るときにちょうどその上限に届きます。36と36の最大公約数は36、12、24、36の最大公約数は12です。また1より小さくなることもありません。1はすべての整数を割り切るからです。
最大公約数は何に使われるのか
いちばん多いのは分数の約分です。24/36は両方の部分を12で割ると2/3になり、分母をできるだけ小さく書いた同じ値になります。比を縮めるのも同じ手順で、24 : 36 : 60は2 : 3 : 5と同じ配合です。そして2つの数が互いに素であること、つまり最大公約数が1であることは、数論のいくつかの結果が必要とする条件で、RSA暗号の背景にあるものもその1つです。

参考文献

関連する計算ツール

約分の計算分数を最も簡単な形に約分し、約数も表示。等しい分数の計算ある分数と等しい分数を上限まで一覧表示。最小公倍数計算2〜10個の整数の公倍数を4つ求め、最小公倍数も表示。分数計算分数の足し算・引き算・掛け算・割り算を計算。ユークリッドの互除法計算互除法の手順を追って最大公約数を計算。素因数分解計算整数を素因数に分解し、指数を使って表示。