# Math Help - Simple proof for the infinitude of surds

1. ## Simple proof for the infinitude of surds

I am teaching a student proofs this semester. I came across a problem in the text that I cannot think of a simple solution for.

It is in the chapter on "Proof by Contradiction" (the text we are using, for those who are interested, is "Mathematical Proofs: A transition to advanced Mathematics" by Chartrand).

Anyway, here is the problem and here is my proof, which I am pretty sure is valid.

Result: Prove that there are infinitely many positive integers $n$ such that $\sqrt{n}$ is irrational.

I will use the fact that if an integer is a perfect square, then it is equivalent to 0 mod 4 or 1 mod 4, as a lemma. (I would prove this separately, or better yet, ask the student to prove it.)

Proof:

Assume, to the contrary, that there are only finitely many integers $n$ such that $\sqrt{n}$ is irrational. Then, there is a largest such integer, call it $x$. By the above lemma, we have that $x \equiv 2 ~(\text{mod }4)$ or $x \equiv 3~( \text{mod }4)$. Say the former, then that means $x + 4 \equiv 2 ~(\text{mod }4)$ also, and so $\sqrt{x + 4}$ is irrational as well, since $x + 4$ is not a perfect square. But $x + 4 > x$, and so we have found a larger integer than our largest, a contradiction. Assuming $x \equiv 3 ~(\text{mod }4)$ yields a similar contradiction.

QED

So here's the thing: I know it's a famous result, but the book has not mentioned the lemma I used. And it is not something I think a person who is a beginner when it comes to proofs (and is also a novice when it comes to set theory and number theory) can come up with. I can't really think of any simple ways to prove it though. Do you guys know any easier way?

Thanks

2. This is what Euclid would do. Say there are finitely many of them: $a_1,...,a_N$. So that $\sqrt{a_j}$ is rational. Then $a=a_1...a_N$ has property that $\sqrt{a}$ is rational. However, $a\not \in \{a_1,...,a_N\}$ because $a>a_j$. A contradiction!

3. Originally Posted by ThePerfectHacker
This is what Euclid would do. Say there are finitely many of them: $a_1,...,a_N$. So that $\sqrt{a_j}$ is rational. Then $a=a_1...a_N$ has property that $\sqrt{a}$ is rational. However, $a\not \in \{a_1,...,a_N\}$ because $a>a_j$. A contradiction!
Yes, that proof does have a Euclid feel to it.

do you think that's something that a 308 student should be able to come up with?

by the way, what is $a_j$ here. and did you mean to say "irrational" when you said "rational"?

Thanks.

4. Originally Posted by ThePerfectHacker
This is what Euclid would do. Say there are finitely many of them: $a_1,...,a_N$. So that $\sqrt{a_j}$ is rational. Then $a=a_1...a_N$ has property that $\sqrt{a}$ is rational. However, $a\not \in \{a_1,...,a_N\}$ because $a>a_j$. A contradiction!
Originally Posted by Jhevon
by the way, what is $a_j$ here. and did you mean to say "irrational" when you said "rational"?
Yes, it should be "irrational", and that causes the proof to fail: $\sqrt{2}$ and $2\sqrt{2}$ are distinct irrational numbers, yet their product is not.

In order to prove the theorem, I would give an easy and well-worth knowing proof that $\sqrt{2}$ is irrational, and then say that $n\sqrt{2}=\sqrt{n^22}$ is irrational for all $n$ (otherwise, $\sqrt{2}$ would be rational). This is a constructive proof, which perhaps is not what you want, but after all the fact that $\sqrt{2}$ is irrational is a must-know one (both historically and since proof is elementary).

5. Originally Posted by Laurent
Yes, it should be "irrational", and that causes the proof to fail: $\sqrt{2}$ and $2\sqrt{2}$ are distinct irrational numbers, yet their product is not.

In order to prove the theorem, I would give an easy and well-worth knowing proof that $\sqrt{2}$ is irrational, and then say that $n\sqrt{2}=\sqrt{n^22}$ is irrational for all $n$ (otherwise, $\sqrt{2}$ would be rational). This is a constructive proof, which perhaps is not what you want, but after all the fact that $\sqrt{2}$ is irrational is a must-know one (both historically and since proof is elementary).
Ah, thanks. that is a nice way.

whether the proof is constructive or not doesn't matter to me. as long as it is a simple one that a beginner can understand. if anything, i can offer hints along with the question so the student knows what direction i want them to think in

6. Originally Posted by ThePerfectHacker
...Then $a=a_1...a_N$ has property that $\sqrt{a}$ is irrational....
in light of what Laurent said (it had occured to me when i read the proof at first) how does this follow? since if $\sqrt{x}$ is irrational and $\sqrt{y}$ is irrational, it does not imply that $\sqrt{xy}$ is irrational.

i am thinking of doing a combination of the proofs you and Laurent posted, but that might be too complicated. a constructive proof is perhaps best for the level this student is at. i will be asking them to prove $\sqrt{2}$ is irrational--it's a famous result, i have to make sure they can do it--so maybe using that somehow would be good.

EDIT: Ah, it seems TPH's proof was about rational square roots, not irrational ones.