This site is supported by donations to The OEIS Foundation.

# Fundamental theorem of arithmetic

The fundamental theorem of arithmetic shows that the integers form a unique factorization domain.

Theorem. Each positive integer $n\,$ is the product of prime numbers in only one way (up to ordering.)

Since multiplication in $\mathbb {Z} \,$ is commutative, it does not matter in what order we state the prime factors. So, for example, the ordered prime factorizations $2\times 5\times 2\times 3\times 2\,$ and $2^{3}\times 3\times 5\,$ are not different prime factorizations of 120, but merely different ways of expressing the only prime factorization of 120 that exists.

We could alternatively state the theorem as: given the set of positive integers $\mathbb {Z} _{+}\,$ and its subset of prime numbers $\mathbb {P} \,$ , each $n\,\in \,\mathbb {Z} _{+}\,$ has a unique prime factorization as a product of $p_{i}\,\in \,\mathbb {P} \,$ . Or we could simply say that $\mathbb {Z} \,$ is a unique factorization domain.

Or that A000012(n) (the all 1's sequence) counts how many different ways $n\,$ can be expressed as a product of primes.

Proof. For now let's take as axiomatic the fact that each integer has any prime factorization at all. Let's say that $n\,$ actually has two distinct prime factorizations: $n\,=\,\prod _{i=1}^{m}p_{i}\,=\,\prod _{j=1}^{k}q_{j}\,$ where the $p_{i}\,$ and $q_{j}\,$ are primes, and $k\,\geq \,m\,$ . Since $p_{1}\,$ is a divisor of $n\,$ , it must also be a divisor of the product of the primes $q_{j}\,$ . But since the $q_{j}\,$ are primes and $p_{1}\,$ is also prime, this must mean that $p_{1}\,=\,q_{o}\,$ , with $o\,$ being an integer in the range $1\,\leq \,o\,\leq \,k\,$ , and we can therefore remove $p_{1}\,$ from one side of the equation and $q_{o}\,$ from the other. We can continue this process to the point of removing all $p_{i}\,$ until we're left with $1\,=\,\prod _{j=m+1}^{k}q_{j}\,$ , something that is absurd (unless $k\,=\,m\,\,$ , in which case we have the empty product on the right) if all the $q_{j}\,$ are in fact primes. Therefore, $m\,$ must be equal to $k\,$ , and the primes $q_{j}\,$ are the same primes $p_{i}\,$ just perhaps given in a different order.

This theorem is sometimes given as a reason for excluding 1 from the list of primes. Though there are much better reasons to regard 1 as not prime, rigor nevertheless demands that we either handle 1 in some way or amend the theorem to say $n\,>\,1\,$ . The usual handling is to state that 1, as the "empty product," is in fact the product of multiplying zero primes together. Now, 1 is considered a unit, i.e. an invertible (multiplicative inverse) element of the set of positive integers.

As for negative integers, the most straightforward handling is probably to regard all the prime factors as positive and have this prefixed by the unit $(-1)\,$ to accomplish the sign change (this is what Mathematica does). Thus an integer would have its prime factorization prefixed by $(-1)^{0}\,=\,1\,$ or $(-1)^{1}\,=\,-1\,$ . A more complicated but perhaps equally valid way would be to add negative signs to an odd number of the prime factors.

Compare with the frivolous theorem of arithmetic.