1
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ unique factorization is easily researched online (or in your text). $\endgroup$ – lulu Apr 3 at 0:08
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.