This question already has an answer here:

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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
up vote 1 down vote accepted

A rational number could be written as a fraction of two integers that are not relatively prime. However, we can write a rational number as a fraction of two relatively prime integers. Hence, if we take these to integers, we can prove that in fact, they are not relatively prime, then it contradicts this assumption

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.

The name for such a method of proof is "infinite descent" where one assumes there exists a counter-example and allows themself to have chosen the "smallest" counter-example and then uses that counter-example to construct a "smaller" counter-example.

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.