Greatest Common Divisor (GCD) and Least Common Multiple (LCM)
Definitions and Properties
GCD (greatest common divisor): the greatest of the common divisors of two or more integers
LCM (least common multiple): the smallest positive common multiple of two or more integers
Finding Them by Prime Factorization
GCD → take the common prime factors with the smaller exponents
LCM → take all prime factors with the larger exponents
Example ①
Find GCD(72, 120) and LCM(72, 120).
72 = 2³×3²、120 = 2³×3×5
GCD = 2³×3 = 24、LCM = 2³×3²×5 = 360
Find GCD(72, 120) and LCM(72, 120).
72 = 2³×3²、120 = 2³×3×5
GCD = 2³×3 = 24、LCM = 2³×3²×5 = 360
Important Formula
GCD(a,b) × LCM(a,b) = a × b
Example ② (Application of the Formula)
If GCD(a,b)=6 and LCM(a,b)=180, find a×b.
a×b = GCD×LCM = 6×180 = 1080
If GCD(a,b)=6 and LCM(a,b)=180, find a×b.
a×b = GCD×LCM = 6×180 = 1080
Key Points
- GCD×LCM=a×b (for two integers)
- If GCD(a,b)=d, then a=dm and b=dn (m,n are relatively prime)
- LCM(a,b)=dmn
Practice Problems
- Using prime factorization, find GCD(84, 126) and LCM(84, 126).
- If GCD(a,b)=4 and a=20, find the possible values of b (assume b＜50).
- Two natural numbers have sum 100 and GCD 4. Find the LCM. Assume one number is a=4m.
Solutions and Explanations
- 84=2²×3×7、126=2×3²×7. GCD=2×3×7=42、LCM=2²×3²×7=252
- a=20=4×5. Since GCD(a,b)=4, b=4n (5 and n are relatively prime). b＜50 → n=1,2,3,4,7,… values relatively prime to 5 → b=4,8,12,28,32,36,44,48 (n must not be a multiple of 5)
- a=4m、b=4n (GCD=4、m+n=25、m,n are relatively prime). LCM=4mn. Relatively prime pairs with m+n=25 include (m,n)=(1,24),(2,23),(3,22)… If no pair is specified, express the LCM as 4mn.