30
$\begingroup$

There is a very simple proof by means of divisibility that $\sqrt 2$ is irrational. I have to prove that $\sqrt 3$ is irrational too, as a homework. I have done it as follows, ad absurdum:

Suppose $$\sqrt 3= \frac p q$$

with $p/q$ irreducible, then

$$\begin{align} & 3q^2=p^2 \\ & 2q^2=p^2-q^2 \\ &2q^2=(p+q)(p-q) \\ \end{align}$$

Now I exploit the fact that $p$ and $q$ can't be both even, so it is the case that they are either both odd, or have different parity. Suppose then that $p=2n+1$ and $q=2m+1$

Then it is the case that

$$\begin{align} &p-q=2(n-m) \\ &p+q=2(m+n+1) \\ \end{align}$$

Which means that

$$\begin{align} &2q^2=4(m-n)(m+n+1) \\ &q^2=2(m-n)(m+n+1) \\ \end{align}$$

Then $q^2$ is even, and so is then $q$, which is absurd. Similarly, suppose $q=2n$ and $p=2m+1$.

Then $p+q=2(m+n)+1$ and $p-q=2(m-n)+1$. So it is the case that

$$\begin{align} &2q^2=(2(m-n)+1)(2(m+n)+1)\\ &2q^2=4(m^2+m-n^2)+1 \\ \end{align}$$

So $2q^2$ is odd, which is then absurd.


Is this valid?

$\endgroup$
  • 3
    $\begingroup$ There is a very simple proof by means of divisibility that $\sqrt3$ is irrational, too! Why not use that? This proof looks fine. $\endgroup$ – The Chaz 2.0 Apr 13 '12 at 17:56
  • 3
    $\begingroup$ The far simpler proof is use the fact the $p$ and $q$ cannot both divide by 3 leading to a contradiction in two lines. $\endgroup$ – nbubis Apr 13 '12 at 17:56
  • $\begingroup$ @nbubis Hint me, then. $\endgroup$ – Pedro Tamaroff Apr 13 '12 at 17:57
  • 1
    $\begingroup$ @David That'd be a WLOG quintessential. $\endgroup$ – Pedro Tamaroff Apr 13 '12 at 17:59
  • 2
    $\begingroup$ @PeterT.off: You didn't deal explicitly with the case of opposite parity, though you mentioned it. It is clearly impossible. Very nice proof, creative. I had not seen it before. $\endgroup$ – André Nicolas Apr 13 '12 at 18:09

10 Answers 10

13
$\begingroup$

It works, but can be simplified: $\rm\:mod\ 2\!: p\equiv p^2 = 3q^2 \equiv q,\:$ so $\rm\:p,q,\:$ being coprime, are odd. $\rm\:mod\ 4\!:\ odd\equiv \pm 1,\:$ so $\rm\:odd^2\equiv 1,\:$ so $\rm\: 1\equiv p^2 = 3q^2\equiv 3\ \Rightarrow\ 4\:|\:3-1\:\Rightarrow\Leftarrow$

$\endgroup$
  • 2
    $\begingroup$ Peter, the symbolic approach is Bill's style... $\endgroup$ – The Chaz 2.0 Apr 13 '12 at 18:59
  • 2
    $\begingroup$ @Bill It isn't that I can't follow, but rather that I need a middle input{symbol}=output{word} process to read it. $\endgroup$ – Pedro Tamaroff Apr 13 '12 at 20:01
  • 3
    $\begingroup$ this is one way to show that using more symbols isn't helping.. $\endgroup$ – stefan Apr 13 '12 at 23:21
  • 6
    $\begingroup$ @Peter Alas, I have no clue what your prior comment means. What I wrote above is very simple modular arithmetic. It is well-worth your effort to become proficient at such. It's impossible for me to say more unless you can be more specific about what is problematic. $\endgroup$ – Bill Dubuque Apr 13 '12 at 23:28
  • 4
    $\begingroup$ @Peter That is part of the natural learning process. When you become more proficient you'll no longer need to do this translation process (similar to when you master a foreign language). $\endgroup$ – Bill Dubuque Apr 13 '12 at 23:59
