このツールでできること
このツールは、2つ以上の正の整数を入力すると、次の3つを一度に求めます。各数の約数(その数を割り切れる数)の一覧、すべての数に共通する公約数、そして最大公約数(GCF)です。最大公約数は最大公約数(GCD)とも呼ばれます。分数の約分や式の因数分解、整数論の宿題などに役立ちます。
使い方
整数をカンマで区切って入力します。例えば 136, 64, 24, 16 のように入力すると、結果が表示されます。各数の約数は小さい順に並び、続いて公約数、最後に最大公約数(GCF)が1つ表示されます。入力できるのは正の整数のみです。0、負の数、小数は約数の入力としては無効です。
計算のしくみ
整数 \(d\) が \(n\) の約数であるとは、\(n \bmod d = 0\) となること、つまり余りなく割り切れることを意味します。すべての約数を効率よく見つけるには、\(i\) を1から \(n\) の平方根まで動かし、\(i\) が \(n\) を割り切るたびに \(i\) と \(n/i\) の両方を約数として記録します。複数の数の最大公約数は、ユークリッドの互除法を2数ずつ繰り返して求めます。b が0でない間、(a, b) を (b, a mod b) に置き換え、最後に残った a が最大公約数(GCD)です。$$\gcd(a, 0) = a, \quad \gcd(a, b) = \gcd(b, \; a \bmod b)$$ 便利な性質として、全体の公約数はちょうど最大公約数(GCF)の約数と一致します。$$\text{CommonFactors} = \{\, d : g \bmod d = 0 \,\}, \quad g = \gcd(n_1, n_2, \dots)$$
計算例
136, 64, 24, 16 の場合、16 の約数は 1, 2, 4, 8, 16、24 の約数は 1, 2, 3, 4, 6, 8, 12, 24、64 の約数は 1, 2, 4, 8, 16, 32, 64、136 の約数は 1, 2, 4, 8, 17, 34, 68, 136 です。ユークリッドの互除法では \(\gcd(16, 24) = 8\)、次に \(\gcd(8, 64) = 8\)、さらに \(\gcd(8, 136) = 8\) となり、最大公約数(GCF)は 8 です。8 の約数である 1, 2, 4, 8 が、そのまま公約数になります。
異なる種類の数の組における最大公約数(GCF)の結果
最大公約数(GCF)は、数どうしの関係によって決まります。次の表は代表的なケースをいくつか示しています。ある数の組に共通する約数は、その最大公約数の約数とちょうど一致します。
| 数 | GCF | 共通の約数 | 関係の種類 |
|---|---|---|---|
| 8 と 15 | 1 | 1 | 互いに素(1以外に共通の約数がない) |
| 12 と 36 | 12 | 1, 2, 3, 4, 6, 12 | 倍数の関係(36は12の倍数) |
| 18, 24, 30 | 6 | 1, 2, 3, 6 | 3つの数が共通の約数を持つ |
| 17 と 31 | 1 | 1 | 異なる2つの素数(必ず互いに素) |
| 20 と 20 | 20 | 1, 2, 4, 5, 10, 20 | 同一の数(GCFはその数自身) |
| 48 と 180 | 12 | 1, 2, 3, 4, 6, 12 | 素因数の一部が重なる |
48と180の確認: \(48 = 2^4 \cdot 3\) かつ \(180 = 2^2 \cdot 3^2 \cdot 5\)。共通する各素数の最も小さい指数を取ると \(2^2 \cdot 3 = 12\)。
GCFが示すことと、その用途
- GCF = 1 は互いに素を意味する。 数は共通の素因数を持ちません。それ自体が素数である必要はありません。8と15は、どちらも素数ではありませんが互いに素です。
- GCFが最小の数に等しい場合。 その最小の数は、他のすべての数を割り切ります。例えば \(\gcd(12, 36) = 12\) です。
- 分数の約分。 分子と分母をそれらの最大公約数で割ると、分数を一度で既約分数にできます。\(\gcd(24, 36) = 12\) なので、\(\frac{24}{36} = \frac{24 \div 12}{36 \div 12} = \frac{2}{3}\) となります。
- 最大の等しい組。 ペンが24本、鉛筆が36本あり、すべてを使って同じ組を作りたい場合、作れる組の最大数は \(\gcd(24, 36) = 12\) です。各組はペン2本と鉛筆3本になります。
- 正方形のタイル。 48 cm × 180 cm の面積に、切らずにちょうど敷き詰められる最大の正方形タイルの一辺は \(\gcd(48, 180) = 12\) cm です。これは縦4枚、横15枚に相当します。
- 最小公倍数との関係。 2つの正の整数について、\(\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b\) が成り立ちます。例: \(\gcd(12, 18) = 6\)、\(\operatorname{lcm}(12, 18) = 36\) なので、\(6 \cdot 36 = 216 = 12 \cdot 18\)。この恒等式は2つの数についてのみ成り立ち、3つ以上の数には当てはまりません。
重要用語: 因数、約数、GCF、互いに素
- 因数(約数)
- 余りなく数を割り切る正の整数。12の因数は1, 2, 3, 4, 6, 12です。
- 倍数
- ある数と任意の整数の積。4の倍数には4, 8, 12, 16などがあります。\(d\) が \(n\) の因数ならば、\(n\) は \(d\) の倍数です。
- 公約数
- その組のすべての数の因数である数。12と18の公約数は1, 2, 3, 6です。
- GCF / GCD / HCF
- 最大公約数。最大の公約数を指し、最大公約数、最大公因数とも呼ばれます。3つの名称はすべて同じ意味です。
- 互いに素(互いに素な関係)
- 共通の約数が1だけである数の組。そのGCFは1です。
- 素数
- 1より大きい整数で、その正の約数が1と自分自身だけのもの。例えば2, 3, 5, 7, 11, 17, 31などです。
- ユークリッドの互除法
- 組 \((a, b)\) を、余りが0になるまで \((b,\; a \bmod b)\) で繰り返し置き換える方法。最後の0でない値がGCFです。例: \(\gcd(180, 48)\): \(180 = 3 \cdot 48 + 36\)、次に \(48 = 1 \cdot 36 + 12\)、次に \(36 = 3 \cdot 12 + 0\)。よってGCFは12です。3つ以上の数の場合は、段階的に適用します: \(\gcd(\gcd(n_1, n_2), n_3)\)。
よくある質問
GCF と GCD は同じものですか? はい、同じです。「最大公約数(greatest common factor)」と「最大公約数(greatest common divisor)」は同じ値を指す2つの呼び方です。日本語ではどちらも「最大公約数」と訳されます。
共通の約数が1つもない場合は? すべての正の整数は1で割り切れるため、公約数には必ず1が含まれ、最大公約数も少なくとも1になります。共通の約数が1だけの数どうしを「互いに素」と呼びます。
数を1つだけ入力してもよいですか? はい。その場合は入力した数の約数が一覧表示され、最大公約数はその数自身になります。