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.

  • $\begingroup$ Your proof seems correct to me. You should define $r$ and $s$ upon using those variables. $\endgroup$
    – Tim Thayer
    Commented Feb 12, 2017 at 20:27
  • $\begingroup$ @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? $\endgroup$
    – user398623
    Commented Feb 12, 2017 at 20:32
  • 1
    $\begingroup$ @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. $\endgroup$
    – kingW3
    Commented Feb 12, 2017 at 20:40
  • $\begingroup$ @kingW3 Yes, I get you. $\endgroup$
    – user398623
    Commented Feb 12, 2017 at 21:15
  • $\begingroup$ That inductive proof shows only existence of prime factorizations, not uniqueness. $\endgroup$ Commented Feb 12, 2017 at 21:45

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .