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$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License