Prime Factorization: The Complete Guide
What Is Prime Factorization?
Prime factorization is the process of expressing a positive integer as a product of prime numbers. For example, 360 = 2³ × 3² × 5. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has a unique prime factorization (up to the order of factors). This makes prime factorization a cornerstone of number theory and the foundation for many algorithms in mathematics and computer science.
Example: 360 = 2³ × 3² × 5¹
Example: 84 = 2² × 3 × 7
Example: 1001 = 7 × 11 × 13
How to Find Prime Factors
The standard method is trial division: divide the number by the smallest prime (2), repeatedly, until it no longer divides evenly. Then try 3, 5, 7, 11, and so on. You only need to test primes up to √n, because if n has a factor larger than √n, the corresponding cofactor must be smaller than √n. For example, to factorize 252: 252 ÷ 2 = 126, 126 ÷ 2 = 63, 63 ÷ 3 = 21, 21 ÷ 3 = 7, and 7 is prime. So 252 = 2² × 3² × 7.
Result: 1260 = 2² × 3² × 5 × 7. It has (2+1)(2+1)(1+1)(1+1) = 36 divisors.
Number of Divisors and Sum of Divisors
If n = p₁ᵃ¹ × p₂ᵃ² × ... × pₖᵃᵏ, the number of divisors (tau function) is τ(n) = (a₁+1)(a₂+1)...(aₖ+1). The sum of divisors (sigma function) is σ(n) = Π((pᵢᵃⁱ⁺¹ − 1)/(pᵢ − 1)). A number is perfect if σ(n) = 2n (like 6 and 28), abundant if σ(n) > 2n, and deficient if σ(n) < 2n. These functions are fundamental in number theory and have connections to the Riemann zeta function.
GCD and LCM via Prime Factorization
The Greatest Common Divisor (GCD) of two numbers uses the minimum exponents of their shared prime factors. The Least Common Multiple (LCM) uses the maximum exponents of all prime factors. For example, 360 = 2³ × 3² × 5 and 252 = 2² × 3² × 7. GCD = 2² × 3² = 36. LCM = 2³ × 3² × 5 × 7 = 2520. A key identity: GCD(a,b) × LCM(a,b) = a × b.
LCM(a,b) = Π pᵢ^max(aᵢ,bᵢ)
GCD(a,b) × LCM(a,b) = a × b
Euler's Totient: φ(n) = n × Π(1 − 1/pᵢ)
Euler's Totient Function
Euler's totient function φ(n) counts integers from 1 to n that are coprime to n (share no common factor other than 1). Using prime factorization: φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × ... × (1 − 1/pₖ). For example, φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4, and indeed {1, 5, 7, 11} are coprime to 12. The totient function is central to RSA encryption and modular arithmetic.
Prime Numbers and Primality
A prime number has exactly two distinct positive divisors: 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47... There are infinitely many primes (proved by Euclid around 300 BCE). The number 1 is neither prime nor composite by convention. The number 2 is the only even prime. The Prime Number Theorem states that the number of primes up to n is approximately n/ln(n). The largest known prime (as of 2024) is a Mersenne prime with over 41 million digits.
Divisibility Rules
Quick divisibility tests: a number is divisible by 2 if its last digit is even; by 3 if its digit sum is divisible by 3; by 4 if its last two digits form a number divisible by 4; by 5 if it ends in 0 or 5; by 6 if divisible by both 2 and 3; by 8 if its last three digits are divisible by 8; by 9 if its digit sum is divisible by 9; by 11 if the alternating sum of digits is divisible by 11. These rules are shortcuts derived from modular arithmetic.
Applications of Prime Factorization
Prime factorization has profound applications in cryptography — RSA encryption relies on the difficulty of factoring large semiprimes (products of two large primes). In computer science, hash table sizes are often chosen as primes to minimize collisions. In music theory, frequency ratios between notes involve small primes (octave = 2:1, perfect fifth = 3:2). In physics, group theory uses prime decomposition to classify symmetries. The factorization of polynomials mirrors integer factorization, connecting algebra to number theory.
Historical Development
The study of prime numbers dates to ancient Greece. Euclid (c. 300 BCE) proved there are infinitely many primes and described a method for finding GCD (the Euclidean algorithm). The Sieve of Eratosthenes (c. 240 BCE) efficiently identifies all primes up to a given limit. Fermat (1640) discovered his Little Theorem (aᵖ⁻¹ ≡ 1 mod p for prime p). Euler extended this with his totient function. Gauss and Legendre conjectured the Prime Number Theorem, proved in 1896 by Hadamard and de la Vallée-Poussin. Modern computational number theory can factor numbers with hundreds of digits using sophisticated algorithms like the General Number Field Sieve.
How to Use This Calculator
Enter any positive integer (2 or larger) and click "Factorize." The calculator displays the complete prime factorization with exponent notation, an animated factor tree visualization, all divisors with factor pairs, divisibility test results for common primes, the number of divisors, sum of divisors, and Euler's totient. For GCD/LCM mode, enter two numbers to see their shared and combined factorizations.