Prime Factorization – Breaking Numbers into Prime Pieces
Prime factorization is the process of writing a number as a product of prime numbers. Because primes cannot be broken down further, this gives us the deepest possible view of a number's structure.
Finding the prime factorization of a small number like 84 takes seconds by hand. But the difficulty grows explosively with size: factoring a 10-digit number by computer is instant, a 100-digit number takes noticeably longer, and a carefully chosen 300-digit number can keep even powerful computers busy for far longer than is practical using known methods. That asymmetry — multiplying primes together is easy, but undoing the multiplication is brutally hard — is the entire foundation of RSA encryption, the system that secures much of your online banking and messaging today.
What Is It?
Prime factorization of N = the unique expression N = p¹ × p² × p³ × ... where every p is a prime number.
Worked Examples
36 ÷ 2 = 18 → 18 ÷ 2 = 9 → 9 ÷ 3 = 3 → 3 is prime.
36 = 2 × 2 × 3 × 3 = 2² × 3²
84 ÷ 2 = 42 → 42 ÷ 2 = 21 → 21 ÷ 3 = 7 → 7 is prime.
84 = 2² × 3 × 7
360 ÷ 2 = 180 → ÷2 = 90 → ÷2 = 45 → 45 ÷ 3 = 15 → 15 ÷ 3 = 5 → 5 prime.
360 = 2³ × 3² × 5
Using Prime Factorization for GCF and LCM
| Goal | Rule | Example (12=2²×3, 18=2×3²) |
|---|---|---|
| GCF | Take lowest power of each shared prime | 2¹ × 3¹ = 6 |
| LCM | Take highest power of every prime | 2² × 3² = 36 |
The Uniqueness Guarantee
The Fundamental Theorem of Arithmetic guarantees that every whole number greater than 1 has exactly one prime factorization (order of primes does not count). This uniqueness makes it a reliable tool.
Key Takeaways
- Divide repeatedly by the smallest prime until 1 is reached.
- Write the result using exponents for repeated primes.
- Every whole number > 1 has a unique prime factorization.
- Use lowest powers for GCF; highest powers for LCM.
Practice: Prime Factorization
Related Topics
Continue exploring related topics: