# Proof of the fundamental theorem of arithmetic.

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.

• Your proof seems correct to me. You should define $r$ and $s$ upon using those variables. Commented Feb 12, 2017 at 20:27
• @kingW3 I know the proof. And that is why I am asking. In the first step when we write the statement why can't we include the uniqueness part in the statement? Commented Feb 12, 2017 at 20:32
• @user398623 I retract my comment,though since both $r,s\leq k$ they can be written as a product of unique primes,now what's left is to conclude that a product of two such numbers must itself be unique. Commented Feb 12, 2017 at 20:40
• @kingW3 Yes, I get you. Commented Feb 12, 2017 at 21:15
• That inductive proof shows only existence of prime factorizations, not uniqueness. Commented Feb 12, 2017 at 21:45

## 1 Answer

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.