I need to prove:
Every integer $n$, $n \ge 2$, can be factored uniquely into primes. (By "unique," we mean unique up to the order in which the primes are listed.)
I assume I need to use induction, but I'm unsure of how to prove the $n+1$ case.
Any assistance would be greatly appreciated!
Assume the statement is false. Because the positive integers are well ordered, there is a smallest $n$ that cannot be uniquely factored into primes. Then $n$ cannot itself be prime or $n=n$ is the unique prime factorization of $n$. Thus, $\exists a, b \lt n$ such that $n=ab$.
But $n$ is the smallest number that cannot be uniquely factored into primes, so $a, b \lt n \Rightarrow a \text{ and } b$ can be factored into primes (and indeed, we can do so uniquely). That demonstrates that $n$ is a product of primes, so $n=pm$ for some prime $p, m =n/p \lt n$. Because $n/p$ can be factored into primes uniquely, it follows that the prime factorization of $n$ is likewise unique, contradicting our original assumption that $n$ cannot be uniquely factored into primes.
