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 Feb 12 '17 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 Feb 12 '17 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 Feb 12 '17 at 20:40
  • $\begingroup$ @kingW3 Yes, I get you. $\endgroup$ – user398623 Feb 12 '17 at 21:15
  • $\begingroup$ That inductive proof shows only existence of prime factorizations, not uniqueness. $\endgroup$ – Bill Dubuque Feb 12 '17 at 21:45

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.


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.