Problem 24 Recitation Proof

24) Complete the proof of the fundamental theorem of arithmetic by proving the uniqueness of the prime factorization up to ordering for positive integers greater than 1.

Pf: Consider $n >1 \in \mathbb{Z}$. We will induct on $n$ to prove that for all $n$, prime factorization is unique. First, consider base case $n=2$. Because 2 is prime, we know that it has exactly two factors, 1 and itself. Thus, the only way to express 2 in the form of the product of primes to positive integer powers is $2^1$. Thus, the base case is proven. Now we may assume that for all $n\leq k$, for some k, prime factorization is unique. We must now simply show that prime factorization is unique for $k+1$. There are two cases. If $k+1$ is prime, prime factorization is clearly unique. If $k+1$ is composite, by definition we may divide it by some prime number to yield another positive integer, $m$, with $m \leq k+1$ and $m > 1$. Since division is well defined, regardless of any chosen factorization of $k+1$, $k+1$ dividing by the same prime always produces the same $m$. And since $m<k$, by inductive hypothesis, $m$ has a unique prime factorization. Thus, $k+1$ has a unique prime factorization. $QED$

page revision: 2, last edited: 23 Apr 2018 22:38