# Prove that square root of 2 is irrational using the principle of Mathematical Induction

How do I prove that the square root of 2 is irrational using the principle of mathematical induction?

-
– Frenzy Li Aug 17 '12 at 13:17

The usual proof starts out something like "suppose for a contradiction $\sqrt 2$ were rational, and write it as $p/q$ in lowest terms ...".

The "in lowest terms" hides an instance of induction, which you can unfold to get a proof in the shape of

Theorem. For all positive integers $p$ and $q$, it holds that $(p/q)^2\ne 2$.

Proof. By long induction on $q$. If $p$ and $q$ have a common factor $n>1$ then $(\frac pq)^2 = (\frac{p/n}{q/n})^2$, and since $q/n<q$, the induction hypothesis guarantees that $(\frac pq)^2\ne 2$. Now we consider the case that $p$ and $q$ are relatively prime ...

-
One can also find induction in the case p,q coprime. Induction is everywhere in proofs about naturals, so it's difficult (if not impossible) to classify proofs by induction or not. These elementary proofs of irrationality all essentially depend on the Division (Euclidean) algorithm, so the descent implied by such may be viewed as the inductive essence of the matter. But, pedagogically, the proofs are better presented with this induction encapsulated in a Lemma (Division algorithm), rather than directly inlining said lemma into proofs, only for the sake of "making the proof look inductive". – Bill Dubuque Aug 17 '12 at 14:27
Is "long induction" another name for strong induction? – user2468 Aug 17 '12 at 14:29
For a nontrivial example of a proof where such descent/induction has been "inlined" into a proof, see Zermelo's classical proof of unique factorization of integers, where he has inlined the classical inductive/descent proof of the prime divisor property $\rm\:p\:|\:ab\:$ $\Rightarrow$ $\rm\:p\:|\:a\:$ or $\rm\:p\:|\:b.\$ – Bill Dubuque Aug 17 '12 at 14:31
@JenniferDylan: Yes, they are synonyms. I learned it as long induction, but there are others who call it strong instead. – Henning Makholm Aug 17 '12 at 15:25