Undergrad Proof that the square root of 2 is irrational

[Mr Davis 97]

Quick question: In the proof that the square root of 2 is irrational, when we are arguing by contradiction, why are we allowed to assume that $\displaystyle \frac{p}{q}$ is in lowest terms? What if we assumed that they weren't in lowest terms, or what if we assumed that $\operatorname{gcd} (p,q)=2$? Would the contradiction still follow?

 

[andrewkirk]

\

why are we allowed to assume that $\frac{p}{q}$ is in lowest terms?

We are using (without citing it) the fact that $p,q$ are positive integers and that the set of positive integers is well-ordered, meaning that every subset has a least element. That guarantees that there exists a unique representation of the fraction in lowest terms, because the set S of all numerators of representations of the fraction is a subset of the positive integers and so must have a least element m. We choose the subset of S that have numerators equal to m. Then we observe that if m/a and m/b are both representations of the fraction, we have m/a=m/b and neither of a nor b is zero, so that a=b, so there is only one representation with numerator m.

BTW, we don't need to assume p and q are on lowest terms. All we need to assume to get the proof to work is that 2 is not a common factor of both, ie that $2\not| \ \gcd(p,q)$.

If we don't assume that, as would be the case if $\gcd(p,q)=2$, we can't get our contradiction. We could probably recover it by then entering into a long induction, but there's no need to do that since we can just assume lowest terms, which implies $2\not| \ \gcd(p,q)$.

 

[jedishrfu]

This discussion may help:

http://mathforum.org/library/drmath/view/52612.html

Basically, we start by assuming that $\sqrt{2}$ is rational then we can conclude that there exists a fully reduced ratio of integers p/q that represent it. From there the proof goes on to show that p/q isn't fully reduced.

It's a key part of the proof. You could start with that notion and then state that there is a common factor to the top and bottom that can be factored out to get a reduced ratio but it is just a side show and it just detracts from the elegance of the proof.

But wait until other mentors reply to get their opinion.

 

[fresh_42]

Quick question: In the proof that the square root of 2 is irrational, when we are arguing by contradiction, why are we allowed to assume that $\displaystyle \frac{p}{q}$ is in lowest terms? What if we assumed that they weren't in lowest terms, or what if we assumed that $\operatorname{gcd} (p,q)=2$? Would the contradiction still follow?

You only need the fact that every integer can be written as a product of primes in a unique way ($\,$up to $\pm1\,$). This way you get $\sqrt{2}=\frac{n}{m} \Longrightarrow 2m^2=n^2$ and you end up with one factor $2$ more on the left than on the right. Strictly speaking one also uses that $\mathbb{Z}$ has no zero divisors, because it allows to cancel out all primes, which are on the left and on the right.

 

[member 587159]

Quick question: In the proof that the square root of 2 is irrational, when we are arguing by contradiction, why are we allowed to assume that $\displaystyle \frac{p}{q}$ is in lowest terms? What if we assumed that they weren't in lowest terms, or what if we assumed that $\operatorname{gcd} (p,q)=2$? Would the contradiction still follow?

It would follow that $gcd(p,q) = 2$, meaning both numerator and denumerator have a factor $2$. You can cancel it. Repeat the process until no more common factors 2 are there (why is this possible?). Conclude that $\sqrt{2}$ is irrational.