29
$\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?

  • 3
    There is a very simple proof by means of divisibility that $\sqrt3$ is irrational, too! Why not use that? This proof looks fine.2012-04-13
  • 3
    The far simpler proof is use the fact the $p$ and $q$ cannot both divide by 3 leading to a contradiction in two lines.2012-04-13
  • 0
    @nbubis Hint me, then.2012-04-13
  • 0
    It looks ok, except that you forgot to mention the third case (which would have an argument entirely similar to the second case).2012-04-13
  • 1
    @David That'd be a WLOG quintessential.2012-04-13
  • 2
    @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.2012-04-13
  • 0
    @Chaz I want to produce one of my own.2012-04-13
  • 0
    Your proof is fine; I present a few variations of a standard proof and the assumptions/methods needed along the way and for the endgame (contradiction) in my post below, such as Euclid's lemma & well-orderedness.2012-04-13
  • 0
    380 Views!$\,\,$2012-05-03
  • 0
    @AD. Yet not a **good question** badge!2012-05-03
  • 0
    Wish you good luck on that :)2012-05-03
  • 0
    I'm still baffled by the 3 downvotes on this question.2012-08-21
  • 0
    This is an old thread, but you can simplify your proof by noticing that $p - q$, and $p + q$ are both odd, or even (since $p + q = (p - q) + 2q$), so from $2q^2 = (p - q) (p + q)$, we can deduce directly that both $p - q$, and $p + q$ must be even. So we only need to consider 2 cases.2013-07-27

10 Answers 10

2

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 $$

27

$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.

  • 0
    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$.2012-05-09
  • 0
    @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 :)2012-05-09
13

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?

12

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$

  • 0
    What is problematic? Do you know modular arithmetic?2012-04-13
  • 2
    Peter, the symbolic approach is Bill's *style*...2012-04-13
  • 0
    @Bill I do know modular arithmetic, but I don't use it everyday, so I have to rather translate it bit by bit.2012-04-13
  • 0
    @Peter Please tell me what parts you cannot follow I will be happy to elaborate.2012-04-13
  • 2
    @Bill It isn't that I can't follow, but rather that I need a middle `input{symbol}=output{word}` process to read it.2012-04-13
  • 3
    this is one way to show that using more symbols isn't helping..2012-04-13
  • 4
    @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.2012-04-13
  • 0
    @Downvoter If something is not clear then please feel free to ask questions and I will be happy to elaborate.2012-04-13
  • 0
    @Bill What I mean is that I understand your proof, but since I'm not proficient at M.A. I have to change symbols to words instead of processing symbols directly (as I would do for other areas). However, now that I've freshened up my mind I get it perfectly.2012-04-13
  • 3
    @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).2012-04-13
9

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.

  • 0
    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 for every $x \in \mathbb R$ and some appropriately large enough $n \in \mathbb N$.2012-04-13
  • 3
    Who downvoted?!2012-04-13
  • 1
    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.2012-04-13
7

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$.

  • 1
    And, for similar reasons, the $\sqrt[r]{n}$ is irrational for any $n$ which isn't an $r$'th power.2012-05-09
5

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.

  • 0
    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.2012-04-13
  • 1
    @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.2012-04-13
  • 2
    @Peter: Eisenstein's is, very crudely, a more elaborate version of the rational roots theorem... :)2012-04-14
  • 0
    @PeterT.off Please see edit above.2012-04-19
  • 0
    @BenjaminLim Thanks for that add!2012-04-19
  • 0
    @PeterT.off I saw the question you deleted. So I edited my answer to add that in :D :D :D2012-04-19
5

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}

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$ chosen to be the minimal which satisfies $\sqrt{3}=\frac{x}{y}$.

$\blacksquare$

4

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.

  • 0
    I have made the post CW since it does not really answer the question.2012-04-19
  • 0
    This should have more upvotes... could you add some more?2012-05-10
3

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.