# Fundamental theorem of arithmetic

In mathematics, and in particular number theory, the **fundamental theorem of arithmetic** is the statement that every positive integer can be written as a product of prime numbers in a unique way. For instance, we can write

- 6936 = 2
^{3}· 3 · 17^{2}or 1200 = 2^{4}· 3 · 5^{2}

To make the theorem work even for the number 1, we think of 1 as being the product of zero prime numbers (see empty product).

## Applications

with [0 ≤*a*≤ 3], [0 ≤

*b*≤ 1], and [0 ≤

*c*≤ 2]. This yields a total of 4 · 2 · 3 = 24 positive factors.

Once the prime factorizations of two numbers are known, their greatest common divisor and least common multiple can be found quickly. For instance, from the above we see that the greatest common divisor of 6936 and 1200 is 2^{3} · 3 = 24. However if the prime factorizations are not known, the use of Euclid's algorithm generally requires much less calculation than factoring the two numbers.

The fundamental theorem ensures that additive and multiplicative arithmetic functions are completely determined by their values on the powers of prime numbers.

## Proof

The uniqueness part of the proof hinges on the following fact: if a prime number *p* divides a product *ab*, then it divides *a* or it divides *b* (Proof: if *p* doesn't divide *a*, then *p* and *a* are relatively prime and Bézout's identity yields integers *x* and *y* such that *px* + *ay* = 1. Multiplying with *b* yields *pbx* + *aby* = *b*. Both summands of the left-hand side are divisible by *p*, so the right-hand side is also divisible by *p*.) Now take two products of primes which are equal. Take any prime *p* from the first product. It divides the first product, and hence also the second. By the above fact, *p* must then divide at least one factor in the second product. But the factors are all primes themselves, so *p* must actually be equal to one of the factors of the second product. So we can cancel *p* from both products. Continuing in this fashion, we eventually see that the prime factors of the two products must match up precisely.

Another proof of the uniqueness of the prime factorization of a given integer uses infinite descent: Assume that a certain integer *can* be written as (at least) two different products of prime numbers, then there must exist a smallest integer *s* with such a property. Call the two products of *s* *p _{1}*...*p_{m}* and

*q*. No

_{1}*...*q_{n}*p*(with

_{i}*1≤i≤m*) can be equal to any

*q*(with

_{j}*1≤j≤n*), as there would otherwise be a smaller integer factorizable in two ways (by removing prime factors common in both products) violating our assumption. We can now assume without loss of generality that

*p*is a prime factor smaller than any

_{1}*q*(with

_{j}*1≤j≤n*). Take

*q*. Then there exist integers

_{1}*d*and

*r*such that

*q*and

_{1}/p_{1}= d+r/p_{1}*0*1 (

1

*r*can't be 0, as that would make

*q*a multiple of

_{1}*p*and not prime). We now get

_{1}*p*. The second term in the last expression must be equal to an integer we call

_{2}*...*p_{m}= (d+r/p_{1})*q_{2}*...*q_{n}= d*q_{2}*...*q_{n}+r*q_{2}*...*q_{n}/p_{1}*k*, i.e.

*k=r*q*. This gives us

_{2}*...*q_{n}/p_{1}*p*. The value of both sides of this equation is obviously smaller than

_{1}*k=r*q_{2}*...*q_{n}*s*, but is still large enough to be factorizable. Since

*r*is smaller than

*p*, the two prime factorizations we get on each side after both

_{1}*k*and

*r*are written out as their product of primes, must be different. This is in contradiction with

*s*being the smallest integer factorizable in more than one way. Thus the original assumption must be false.

See also: Prime factorization algorithm