# Proof that the square root of 2 is irrational

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
Homework Helper
Gold Member
\
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)##.

Last edited:
jedishrfu
Mentor
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
Mentor
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.

Last edited:
Math_QED