Prime factorization

Every integer greater than 1 can be written as a product of prime numbers in exactly one way, apart from the order of the factors. This is the Fundamental Theorem of Arithmetic. Prime factorization is the basis for finding greatest common divisors, least common multiples, simplifying fractions and understanding why RSA encryption works.

How to use it

1. Enter a positive integer.
2. Read its prime factors, written with exponents.

Worked examples

• 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5
• 1001 = 7 × 11 × 13
• 97 = 97 (a prime number)
• 1024 = 2¹⁰

How it is calculated

The simplest method is trial division: divide by 2 as long as possible, then by 3, 5, 7 and so on. You only need to test divisors up to the square root of the remaining number; if nothing divides it by then, what remains is prime. For 360: 360 / 2 = 180, / 2 = 90, / 2 = 45, / 3 = 15, / 3 = 5, and 5 is prime.

Useful applications

• Number of divisors: add 1 to each exponent and multiply. 360 = 2³ × 3² × 5¹ has (3+1)(2+1)(1+1) = 24 divisors.
• GCD: take the lowest power of each shared prime. GCD(360, 84) with 84 = 2² × 3 × 7 is 2² × 3 = 12.
• LCM: take the highest power of every prime: 2³ × 3² × 5 × 7 = 2520.

Why big numbers are hard

Multiplying two large primes is easy, but factoring their product is extremely hard. RSA encryption relies on this: factoring a 2048-bit RSA modulus is far beyond today's computers.