Unique factorization/Advanced

In mathematics, the unique factorization theorem, also known as the fundamental theorem of arithmetic states that every nonzero integer can be written in a unique way as a product of a unit (i.e., $\pm 1$) and prime numbers. Unique factorization is the foundation for most of the structure of whole numbers as described by elementary number theory. The formulation of many results (for instance, the Chinese remainder theorem) would either be nonsensical, or at least more complicated, if unique factorization did not hold.

Precise formulation

The theorem has two parts: first, that a factorization exsits, and second, that it is unique. This description leads to a couple of troublesome questions. If we allow rearrangement of the factors, as in $6=2\times 3=3\times 2$, the theorem is false. Also, what are the prime factorizations of 1 and -1?

We can give a more precise version as follows. The first part of the theorem states that every nonzero integer n has a prime factorization. We can therefore write

$n=(-1)^{\varepsilon }\prod _{p}p^{e_{p}};$

this being an infinite product over the set of prime numbers. As n can have only finitely many prime factors, all but finitely many of the exponents $e_{p}$ are 0, so the product makes sense. Also, we can restrict $\varepsilon$ to be either 0 or 1 when n is positive or negative respectively, and all of the exponents $e_{p}$ must be nonnegative integers. With these conventions, the fundamental theorem can now be precisely expressed as saying that for any nonzero integer n, a factorization as above exists, and the list of integers $\left(\varepsilon ,e_{2},e_{3},e_{5},\ldots \right)$ is uniquely determined by n.

For a nonnegative integer n and a prime number p, the exponent $e_{p}$ in the factorization is called the order of n at p, written $\mathrm {ord} _{p}(n)$. Consideration of these orders leads directly to the useful theory of valuations.

Proof

The proof of both the existence and uniqueness statements of the fundamental theorem requires the technique mathematical induction.

Every integer $N>1$ can be written in a unique way as a product of prime factors, up to reordering. To see why this is true, assume that $N$ can be written as a product of prime factors in two ways

$N=p_{1}p_{2}\cdots p_{m}=q_{1}q_{2}\cdots q_{n}$

We may now use a technique known as mathematical induction to show that the two prime decompositions are really the same.

Consider the prime factor $p_{1}$. We know that

$p_{1}\mid q_{1}q_{2}\cdots q_{n}.$

Using the second definition of prime numbers, it follows that $p_{1}$ divides one of the q-factors, say $q_{i}$. Using the first definition, $p_{1}$ is in fact equal to $q_{i}$

Now, if we set $N_{1}=N/p_{1}$, we may write

$N_{1}=p_{2}p_{3}\cdots p_{m}$

and

$N_{1}=q_{1}q_{2}\cdots q_{i-1}q_{i+1}\cdots q_{n}$

In other words, $N_{1}$ is the product of all the $q$'s except $q_{i}$.

Continuing in this way, we obtain a sequence of numbers $N=N_{0}>N_{1}>N_{2}>\cdots >N_{n}=1$ where each $N_{\alpha }$ is obtained by dividing $N_{\alpha -1}$ by a prime factor. In particular, we see that $m=n$ and that there is some permutation ("rearrangement") σ of the indices $1,2,\ldots n$ such that $p_{i}=q_{\sigma (i)}$. Said differently, the two factorizations of N must be the same up to a possible rearrangement of terms.