# Incorrect logic in popular proof of the irrationality of $\sqrt2$?

A popular proof of the irrationality of $\sqrt2$ is to first assume that the number is rational. This means that $\sqrt2=a/b$ where $a$ and $b$ are integers. Another assumption is that $a$ and $b$ are coprime. It turns out that this leads to a contradiction. And the conclusion is that $\sqrt2$ is not rational (because the assumption of rationality led to a contradiction). But what about the second assumption? Logically, the conclusion could also be that $a$ and $b$ are not coprime..

How can this be resolved?

Edit:

Three aspects of this kind of proof are: mathematical, logical, and didactical.

Mathematically, it is the case that any rational number can be written as a fraction with coprime numerator and denominator. But this point is often described in a way that is either literally a logical assumption, or in a way that is natural to interpret as a hidden logical assumption. In this case, the proof will have a flawed logic, because any of the two assumptions could be the cause of the contradiction. Didactically, this can cause confusion in the mind of the student, who might not be so accepting of the proofs conclusion. I used to be that student.

So, how to resolve it? Many of you provided explanations on the mathematical aspect, which are all correct. But my main point is not of not understanding the proof, but of the use of flawed logic which leads to not understanding the proof. I am sure that a lot of teachers think or say something along the lines of WLOG, but for many students, this makes the proof weaker, because it is not so convincing. When we present this proof to our students, we need to have this in mind.

Thank you.

• You can write every rational in reduced form. Saying $a,b$ are coprime is just choosing the reduced form of $\frac{a}{b}$. Suppose $\sqrt{2} = \frac{p}{q}$, let $\frac{a}{b}$ the reduced form of $\frac{p}{q}$ ... – Daniel Fischer Mar 19 '14 at 22:00
• If you have a fraction $a/b$ where $\gcd(a,b)=d$ then rewrite $a=da'$ and $b=db'$. So $a/b = da'/db' = a'/b'$. Long way of saying what Daniel Fischer beat me to while I was typing. :) – John Habert Mar 19 '14 at 22:00
• if you are familiar with abstract algebra google "field of fractions": in reality $\frac{ka}{kb}$ are just elements of the same equivalence class that we call fraction and denote by $\frac{a}{b}$ – Jack Mar 19 '14 at 22:12

You don't need to assume that $a$ and $b$ are coprime.

If $\sqrt 2= a/b$ with $a,b\in \mathbb Z$, then $2b^2=a^2$. Now count the number of factors of $2$ on each side: on the left, you get an odd number of factors of $2$, while on the right you get an even number of factors.

• Of course unique factorization is a more advanced topic than the usual proof of irrationality of $\sqrt{2}$. That just used arguments about even/odd. – GEdgar Sep 12 '16 at 17:39

That $a$ and $b$ are coprime is not an assumption, it is simply the fact that any rational number can be written in a way so that the numerator and denominator are coprime. The only assumption being made is that $\sqrt 2$ is rational.

• To be honest most people write it as an assumption. "WLOG suppose $\gcd(a,b)=1\ldots$" – Git Gud Mar 19 '14 at 22:03
• "WLOG" is not an assumption. It means "every case is equivalent to the case where" – Stella Biderman Mar 19 '14 at 22:41

If you like, you an proceed as follows: suppose that $\sqrt{2}$ is rational. Then it may be expressed in the form $\sqrt{2} = \frac{a}{b}$ for positive integers $a$ and $b.$ Choose such a representation with $a$ as small as possible: then $a$ and $b$ can have no common factor greater than $1$, for if $a = ec$ and $b = ed$ for positive integers $c,d,e$ with $e > 1,$ then $\sqrt{2} = \frac{c}{d},$ which is a contradiction since $0 < c < a$.

Recall that if $a=km$ and $b=kn$ then we have $$\frac ab=\frac{kn}{km}=\frac nm.$$

Setting $k=\gcd(a,b)$ ensures that $n$ and $m$ are coprime, and we can take them as our fraction to begin with. So the derived contradiction does not contradict this assumption, but rather that such $a$ and $b$ cannot exist.

I think that the problem here is not incorrect logic, but rather a hidden assumption which is everywhere tacitly. This is what is often known as the Well-Ordering Principle/Property.

Every nonempty set of positive integers has a least element.

This property isn't true of many sets - e.g., all integers, positive reals, etc. (using the usual ordering and other axioms, of course).

So when @Geoff says, in an earlier post,

Choose such a representation with a as small as possible: then a and b can have no common factor greater than 1

this is implicitly using this (and possibly also absolute value).

To your main point; naturally, you can also conclude $a$ and $b$ are not coprime! You could conclude one of them is not an integer (which is not quite the same as concluding $\sqrt{2}$ is irrational, just that this representation isn't the rational rep). I suppose you could conclude that $\sqrt{2}$ doesn't exist.

However, let's see what then happens. If I assume $a$ and $b$ are not coprime, then by all the other posts they must share a factor, and so we can reduce it - and then start the proof over. Normally one might think one could keep doing this forever, but by whichever version of Fundamental Theorem of Arithmetic or other tools you like (all of which depend on the Well-Ordering Principle to avoid infinite regress) you will keep getting smaller factors and eventually hit the "smallest" ones. @lhf's very elegant answer from a few minutes ago can be thought of in this way.

Now, you COULD conclude that the WOP is not correct. But now you are starting to suggest that the logical conclusion is that the integers don't have the properties we associate with the integers - in which case proving $\sqrt{2}$ is irrational is probably not particularly interesting.

Well imagine a fraction that can be expressed in the form $\dfrac a b$ where $a$ and $b$ are not coprime, but cannot be expressed in such a form where $a$ and $b$ are coprime. That means you can keep cancelling common factors, but you will never finish. That is clearly nonsensical, but also makes sense because as you better approximate $\sqrt 2$ the numerator and denominator will get larger and larger.

I think we can consider Gauss Lemma here. If $n$ is prime, then $\sqrt n$ is a root of $f(x)=x^2−n$ Now, according to Gauss Lemma $f(x)=x^2−n$ has no rational roots, therefore $\sqrt n$ is irrational.