# Understanding the proof of the existence of Fundamental Theorem of Arithmetic as explained on wikipedea.

I'm reading this wikipedea article:

We need to show that every integer greater than $1$ is a product of primes. By induction: assume it is true for all numbers between $1$ and $n$. If $n$ is prime, there is nothing more to prove (a prime is a trivial product of primes, a "product" with only one factor). Otherwise, there are integers $a$ and $b$, where $n = ab$ and $1 < a ≤ b < n$. By the induction hypothesis, $a = p_1p_2...p_j$ and $b = q_1q_2...q_k$ are products of primes. But then $n = ab = p_1p_2...p_ jq_1q_2...q_k$ is a product of primes.

They said, "If n is prime, there is nothing more to prove...". Haven't we have to show that $P(n) \implies P(n+1)$? Even in the second case where $n$ is not supposed to be prime they do not show that FTA exists for the $n+1$th number. Why is that?

My understanding:

There are two cases, either $n+1$ is prime or it is not. If it is prime then it's fine. If it is not prime then then we must have $n+1=a_1a_2....a_p$ s.t. $a_i<n$ but every number less than $n$ can be factorized in primes so $n+1$ can also be.

• That proof proceeds by strong induction. – Zircht Nov 30 '14 at 4:21
• To add to Zircht's comment. This means we assume it is true for all $k<n$ and prove that it is true for $n$. See here. – Eoin Nov 30 '14 at 4:22
• Oh, I wasn't aware of this kind of Induction. – user103816 Nov 30 '14 at 4:28
• When it says "assume it is true for all numbers between $1$ and $n$", it means strictly between $1$ and $n$. – Gerry Myerson Nov 30 '14 at 4:52
• You can use "usual induction" to prove that "strong induction" is a valid method of argument. They are logically equivalent, but sometimes strong induction is a more convenient way to do things. – Gerry Myerson Nov 30 '14 at 22:33