# About the proof of square root of 2 is irrational [duplicate]

I looked at the proof of $\sqrt 2$ is irrational. In first step we assume that $\sqrt 2$ is rational. Then we say it should be written as $\frac ab$ if it's rational.After that we assume gcd(a,b)=1 and end of the calculations we conclude that a and b are even numbers.So there is a common factor but we assumed that gcd(a,b)=1 so it's a contradiction , $\sqrt 2$ must be irrational.The thing that I don't understand why we assume that gcd(a,b)=1 ? We assume that $\sqrt 2$ is rational it's okay but why we need to assume gcd(a,b)=1.I don't think it's the need of being rational ?

## marked as duplicate by Hans Lundmark, Community♦Oct 8 '17 at 15:30

• The point is we can assume without loss of generality that $\operatorname{gcd}(a, b)=1$: Every rational number can be written as a fraction $\frac{a}{b}$ with $a, b$ relatively prime. – Dustan Levenstein Oct 8 '17 at 15:24
• It's not. But if $\gcd(a,b) = d > 1$, say $a = ud$ and $b = vd$, then without loss of generality, we can replace $\frac{a}{b}$ with $\frac{u}{v}$. – David Wheeler Oct 8 '17 at 15:24
• If $\sqrt 2=\frac ab$ and $d=\gcd(a,b)>1$, then also $\sqrt 2=\frac{a/d}{b/d}$ with $\gcd(a/d,b/d)01$, so we can certainly obtain such a representaion. – Hagen von Eitzen Oct 8 '17 at 15:24
• Actually, you can ignore he concept of $\gcd$ altogether. Instead, we may note that $|b|$ is a natrual number and then pick - among the possibly many representations fo $\sqrt 2$ as fraction - one that minimzes $|b|$ (every non-empty set of naturals has a minimal element!). With this, we instead find that $a$ and $b$ are both even, $a=2a'$, $b=2b'$, and find that $\sqrt 2=\frac{a'}{b'}$ with $|b'|<|b|$, contradiction. – Hagen von Eitzen Oct 8 '17 at 15:29
• @HansLundmark It looks like that question addresses why we may assume no common factors whereas this question seems to be about why we need to assume it. – Trevor Gunn Oct 8 '17 at 15:31

Basically, you could view the contradiction as follows: Every rational number can be written as a fraction of two relatively prime integers. However, $\sqrt{2}$ can not.
To prove that $\sqrt 2$ is irrational, we assume there exists a counter-example. Which in this case means that $\sqrt 2 = \frac{a}{b}$ where $a, b$ are integers. Then we take the smallest counter-example. Here smallest means that the denominator should be as small as possible. For instance $2/4 = 1/2$ and $1/2$ has a smaller denominator. If the denominator is not as small as possible then that means it shares a factor with the numerator so we can equivalently say that $\gcd(a,b) = 1$. Then, in the proof, when we get $a = 2a'$ and $b = 2b'$ we have $\sqrt 2 = \frac{a'}{b'}$ and now $b'$ is a smaller denominator, which is a contradiction.