What Is Prime Factorization?
Prime factorization is the process of breaking a composite number down into a product of prime numbers. A prime number is a number greater than 1 that has no divisors other than 1 and itself (2, 3, 5, 7, 11, 13, 17, 19, 23, …).
By the Fundamental Theorem of Arithmetic, every integer greater than 1 is either itself a prime, or can be represented as a unique product of primes (up to the order of factors).
Example: 360 = 2³ × 3² × 5
Method 1: Trial Division
Start dividing by the smallest prime (2), then 3, then 5, and so on until the quotient becomes 1.
Example: Prime Factorization of 84
- 84 ÷ 2 = 42
- 42 ÷ 2 = 21
- 21 ÷ 3 = 7
- 7 is prime — stop!
Prime factorization of 84 = 2² × 3 × 7
Method 2: Factor Tree
A factor tree is a visual method where you branch a number into two factors, then keep factoring each branch until all branches end in primes.
Example: Factor Tree of 180
180
/ 2 90
/ 2 45
/ 5 9
/ 3 3
Reading the prime leaves: 180 = 2² × 3² × 5
Method 3: The Ladder (Upside-Down Division) Method
Write the number at the top, divide by primes going down, and read the primes from the left side. This is a clean, organized approach popular in schools.
2 | 72 2 | 36 2 | 18 3 | 9 3 | 3 | 1
72 = 2³ × 3²
How to Know When to Stop
You only need to test prime divisors up to the square root of the number. If no prime up to √n divides n, then n itself is prime.
Example: Is 97 prime? √97 ≈ 9.8, so we test primes up to 9: 2, 3, 5, 7. None divide 97, so 97 is prime.
Applications of Prime Factorization
Finding the GCF
GCF = product of the lowest powers of all common prime factors.
GCF(36, 48): 36 = 2² × 3², 48 = 2⁴ × 3 → GCF = 2² × 3 = 12
Finding the LCM
LCM = product of the highest powers of all prime factors that appear.
LCM(36, 48): → LCM = 2⁴ × 3² = 16 × 9 = 144
Simplifying Fractions
Factor numerator and denominator, then cancel common prime factors.
72/90 = (2³ × 3²) / (2 × 3² × 5) = 2² / 5 = 4/5
Cryptography
RSA encryption — the backbone of internet security — relies on the fact that it is computationally easy to multiply two large primes together, but extremely difficult to factor the result back into its primes. Prime factorization is literally what keeps online banking secure.