29
$\begingroup$

$3q^2 = p^2$, so $3|p$ (as in the case of $\sqrt2$).

Hence $q^2 = 3k$ for some $k$, and then $3|q$

Contradiction.

$\endgroup$
  • $\begingroup$ This is the correct way to do it (in my opinion), because as it is just the same as the usual method for $\sqrt{2}$ and carries across almost unchanged to $\sqrt{p}$ for any prime $p$. It will also carry across without too much work to $\sqrt{n}$ for any non-square $n$. $\endgroup$ – George Lowther May 9 '12 at 19:57
  • $\begingroup$ @George: I would hope that the plenitude of answers to this question would suggest that there is not just one right way to go about this :) $\endgroup$ – The Chaz 2.0 May 9 '12 at 20:05
14
$\begingroup$

Here are some proofs I've found (link at bottom):

If $\sqrt 3 = m/n$: $$ \frac{m}{n} = \sqrt 3 \frac{\sqrt 3 - 1}{\sqrt 3 - 1} = \frac{3-\sqrt 3}{\sqrt 3 - 1} = \frac{3-m/n}{m/n-1} = \frac{3 n - m}{m-n}$$ and the right side has a smaller denominator, since $m < 2n$ (i.e., $\sqrt 3 < 2$).


$x = \sqrt{3} - 1$ is a root of the equation $x^2 + 2x - 2 = 0$, thus: $$x(3+x) = 2+x$$

$$x = \frac{2+x}{3+x} = \cfrac{1}{1 + \cfrac{1}{2 + x}}$$

And thus

$$x = [1,2,1,2,\dots]$$

So $\sqrt{3}$ os irrational.


These proofs and others: How to prove that $\sqrt 3$ is an irrational number?

$\endgroup$
10
$\begingroup$

There is also a really nice proof using what is called reductio ad absurdum (or infinite regress), which can also be framed as a simple contradiction using the minimality property of the natural numbers.

