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 ${\displaystyle \scriptstyle n\,}$ is the product of prime numbers in only one way (up to ordering.)

Since multiplication in ${\displaystyle \scriptstyle \mathbb {Z} \,}$ is commutative, it does not matter in what order we state the prime factors. So, for example, the ordered prime factorizations ${\displaystyle \scriptstyle 2\times 5\times 2\times 3\times 2\,}$ and ${\displaystyle \scriptstyle 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 ${\displaystyle \scriptstyle \mathbb {Z} _{+}\,}$ and its subset of prime numbers ${\displaystyle \scriptstyle \mathbb {P} \,}$, each ${\displaystyle \scriptstyle n\,\in \,\mathbb {Z} _{+}\,}$ has a unique prime factorization as a product of ${\displaystyle \scriptstyle p_{i}\,\in \,\mathbb {P} \,}$. Or we could simply say that ${\displaystyle \scriptstyle \mathbb {Z} \,}$ is a unique factorization domain.

Or that A000012(n) (the all 1's sequence) counts how many different ways ${\displaystyle \scriptstyle 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.[1] Let's say that ${\displaystyle \scriptstyle n\,}$ actually has two distinct prime factorizations: ${\displaystyle \scriptstyle n\,=\,\prod _{i=1}^{m}p_{i}\,=\,\prod _{j=1}^{k}q_{j}\,}$ where the ${\displaystyle \scriptstyle p_{i}\,}$ and ${\displaystyle \scriptstyle q_{j}\,}$ are primes, and ${\displaystyle \scriptstyle k\,\geq \,m\,}$. Since ${\displaystyle \scriptstyle p_{1}\,}$ is a divisor of ${\displaystyle \scriptstyle n\,}$, it must also be a divisor of the product of the primes ${\displaystyle \scriptstyle q_{j}\,}$. But since the ${\displaystyle \scriptstyle q_{j}\,}$ are primes and ${\displaystyle \scriptstyle p_{1}\,}$ is also prime, this must mean that ${\displaystyle \scriptstyle p_{1}\,=\,q_{o}\,}$, with ${\displaystyle \scriptstyle o\,}$ being an integer in the range ${\displaystyle \scriptstyle 1\,\leq \,o\,\leq \,k\,}$, and we can therefore remove ${\displaystyle \scriptstyle p_{1}\,}$ from one side of the equation and ${\displaystyle \scriptstyle q_{o}\,}$ from the other. We can continue this process to the point of removing all ${\displaystyle \scriptstyle p_{i}\,}$ until we're left with ${\displaystyle \scriptstyle 1\,=\,\prod _{j=m+1}^{k}q_{j}\,}$, something that is absurd (unless ${\displaystyle \scriptstyle k\,=\,m\,\,}$, in which case we have the empty product on the right) if all the ${\displaystyle \scriptstyle q_{j}\,}$ are in fact primes. Therefore, ${\displaystyle \scriptstyle m\,}$ must be equal to ${\displaystyle \scriptstyle k\,}$, and the primes ${\displaystyle \scriptstyle q_{j}\,}$ are the same primes ${\displaystyle \scriptstyle p_{i}\,}$ just perhaps given in a different order.[2]

This theorem is sometimes given as a reason for excluding 1 from the list of primes.[3] 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 ${\displaystyle \scriptstyle 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 ${\displaystyle \scriptstyle (-1)\,}$ to accomplish the sign change (this is what Mathematica does). Thus an integer would have its prime factorization prefixed by ${\displaystyle \scriptstyle (-1)^{0}\,=\,1\,}$ or ${\displaystyle \scriptstyle (-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.

## Notes

1. Most books either have this as a previous theorem or at least as a lemma.
2. B. Fine & G. Rosenberger, Number Theory: An Introduction via the Distribution of the Primes Boston: Birkhaüser (2007) p. 18. The fact that an integer has any factorization at all is given as an earlier lemma. The proof is not unique to this text, but it seems to me to provide the clearest explanation of the proof.
3. Primefan, Arguments for and against the primality of 1, "The Prosecution" Arguments 1 and 2. Graeme McRae is credited with the counter-arguments that the theorem accepts the commutative property of multiplication, so why can't it accept the multiplicative identity, or understand the exponents as being the lowest necessary?