| | |
$\require{AMSsymbols}$Before diving into the Fundamental Theorem of Arithmetic, we need to first dispatch with an old claim. Namely, that if $p$ is prime and $p \mid ab$, then either $p \mid a$ or $p \mid b$.
Proof: Consider what values $\textrm{gcd}(a,p)$ can have. Since $p$ is prime, either $\textrm{gcd}(a,p)=1$ or $\textrm{gcd}(a,p)=p$. In the latter case, $p \mid a$ and we are done. So, let us focus on the case where $p$ and $a$ are relatively prime. When $\textrm{gcd}(a,p)=1$, we know that we can find integers $x$ and $y$ that satisfy $$px+ay=1$$ Now, multiply both sides of the equation by $b$ to give $$pbx+aby=b$$ Certainly, $p \mid pbx$. We also know that $p \mid aby$ (since we know $p \mid ab$). It follows that $p$ divides the sum of these two terms. $$p \mid pbx + aby$$ But this sum is $b$, so $p \mid b$, which completes the proof.
We can generalize the above claim in the following way:
The Prime Divisibility Property Let p be a prime number, and suppose that $p \mid a_1 a_2 \cdots a_r$. Then p divides at least one of the factors $a_1, a_2, ... a_r$.
Proof: If $p \mid a_1$ we are done. If not, we apply the claim argued above to the product $$a_1(a_2 a_3 \cdots a_r)$$ to conclude that $p \mid a_2 a_3 \cdots a_r$. In other words, we are applying the claim with $a=a_1$ and $b=a_2 a_3 \cdots a_r$. We know that $p \mid ab$, so if $p \nmid a$, the claim requires that $p \mid b$. So now we know that $p \mid a_2 a_3 \cdots a_r$. If $p \mid a_2$ we are done. If not, we apply the claim to the product $a_2 (a_3 \cdots a_r)$ to conclude that $p \mid a_3 \cdots a_r$. Continuing in this fashion, we must eventually find some $a_i$ that is divisible by $p$.
Now, we have the machinery we need to tackle...
The Fundamental Theorem of Arithmetic Every integer $n \ge 2$ can be factored into a product of primes in exactly one way (aside from rearranging the factors).
Proof: We can prove the first part of this theorem (that every integer $n \ge 2$ can be factored into a product of primes) with strong induction. We'll save proving the uniqueness of the factorization for later...
Basis Step: Observe that $2=2$, $3=3$, $4=2 \cdot 2$, and so on... Clearly, the first several numbers can be factored into a product of primes.
Inductive Step: Suppose that we know every number $n \le k$ can be factored into a product of primes. Let us consider $n=k+1$.
There are two possibilities. Either $k+1$ is prime (in which case we are done) or $k+1$ is composite. Recall that a number greater than 2 is composite (i.e., not prime) if and only if it has factors other than itself or 1. Consequently, we can find integers $n_1$ and $n_2$ where $$k+1 = n_1 n_2 \quad \quad \textrm{where} \quad \quad 2 \le n_1 , n_2 \le k$$ But both $n_1$ and $n_2$, being less than or equal to $k$ and greater than or equal to $2$ have prime factorizations by the inductive hypothesis! Suppose these prime factorizations are $$n_1 = p_1 p_2 \cdots p_r \quad \quad \textrm{and} \quad \quad n_2 = q_1 q_2 \cdots q_s$$ But then, multiplying these two products together gives $$k+1 = n_1 n_2 = p_1 p_2 \cdots p_r q_1 q_2 \cdots q_s$$ So $k+1$ can be factored into a product of primes, which is what we sought to show.
With the principle of strong mathematical induction, we can then conclude that every integer $n \ge 2$ can be factored into a product of primes.
Now, to prove the uniqueness of this factorization, we appeal to an indirect argument. Suppose the factorization is not unique - that instead, $$n = p_1 p_2 p_3 p_4 \cdots p_r = q_1 q_2 q_3 q_4 \cdots q_s$$ where the factorization on the right is not just a rearrangement of the factorization on the left. Note $p_1 \mid n$, so by the Prime Divisibility Property, $p_1$ must divide some $q_i$. Without loss of generality, suppose that $i=1$ (note, we can rearrange the $q$'s if necessary). But we have $p_1 \mid q_1$ where $q_1$ is prime. Prime numbers are only divisible by themselves and 1, and seeing as how $p_1 \neq 1$ since it too is prime, it must be the case that $p_1 = q_1$.
So we may cancel the $p_1$ (which is the same as $q_1$) from both sides to arrive at $$ p_2 p_3 p_4 \cdots p_r = q_2 q_3 q_4 \cdots q_s$$ Repeating the same argument, we note that $p_2$ divides the left side, so $p_2$ divides the right side as well. Again, by the Prime Divisibility Property, $p_2$ divides some $q_j$, which we may call $q_2$ (after rearranging the factors, if needed). Thus $p_2 \mid q_2$, and given that they are both prime, we have $p_2 = q_2$. Canceling the $p_2$ (which equals $q_2$) from both sides, we have $$ p_3 p_4 \cdots p_r = q_3 q_4 \cdots q_s$$ We continue in this fashion until either all of the $p_i$'s or all of the $q_i$'s are gone. But if all of the $p_i$'s are gone, then the left side of the equation equals 1, and so the $q_i$'s must have been exhausted as well. This argument works just as easily if all of the $q_i$'s disappeared first. Being able to match up each $p_i$ with some equal $q_i$ implies that the $q_i$'s are just a rearrangement of the $p_i$'s, which contradicts our assumption. Hence, the prime factorization for any $n \ge 2$ is unique.
QED.