I'm trying find where the common proof by contradiction that $\sqrt 2$ is irrational breaks down when trying to prove $\sqrt 4$ is irrational.

Assume $\left(\frac pq\right)^2=4$ and $\gcd(p,q)=1$. I guess I could just let $p=2, q=1$ and be done, but why is that an adequate failure of the proof? If it's not, then where else does the proof break down?

Continuing the "proof": Then $p^2=4q^2$, so $p$ is even, that is, $p=2r$. That implies that $4r^2=4q^2$, or that $q=r$.

If $p=2r$ and $q=r$ then $\gcd(p,q)=r$ which contradicts $\gcd(p,q)=1$, leaving us with the untenable conclusion that $\sqrt 4$ is irrational.

  • 12
    $\begingroup$ Why can't $r=1$? $\endgroup$ – John Brevik Apr 25 '15 at 23:43
  • 1
    $\begingroup$ In fact $r$ has to be $1$ if you have $q=r, p=2r$ and $(\frac{p}{q})^2=4$. Then $\frac{p}{q}$ in nothing more than $2$, exactly what you should expect! $\endgroup$ – truebaran Apr 25 '15 at 23:48
  • $\begingroup$ I think $r$ can be any number, @truebaran, since it cancels. $\endgroup$ – Jeff Apr 26 '15 at 3:07
  • $\begingroup$ The necessary theorem is the fundamental theorem of arithmetic $\endgroup$ – Matthew Levy Apr 26 '15 at 3:40
  • 1
    $\begingroup$ @truebaran You also need that $\frac pq$ is in lowest terms, no? $\endgroup$ – Akiva Weinberger Apr 26 '15 at 4:10

It does not contradict the relatively prime assumption because we can take $r=1$.


I think this is a good example of how proofs by contradiction are a bad habit. Once you run into a contradiction, you think you're done. But how do you know you haven't just made a mistake, introducing a new contradiction?

Here is a proof that $\sqrt{2}$ is irrational which is not a proof by contradiction and incidentally which tells you exactly what happens with $\sqrt{4}$. The distinction between this proof and a proof by contradiction is that everything I'm about to say is true.

The key idea is that unique prime factorization can be extended to rational numbers: in the same way that any nonzero integer $n$ has a unique prime factorization

$$n = \pm \prod_p p^{\nu_p(n)}$$

where the exponents $\nu_p(n)$ are non-negative integers and the product runs over all primes, any rational number $r$ has a unique prime factorization

$$r = \pm \prod_p p^{\nu_p(r)}$$

where the exponents $\nu_p(r)$ are now allowed to be negative. If we write $r$ as a fraction $\frac{n}{m}$ then the factorization of $r$ is just given by dividing the factorization of $n$ by the factorization of $m$, and the exponents subtract.

The reason it's cool to write the exponents $\nu_p(r)$ explicitly as a function of $r$ is that this makes it easier to state the very important observation that when you multiply two rational numbers together, the exponents in their unique prime factorizations add:

$$\nu_p(rs) = \nu_p(r) + \nu_p(s).$$

In particular,

$$\boxed{ \nu_p(r^2) = 2 \nu_p(r) }.$$

That is, if $r^2$ is the square of a rational number, then the exponents in its prime factorization must all be even. So why can't $2$ be the square of a rational number? Because one of the exponents in its prime factorization - namely the exponent of $2$ - is odd. And why doesn't $4$ succumb to this argument? Because $4 = 2^2$, so all of the exponents in its prime factorization are even.

This argument proves with no further difficulty that lots of other numbers are irrational besides $\sqrt{2}$: namely, if $n$ and $k$ are positive integers, then $\sqrt[k]{n}$ is rational if and only if every exponent $\nu_p(n)$ in the prime factorization of $n$ is divisible by $k$.

  • $\begingroup$ How do you know that your direct proof doesn't have gaps in it? Even if you think you're careful, how can you be sure? But I do agree that we should strive to minimize the proofs by contradiction that we use, if only because those can often pile up and then you lose track of your proof, and sight of the theorem. $\endgroup$ – Asaf Karagila Apr 26 '15 at 4:20
  • $\begingroup$ @Asaf: In a direct proof, I can check the statements I'm making against mathematical reality; in this case, I can look at examples of natural numbers, and I can verify that everything I've just said holds for those examples. In the standard proof by contradiction that $\sqrt{2}$ is irrational I can't check anything I'm saying against examples of positive integers $n, m$ such that $n^2 = 2m^2$, because there aren't any! $\endgroup$ – Qiaochu Yuan Apr 26 '15 at 4:22
  • $\begingroup$ In this particular case, sure. But the first statement against contradiction based proof is much broader than $\sqrt2\notin\Bbb Q$. $\endgroup$ – Asaf Karagila Apr 26 '15 at 4:25

Another common proof that $\sqrt{n}$ is irrational if $n$ is not a perfect square is here: $\sqrt{17}$ is irrational: the Well-ordering Principle

It depends on the fact that $n$ is not a perfect square if and only if $\lfloor \sqrt{n} \rfloor < \sqrt{n} $.

  • $\begingroup$ Isn't the last sentence trivially true. If its less than it can't be an integer itself... $\endgroup$ – Matthew Levy Apr 26 '15 at 3:42
  • $\begingroup$ @Matthew: Not an integer, sure. Why does that mean it is irrational? $\endgroup$ – Asaf Karagila Apr 26 '15 at 3:44
  • $\begingroup$ It doesn't, I think I misunderstood. The last statement does not need proof is what I'm saying. $\endgroup$ – Matthew Levy Apr 26 '15 at 3:45

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.