最大公約数

1. 2つ以上の「値」を入力します。
2. 自動的に「最大公約数」「公約数」が表示されます。

最大公約数（Greatest Common Divisor, GCD）とは、複数の整数の中で、全ての数を割り切ることができる最大の正の整数のことです。数学やコンピュータサイエンスで頻繁に使われる概念です。

特徴

• 分母の簡約分数を簡単な形にする際に用いられる。
• 整数の性質数の共通因数（公約数）を調べることで、整数の性質を理解する助けになる。

例

数字 48 と 64 の場合

• 48 の約数：1, 2, 3, 4, 6, 8, 12, 16, 24, 48
• 64 の約数：1, 2, 4, 8, 16, 32, 64
• 両方に共通する約数（公約数）：1, 2, 4, 8, 16
• 最大公約数: 16

応用例

• 暗号学RSA暗号などで使用される。
• 整数の簡約分数や数値の簡約に利用。
• プログラミング数値演算の最適化やアルゴリズム設計で活用。

最大公約数を求める方法

方法1.約数を列挙して求める

以下の手順で最大公約数を求めます。

1. 各数の約数をすべて列挙します。
2. 共通する約数を見つけます。
3. その中で最大の数が最大公約数です。

例:

• 24の約数: 1, 2, 3, 4, 6, 8, 12, 24
• 36の約数: 1, 2, 3, 4, 6, 9, 12, 18, 36
• 共通する約数: 1, 2, 3, 4, 6, 12
• 最大公約数: 12

方法2．ユークリッドの互除法

ユークリッドの互除法は、効率的に最大公約数を求めるアルゴリズムです。

以下の手順で計算を行います。

1. 2つの数のうち大きな数を小さな数で割り、余りを求めます。
2. 小さな数を次の割られる数、余りを次の割る数として繰り返します。
3. 余りが0になった時の割る数が最大公約数です。

例:

• 24 ÷ 36 = 商 0, 余り 24
• 36 ÷ 24 = 商 1, 余り 12
• 24 ÷ 12 = 商 2, 余り 0
• 余りが0になったので、最大公約数は12

このツールは無料でご利用いただけます。