Prime factorization

How the repeated division method works

Divide the number by the smallest prime that divides it evenly (2, then 3, 5, 7, 11…) and repeat the operation on the quotient until you reach 1. The divisors used along the way are the prime factors. Take 360, for example: divide by 2 three times (360 → 180 → 90 → 45), by 3 twice (45 → 15 → 5) and by 5 once, so 360 = 2³ × 3² × 5.

What prime factorization is used for

It is the foundation for finding the GCF and LCM: the greatest common factor comes from multiplying the shared prime factors with the smallest exponent, while the least common multiple takes shared and non-shared factors with the largest exponent. It's also how you reduce fractions to lowest terms and count the divisors of a number (add 1 to each exponent and multiply). Fun fact: the sheer difficulty of factoring enormous numbers is what keeps RSA encryption, used by banks and websites, secure.

Why every number has only one factorisation

It is the fundamental theorem of arithmetic: every whole number greater than 1 can be written as a product of primes in exactly one way, up to order. It is not obvious and has to be proved, but it is why a factorisation works as a number's identity card.

The practical use follows: two numbers are compared by looking at their factors instead of their values. The greatest common divisor takes the shared factors with the smallest exponent, the least common multiple takes all the factors with the largest exponent, and neither operation requires trying divisors one by one.

You stop at the square root

To know whether a number is prime you do not have to try every divisor up to it: reaching its square root is enough. If a number has a divisor larger than the root, it necessarily has a smaller one too, and that is the one you meet first.

It is why checking that 9,973 is prime takes fewer than twenty-five attempts and not ten thousand: you only try the primes up to 99. In factorisation the same principle says when to stop: when the remaining quotient is smaller than the square of the current divisor, that quotient is prime.

The number that is easy to multiply and hard to break

Multiplying two large primes is instant; recovering the two factors from the product is extremely hard, and nobody knows how to do it quickly on numbers of hundreds of digits. RSA cryptography, and therefore much of the security of the internet, rests on that asymmetry.

For small numbers, by contrast, factorisation is immediate and useful every day: simplifying a fraction, finding a common denominator, seeing whether a root can be taken outside. It is the same tool at two completely different scales.

Nearby tools

For the greatest common divisor and least common multiple there is GCD and LCM calculator, and to reduce a fraction Simplify fractions. If the number is large, look at Prime numbers.