Theorem: $\sqrt{2}$ is irrational

Proof (By contradiction): Assume, on the contrary that $\sqrt{2}$ is rational Then there are natural numbers $p$ and $q$, with no common factors, such that $\sqrt{2} = \frac{p}{q}$

Squaring: $2 = \frac{p^2}{q^2}$
Rearranging: $2q^2 = p^2$

So $p^2$ is even ( it is equal to twice something $ \to 2 \times q^2$ ), Hence $p$ is even.

(Why?): Because the square of an even number is even, and the square of an odd number is odd. So the only way to get the square of a number to be even is if the number is even

So $p$ is $2r$ for some $r$
Substituting for $p$: $ 2q^2 = 2r^2 = 4r^2 $
Cancelling $2$: $ q^2 = 2r^2$

So $q^2$ is even ( it is equal to twice something $\to 2 \times r^2$ ), Hence $q$ is even (Reason: See Why?)

Deduction: $p$ is even, $q$ is even...

Conclusion: if both $p$ and $q$ are even, then they have $2$ as a common factor; but by the original assumption: ...Then there are natural numbers p and q, with no common factors, this shows that $p$ and $q$ cannot have a common factor. Since this conclusion does not agree with the assumption, this means that $\sqrt{2}$ is irrational. QED

I have a couple questions about the proof:

  • If I have an even number $N$, then isn't it possible to factor this number until it is odd? Then wouldn't this mean that although $p$ and $q$ are even, they can be factored until no more factors are possible?

  • Is it correct to assume that any rational number can be expressed as the quotient of $2$ other numbers who have no common factors?

  • 1
    $\begingroup$ Your contradiction comes from the fact that you assumed $p$ and $q$ have no common factor, yet showed they are both divisible by $2$. What further factorization is possible for either number is really inconsequential. As to your question about $N$, what can you say if $N=32$ for instance? You can continue to factor out $2$'s, but always get an even quotient. Finally, a rational number is, by definition, a quotient of integers (denominator $\neq 0, of course). You can always cancel common factors so that numerator and denominator are relatively prime. $\endgroup$ – Chris Leary Mar 10 '14 at 17:25

Yes, you could instead (uniquely!) write $\,p = 2^j a\,$ and $\,q = 2^k b\,$ for $\,a,b\,$ odd and then deduce a contradiction by comparing the number of factors of $2,\,$ viz. $\,p^2\,$ has an even number of $2$'s but $\,2q^2\,$ has an odd number of $2$'s, a contradiction. This method uses only the very easily-proved existence and uniqueness of $2$-factorizations, i.e. representations of the form $\,2^j n,\,$ with $\,n\,$ odd (versus the much more powerful, and much more difficult to prove Fundamental Theorem of Arithmetic = existence and uniqueness of arbitrary prime factorizations).

As for your second question, yes, every fraction $\,A/B\,$ can be written with coprime numerator and denominator $\,a/b\,$ simply by cancelling their gcd $\,c,\,$ i.e. $\,A/B = ca/cb = a/b.\,$ By the maximality ("greatest") property of the gcd it follows that $\,d =\gcd(a,b) = 1,\,$ else $\,cd\,$ would be a common divisor of $\,A,B\,$ larger than the greatest common divisor $\,c=\gcd(A,B),\,$ contradiction. However, as above, it suffices to cancel only common factors of $\,2,\,$ so no knowledge of gcds is required.


You are correct that you can always factor a number $N$ to take away the even part; that is, we can always write

$$ N = 2^p (2k-1) $$

for some $p, k$. However, the contradiction in this case arises from your second question: Yes, it is always possible to write any rational number as a quotient of two integers with no common factors. In particular, if we write $N = p/q$ then we can arrange it so that at most one of $p, q$ are even.

However, from the argument above we see that if $\sqrt{2} = p/q$, then it would have to follow that no matter how we wrote this, that both $p$ and $q$ are even, which contradicts the above observation.

There is another way of thinking about this:

We can always write (by the fundamental theorem of arithmetic) any number as

$$ N = 2^{n_2}3^{n_3}5^{n_5}7^{n_7} \cdots $$

and so if apply this to $p, q$ as obtained previously we would see that they are both even. We could then (by cancelling a power of 2 from each of them) see that there are strictly smaller integers $p_1, q_1$ (since they have fewer factors of 2) such that

$$ \sqrt{2} = \frac{p_1}{q_1} $$

But the same argument shows that these two numbers must be also even. Hence we can find yet strictly smaller integers $p_2, q_2$ such that...

we then obtain a strictly decreasing sequence of positive integers $p_1 > p_2 > \ldots$. However, by the well-ordering principle, any such sequence must have a smallest element, which is a contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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