Proof of the fundamental theorem of arithmetic.

Question

Fundamental theorem of arithmetic. Proof:- $P(n)$: $n$ is a prime or can written uniquely as a product of primes. $P(2)$ is true, and assume true for $n=3,4,...,k$. Now if $k+1$ is not a prime it can be written as $k+1= r\times s$ . Now $r<k+1$ and $s<k+1$. Thus both can be written uniquely as product of primes (or prime themselves). Thus $k+1$ can be written uniquely as product of primes. So $P(n)$ is true for all natural numbers.

Where did I go wrong? Can I include 'uniquely' in the statement? Because in every book it is proved first that every composite number is product of primes and then uniqueness is proved.

Answer 1

That $r,\,s$ have unique prime factorisations proves $rs$ has a prime factorisation, but you still need to show it's unique.

The usual proof begins with Bézout's lemma, stating the hcf of two integers is a linear combination of them. Thus if $p|mn$ with $p$ prime and $p\nmid m$ then integers $x,\,y$ exist with $1=px+my$ and $n=pnx+mny$, an obvious multiple of $p$.

Since $p$ divides $m$ or $n$ whenever it divides $n$, if $pM=q_1\cdots q_N$ with $p,\,q_i$ prime then $p$ divides, and hence equals, some $q_i$, say $q_1$ so $M=q_2\cdots q_N$. So if $k+1$ were a natural with multiple prime factorisations, we could cancel one of its prime factors to obtain a smaller such natural.