Understanding Prime Factorization
What Is Prime Factorization?
Prime factorization expresses a number as a product of prime numbers. By the Fundamental Theorem of Arithmetic, every integer greater than 1 has a unique prime factorization (up to ordering).
How It Works
Start dividing by the smallest prime (2) and continue until the quotient is 1. For example: 360 = 2³ × 3² × 5¹. The algorithm tries each prime in ascending order and counts how many times it divides.
The Fundamental Theorem
Every integer n > 1 can be uniquely expressed as n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ where each pᵢ is prime and each aᵢ ≥ 1. This uniqueness is why prime numbers are the 'building blocks' of all integers.
Why It Matters
Prime factorization is central to number theory and cryptography. RSA encryption relies on the difficulty of factoring large numbers. It's also used to find GCD, LCM, and simplify fractions.
Applications
Cryptography (RSA, Diffie-Hellman), simplifying fractions, finding GCD and LCM, determining if a number is prime, and solving Diophantine equations.