最大公約数とは？
さいだいこうやくすう
最大公約数とは、2つ以上の整数に共通する約数の中で最も大きい数のことで、GCDとも略されます。
最大公約数（さいだいこうやくすう）とは、2つ以上の整数すべてを割り切れる整数（公約数）の中で最大のものを指します。英語ではGreatest Common Divisor（GCD）と呼ばれます。たとえば12と18の約数をそれぞれ調べると、12の約数は1・2・3・4・6・12、18の約数は1・2・3・6・9・18です。共通する約数は1・2・3・6で、その中の最大値である6が最大公約数です。
最大公約数の求め方にはいくつかあります。
- 素因数分解：それぞれを素因数分解し、共通する素因数を最小の指数でかけ合わせる。
- ユークリッドの互除法：大きい数を小さい数で割った余りを使って繰り返し割り算する効率的な方法。
ユークリッドの互除法は紀元前から知られる歴史ある手法で、数が大きくなっても素早く計算できるためコンピュータでも広く使われます。
最大公約数は、分数の約分（分子と分母を最大公約数で割る）や、いくつかのものを等しいグループに分ける問題、タイルの最大サイズを求める問題など、日常・理数両面の場面で活用されます。関連する概念として最小公倍数（LCM）があり、「GCD×LCM＝元の2数の積」という関係が成り立ちます。
使い方・例文
72枚と48枚のシールをできるだけ多い人数で同じ枚数ずつ配るとき、最大公約数GCD(72, 48)＝24を求めることで、最大24人に配れると分かります。また12/18の分数を約分するときも、GCD(12,18)＝6で割って2/3にします。
この用語をシェア
最終更新: