Skip to main content
AMC 10 & 12

Divisibility, GCD & LCM

Prime factorization, the Euclidean algorithm, and counting divisors — the vocabulary every other number theory topic assumes you already know.

Prime factorization

Every integer greater than 1 has a unique prime factorization (the Fundamental Theorem of Arithmetic). Writing n=p1e1p2e2⋯pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} unlocks a clean formula for the number of divisors:

d(n)=(e1+1)(e2+1)⋯(ek+1)d(n) = (e_1+1)(e_2+1)\cdots(e_k+1)

(Add 1 to each exponent because each prime’s power in a divisor can range from 00 toeie_i, giving ei+1e_i+1 independent choices, then multiply the choices together.)

GCD and LCM

The greatest common divisor and least common multiple of two numbers are always linked by their product:

gcd⁡(a,b)⋅lcm⁡(a,b)=a⋅b\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b

The fastest way to compute a GCD by hand is the Euclidean algorithm, which repeatedly replaces the larger number with the remainder of dividing it by the smaller:

gcd⁡(a,b)=gcd⁡(b, a mod b),gcd⁡(a,0)=a\gcd(a,b) = \gcd(b,\ a \bmod b), \qquad \gcd(a,0)=a

Worked example

Problem: Find gcd⁡(252,105)\gcd(252, 105) using the Euclidean algorithm.

Solution:

gcd⁡(252,105)=gcd⁡(105, 252 mod 105)=gcd⁡(105,42)\gcd(252,105) = \gcd(105,\ 252 \bmod 105) = \gcd(105, 42)
=gcd⁡(42, 105 mod 42)=gcd⁡(42,21)=gcd⁡(21, 42 mod 21)=gcd⁡(21,0)=21= \gcd(42,\ 105\bmod42) = \gcd(42,21) = \gcd(21,\ 42\bmod21)=\gcd(21,0)=21

So gcd⁡(252,105)=21\gcd(252,105)=21. As a check via prime factorization: 252=22⋅32⋅7252=2^2\cdot3^2\cdot7, 105=3⋅5⋅7105=3\cdot5\cdot7, common factors give 3⋅7=213\cdot7=21 ✓.

Practice problems

1.How many positive divisors does 360360 have? (360=23⋅32⋅5360=2^3\cdot3^2\cdot5)

2.Find gcd⁡(84,132)\gcd(84, 132) using the Euclidean algorithm.

3.If gcd⁡(a,b)=6\gcd(a,b)=6 and lcm⁡(a,b)=180\operatorname{lcm}(a,b)=180, find abab.

4.Find the smallest positive integer with exactly 12 positive divisors.

Modular Arithmetic