Suppose WLOG (without loss of generality) that $$\sqrt3=\frac{u}{v}$$ for $u,v\in\mathbb{N}$ relatively prime (any positive rational number in $\mathbb{Q}$ can be expressed as a fraction in lowest terms). The reason we can assume $u,v\in\mathbb{N}$ rather than $\mathbb{Z}$ without losing the generality of our argument is because any case in the latter category furnishes one in the former by observing that $3>0$ so that $u$ and $v$ must have the same sign, and if they are negative, then $-u,-v\in\mathbb{N}$ also has the same ratio. So then $$u^2=3\,v^2.$$ But $3$ is prime and divides the RHS, hence it divides the LHS, and that means it must divide $u$ (it is a fact, known as Euclid's Lemma, that if $p$ is prime, then $p|ab \implies p|a$ or $p|b$). But then $3|u=u_0$ means that $u=3u_1$ for some $u_1\in\mathbb{N}$, and consequently, $$9u_1^2=(3u_1)^2=3v^2 \quad\implies\quad 3u_1^2=v^2.$$ At this point, if we have not assumed that $u,v$ are relatively prime, we continue by noting that $v=v_0=3v_1$ for some $v_1\in\mathbb{N}$, whence $u_1^2=3v_1^2$ $\implies\cdots\implies$ $$\forall n\in\mathbb{N}:u_n=u\cdot3^{-n},~v_n=v\cdot3^{-n}\in\mathbb{N}$$ which is an impossible infinite regress, also called a reductio ad absurdum (reduction to absurdity). The absurdity, impossibility, or contradiction it leads to is that, from the hypothesis, it shows that the natural numbers $u$ and $v$ are infinitely divisible, while we know that for some $N\in\mathbb{N}$ (eventually, sufficiently large), $\frac{u}{3^n}$ and $\frac{v}{3^n}$ are obviously less than $1$ and thus not whole numbers for all $n\ge N$.

A more elegant variation (avoiding these "infinite gymnastics") is to use the stipulation, which we can make without loss of generality, that $u$ and $v$ are relatively prime. Then, we can stop as soon as we deduce that $3|v$, since at this point we already knew that $3|u$.

An even more elegant variation uses the well-orderedness of $\mathbb{N}$, where we also suppose to begin with that $u$ and $v$ are minimal (or if in doubt about whether we can simultaneously require this of both variables, suppose that either $u$ or $v$ is minimal). Then, as soon as we discover our first extra factor of $3$, we already reach a contradiction.

$\endgroup$
  • $\begingroup$ Great answer! But I do use reductio ad absurdum, don't I? I like the fact the proof you give arrives to $\dfrac u {3^n}$, since then we can use Arichimede's priniciple $x <n$ for every $x \in \mathbb R$ and some appropriately large enough $n \in \mathbb N$. $\endgroup$ – Pedro Tamaroff Apr 13 '12 at 19:59
  • 3
    $\begingroup$ Who downvoted?! $\endgroup$ – Pedro Tamaroff Apr 13 '12 at 20:02
  • 1
    $\begingroup$ Yes, of course you knew and used reductio ad absurdum, I just thought this was a proof worth knowing for its simplicity and didactic versatility. One downvote doesn't matter; we can rely on the law of large numbers to determine the post's merit over time. $\endgroup$ – bgins Apr 13 '12 at 20:04
8
$\begingroup$

I'll just add to this mayhem with this bit of logic.

Assume $\sqrt{3}=\frac{a}{b}\implies3=\frac{a^2}{b^2}\implies3b^2=a^2$. Now, this cannot be true! When you square something, you double all of its prime factors. Then we know $a^2$ and $b^2$ have an even number of factors, therefor $3b^2$ has an odd number of factors because we have added a factor of $3$. So $3b^2 \neq a^2$.

$\endgroup$
  • 1
    $\begingroup$ And, for similar reasons, the $\sqrt[r]{n}$ is irrational for any $n$ which isn't an $r$'th power. $\endgroup$ – George Lowther May 9 '12 at 19:59
6
$\begingroup$

Here is a proof using some results from field theory: Suppose that $\sqrt{3}$ is rational. Then the polynomial $x^2 - 3$ has a root in $\Bbb{Q}$. However we know for degree 2 polynomials that having a root in $\Bbb{Q}$ is equivalent to the polynomial being reducible over $\Bbb{Q}$. But then by Eisenstein's criterion with $p=3$ we have that $x^2 -3$ is irreducible over $\Bbb{Q}$ which is a contradiction.

$\textbf{Edit:}$ Here are some applications of this method. Suppose you want to prove that $\sqrt{2} + \sqrt{3}$ is irrational. For a contradiction suppose it is not. Then you can write $\sqrt{2} +\sqrt{3} = p$ for some rational number $p$, so that squaring both sides we have that $\frac{p^2 -5}{2} = \sqrt{6}$. This is saying that $\sqrt{6}$ is a rational number. However if it is, then the polynomial $x^2 - 6$ is reducible over $\Bbb{Q}$. But then this is a contradiction because Eisenstein's Criterion with $p=3$ or $p=2$ shows that $x^2 - 6$ is irreducible over $\Bbb{Q}$. Done.

Generalisation of this by Eisenstein's Criterion: The square root of any square free positive integer is irrational.

$\endgroup$
  • $\begingroup$ What is Eisenstein's criterion? What does it mean that a polynomial is irreducible over a set of numbers? Sorry, but I don't know about that. However, I'd be glad if you gave me the basics. $\endgroup$ – Pedro Tamaroff Apr 13 '12 at 22:54
  • 1
    $\begingroup$ @PeterT.off First let $f(x)$ be a polynomial with rational coefficients. We say that $f$ is irreducible over $\Bbb{Q}$ if it is not possible to write $f = gh$ for $g$ and $h$ polynomials of degree at least $1$ with coefficients in $\Bbb{Q}$. Eisenstein's criterion (which you can check in wikipedia) is a test to tell if a polynomial is irreducible over $\Bbb{Q}$ or not. In fact I think it even works for the fraction field of just any unique factorisation domain. $\endgroup$ – user38268 Apr 13 '12 at 23:19
  • 2
    $\begingroup$ @Peter: Eisenstein's is, very crudely, a more elaborate version of the rational roots theorem... :) $\endgroup$ – J. M. isn't a mathematician Apr 14 '12 at 4:45
  • $\begingroup$ @PeterT.off Please see edit above. $\endgroup$ – user38268 Apr 19 '12 at 1:25
  • $\begingroup$ @BenjaminLim Thanks for that add! $\endgroup$ – Pedro Tamaroff Apr 19 '12 at 1:49
6
$\begingroup$

A proof of R. Dedekind, from 1901.

(He proves that if $n\in\mathbb{N}$ is not a square number, then $\sqrt{n}$ is irrational.)

$\sqrt{3}$ is irrational.

Proof: Suppose that $\sqrt{3}=\frac{x}{y}$, $x$ and $y$ are integers, when $x$ is the smallest integer which satisfies that equation. (If there exist $x$ and $y$ such that $\sqrt{3}=\frac{x}{y}$ then exist that minimal $x$, $\mathbb{N}$ is well-ordered set and $x$ is there). $\frac{x}{y}$ is not an integer ($3$ is not a perfect square), hence exist $k\in\mathbb{N}$, such that:

$$k-1<\frac{x}{y}<k$$

Now, let us look at

$$x'=(k-\frac{x}{y})x=kx-3y \ \ \ \ ; \ \ \ \ y'=(k-\frac{x}{y})y=ky-x $$

Furthermore, $x$ and $y$ are integers, and:

$$\frac{x'}{y'}=\frac{x}{y}=\sqrt{3}$$

But, $k-\frac{x}{y}<1$, therefor $x'<x$, and that is a contradiction to the fact that out $x$ chosen to be the minimal which satisfies $\sqrt{3}=\frac{x}{y}$.

$\blacksquare$

$\endgroup$
5
$\begingroup$

Here's another proof:

Binomial expansion shows that $(\sqrt{3}- 1)^n = p_n + q_n \sqrt{3}$ where $p_n, q_n$ are integers. The sequence $(\sqrt{3}-1)^n = p_n + q_n \sqrt{3}$ is always nonzero, but it tends to $0$ as $n \to \infty$. Thus for any $\delta > 0$, for sufficiently large $n$ (depending on $\delta$), the number $\sqrt{3}$ admits a "good" rational approximation $-p_n/q_n$ (note the minus sign), in the sense that $$0 < |q_n \sqrt{3} + p_n| < \delta .$$ This shows that $\sqrt{3}$ must be irrational.

The proof is, of course, not original; it is perhaps folklore.

$\endgroup$
  • $\begingroup$ I have made the post CW since it does not really answer the question. $\endgroup$ – Srivatsan Apr 19 '12 at 2:27
  • $\begingroup$ This should have more upvotes... could you add some more? $\endgroup$ – Pedro Tamaroff May 10 '12 at 19:48
4
$\begingroup$

One can show a more general result, that is for any prime number $p$ we must have $\sqrt{p}$ is irrational. see my answer here.

$\endgroup$
3
$\begingroup$

Your proof is simple and easy to be understood, but I think the last equation $$ 2q^2 = 2(m^2 + 2m - n^2) + 1 $$ is wrong, which should be $$ 2q^2 = 4(m^2 + m - n^2) + 1 $$

$\endgroup$

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