Unique factorization

In mathematics, the unique factorization theorem, also known as the fundamental theorem of arithmetic states that every integer can be expressed as a product of prime numbers in essentially only one way.

Proof

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_1 = p_2 p_3 \cdots p_m}

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_1 = q_1 q_2 \cdots q_{i-1} q_{i+1} \cdots q_n}

In other words, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_1} is the product of all the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} 's except Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_i} .

Continuing in this way, we obtain a sequence of numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = N_0 > N_1 > N_2 > \cdots > N_n = 1} where each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_{\alpha}} is obtained by dividing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_{\alpha - 1}} by a prime factor. In particular, we see that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = n} and that there is some permutation ("rearrangement") σ of the indices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1, 2, \ldots n} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i = q_{\sigma(i)}} . Said differently, the two factorizations of N must be the same up to a possible rearrangement of terms.