Prime Factorization: Every Number's Unique Fingerprint
The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a unique product of prime numbers. This prime factorization is like a fingerprint — no two different numbers share the same one.
Method: Divide by Smallest Prime Repeatedly
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 is prime → stop
360 = 2³ × 3² × 5Common Examples
- 12 = 2² × 3
- 100 = 2² × 5²
- 210 = 2 × 3 × 5 × 7
- 1024 = 2¹⁰
Applications
- GCD: Take lowest power of each shared prime factor
- LCM: Take highest power of every prime factor that appears
- Simplifying fractions: Cancel common prime factors
- Cryptography: RSA encryption relies on the difficulty of factoring very large numbers
Find prime factors: Free Prime Factorization Calculator
Methods for Prime Factorisation
- Trial division: Divide successively by 2, 3, 5, 7, 11... until you reach 1. Example: 360 ÷ 2 = 180, ÷2 = 90, ÷2 = 45, ÷3 = 15, ÷3 = 5, ÷5 = 1. So 360 = 2³ × 3² × 5.
- Factor tree: Draw branches splitting a number into any two factors, continue until all branch ends are prime. Both methods give the same result.
Applications
Prime factorisation is the foundation for finding the Greatest Common Divisor (GCD) and Lowest Common Multiple (LCM). GCD of 24 and 36: 24 = 2³×3, 36 = 2²×3². GCD = 2²×3 = 12 (lowest powers). LCM = 2³×3² = 72 (highest powers). These calculations appear in simplifying fractions, scheduling (when will two repeating events coincide), gear design (tooth count ratios), and music theory (rhythmic patterns). Cryptography — including RSA public-key encryption — relies on the fact that factoring very large numbers (hundreds of digits) is computationally infeasible.
Frequently Asked Questions
Is 1 a prime number?
No. By modern definition, a prime must have exactly two distinct positive divisors: 1 and itself. The number 1 has only one positive divisor (itself), so it is neither prime nor composite. Excluding 1 from primes preserves the Fundamental Theorem of Arithmetic: every integer greater than 1 has a unique prime factorisation.
What are the first 20 prime numbers?
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71. The prime counting function π(100) = 25 — there are 25 primes below 100. Primes become less dense as numbers grow but by the Prime Number Theorem, primes near n occur with density 1/ln(n).
Are there infinitely many primes?
Yes, proven by Euclid around 300 BC. His proof by contradiction: assume a finite list of all primes p₁, p₂, ..., pₙ. Multiply them all together and add 1: N = p₁×p₂×...×pₙ + 1. N is either prime (contradicting the list being complete) or divisible by a prime not on the list (also a contradiction). Therefore the list cannot be finite.