# In $\sqrt 2 =\frac ab$. Why must gdc(a, b) = 1 for $\sqrt 2$ $\in\mathbb{Q}$?

In the proof by contradiction of square root of two being irrational it is implied that if both a and b are even or odd then they cannot be on the lowest terms( $gdc(a, b) = 1$ ). Why must they be on the lowest terms for √2 to be rational?

√2 = a/b
2 = a²/b²
2b² = a² => 2 | a² => 2 | a
4 | a²
4 | 2b²
2 | b² => 2 | b


This proves that both a and b are even and thus have common factor of 2. Why does that contradict that √2 is rational?

One proof Why is it obvious

We additionally assume that this a/b is simplified to lowest terms, since that can obviously be done with any fraction.

Given the answers the question becomes why can we presume in the theorem that gdc(a, b) = 1 ?

• Why must they be on the lowest terms Presumably because that's part of the premise of the proof that you haven't quoted. – dxiv Apr 29 '17 at 7:13
• The question essentially asks why is that the premise. – Olavi Sau Apr 29 '17 at 7:16
• That premise is unrelated to $\sqrt2$ being rational. With any rational we can, without loss of generality, assume that $\gcd(a,b)=1$. – Jyrki Lahtonen Apr 29 '17 at 7:17
• @OlaviSau That's hard to answer in specific detail since you didn't quote the full proof. As a guess, if $\sqrt{2}$ were assumed to be a rational, you would have canceled out any common factors between the numerator and denominator before defining the $a,b$ that the proof starts with. – dxiv Apr 29 '17 at 7:17
• So gdc(a, 1) = 1, right... – Olavi Sau Apr 29 '17 at 7:37

A different way to look at this is: if you think there is a pair of positive integers $a,~ b$ such that $\frac{a}{b} = \sqrt{2}$ then you can generate a new pair of integers, $a',~ b'$ where $a' < a$ and $b' < b$. But then the same argument applies again, giving you a descending chain of $a$ and $b$ values. But there is no infinite descent of positive integers. So we couldn't have had the original pair $a,~ b$ after all, and thus there is no rational number $\sqrt{2}$.

• Why would a and b need to be positive? Two negative numbers divided by each other would be positive. – Olavi Sau Apr 29 '17 at 7:27
• If a negative divided by a negative is positive, then $\frac{a}{b}$ is positive. So... – law-of-fives Apr 29 '17 at 7:33
• "But there is no infinite descent of positive integers." But there is an infinite descent of all integers. If a and b are both negative then you can generate a new pair of descending integers. – Olavi Sau Apr 29 '17 at 7:39
• Descent by subtraction, yes, but if you look at your proof, you are dividing by 2. You cannot repeatedly divide any integer by 2 and always get another integer. Even if it were a power of 2, eventually you would get one and could not proceed further. If you are concerned about negative numbers then you can simply change the relation in my comment to be $|a'| < |a|$. That is, smaller in magnitude. The signs of $a,~ b$ are not important. – law-of-fives Apr 29 '17 at 7:43

Because in the statement of the theorem, it is required that $gcd(a,b)=1$.

You have found a contradiction to this, that $gcd(a,b)=2$.

Hence $\sqrt 2$ is irrational, as you assumed it to be rational.

• In order for the question to be complete please give an quote or link of what gcd(a, b) = 1 is. – Olavi Sau Apr 29 '17 at 7:24
• In the theorem that you haven't , but should have stated. The relevant theorem goes something like: Let a,b integers, with gcd(a,b)=1 and b not zero. Then $\sqrt 2$ can not be written as $a/b$. Hence $\sqrt 2$ is irrational. – Charlie Apr 29 '17 at 7:24
• Greatest common divisor. $$\gcd(a,b)=1\implies \text{relatively prime}$$ – projectilemotion Apr 29 '17 at 7:25
• $gcd(a,b)$ is the greatest common divisor of the integers a and b. Meaning that $gcd(a,b)$ (which itself is a natural number) is the largest number, $g$ say, such that $g|a$ and $g|b$. – Charlie Apr 29 '17 at 7:25
• Okay okay I understand now, so the question really is why must the gcd be 0? ( I sorta got the answer how to ask my question though, I will have to google that first.) – Olavi Sau Apr 29 '17 at 7:29