Let $n$ and $d$ be integers such that $d$ is a divisor of $n$ if $n=ad$ for some integer $a$. A prime number is a integer $n>1$ that is divisible by 1 and itself. Prove by induction that every integer $n>1$ is either a prime or product of primes.

My attempt:

Proving equation is true for a particular $n$

If $n=2$ then $n=2=2\cdot 1=1\cdot 2=ad$ , $d$=1,2 then $n$ its a prime since a prime is greater than 1.

If $n=4$ them $n=4=2\cdot 2\cdot 1=1\cdot 2\cdot 2=ad$ , $d$=1,2 then its a product of primes namely $n=2\cdot 2$.

is this ok ?

now assuming $n$ is true lets prove $n+1$



If its prime then...

If it is a product of primes then...

I don't know how to continue

I have seen this however i don't know if it is a good answer however I find it incomplete

  • $\begingroup$ Try to complete the answer you have cited here. $\endgroup$ – Dietrich Burde May 14 '15 at 18:35
  • $\begingroup$ see here en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic $\endgroup$ – Dr. Sonnhard Graubner May 14 '15 at 18:36
  • $\begingroup$ This sentence "if $n=2$ then $n=2=2\cdot 1=1\cdot 2=ad$ , $d$=1,2 them $n$ its a prime since a prime is greatter than 1" is very bad English. First off, I noticed you wrote "them" every time you meant "then" (I fixed most of them). You should take your time and formulate your sentences carefully. $\endgroup$ – Gregory Grant May 14 '15 at 18:38
  • $\begingroup$ yes , i have make some mistakes $\endgroup$ – user238670 May 14 '15 at 18:41
  • $\begingroup$ how i complete the answer by editing the answer there? @DietrichBurde $\endgroup$ – user238670 May 14 '15 at 18:42

You will need strong induction, so you assume it holds for all $n < N$.

Then you prove it for $n=N$.

For $n=2$ it clearly holds.

Now assume it holds for all $n < N$.

If $N$ is a prime, then the statement is true.

Else, you can write $N = a\cdot b$ with $a,b < N$, and by the strong induction hypothesis you can write $a,b$ as a prime or a product of primes, so $N$ is a product of primes.

  • $\begingroup$ is in my attempt the prove that n=2 holds ok? $\endgroup$ – user238670 May 14 '15 at 18:48
  • $\begingroup$ No, not really, you can just say that n=2 is prime and be done with it. $\endgroup$ – wythagoras May 14 '15 at 18:49
  • $\begingroup$ strong induction is when using inequalities? $\endgroup$ – user238670 May 14 '15 at 18:52
  • $\begingroup$ I don't really understand the question, but strong induction is used when you not only assume the previous value, but all previous values. $\endgroup$ – wythagoras May 14 '15 at 18:58
  • $\begingroup$ ok now i understand what you mean by strong induction, thanks $\endgroup$ – user238670 May 14 '15 at 18:59

Your Answer

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