最大公約数（GCD）・最小公倍数（LCM）
定義と性質
GCD（最大公約数）：2つ以上の整数の共通の約数のうち最大のもの
LCM（最小公倍数）：2つ以上の整数の公倍数のうち最小の正のもの
素因数分解による求め方
GCD → 共通する素因数を小さい方の指数で取る
LCM → すべての素因数を大きい方の指数で取る
📘 例題①
GCD(72, 120) と LCM(72, 120) を求めよ。
72 = 2³×3²、120 = 2³×3×5
GCD = 2³×3 = 24、LCM = 2³×3²×5 = 360
GCD(72, 120) と LCM(72, 120) を求めよ。
72 = 2³×3²、120 = 2³×3×5
GCD = 2³×3 = 24、LCM = 2³×3²×5 = 360
重要な公式
GCD(a,b) × LCM(a,b) = a × b
📘 例題②（公式の応用）
GCD(a,b)=6、LCM(a,b)=180 のとき a×b を求めよ。
a×b = GCD×LCM = 6×180 = 1080
GCD(a,b)=6、LCM(a,b)=180 のとき a×b を求めよ。
a×b = GCD×LCM = 6×180 = 1080
💡 ポイント
- GCD×LCM=a×b（2整数のとき）
- GCD(a,b)=d とすると a=dm、b=dn（m,n は互いに素）
- LCM(a,b)=dmn
練習問題
- GCD(84, 126) と LCM(84, 126) を素因数分解を使って求めよ。
- GCD(a,b)=4、a=20 のとき b の候補を求めよ（b＜50 として）。
- 2つの自然数の和が100、GCDが4のとき、LCMを求めよ。ただし一方を a=4m とする。
解答・解説
- 84=2²×3×7、126=2×3²×7。GCD=2×3×7=42、LCM=2²×3²×7=252
- a=20=4×5。GCD(a,b)=4 より b=4n（5とnは互いに素）。b＜50 → n=1,2,3,4,7,… で5と互いに素な値 → b=4,8,12,28,32,36,44,48（nが5の倍数でなければよい）
- a=4m、b=4n（GCD=4、m+n=25、m,nが互いに素）。LCM=4mn。m+n=25で互いに素な組(m,n)=(1,24),(2,23),(3,22)…など。特定しない場合は LCM=4mn と表す。