Simple proof for the infinitude of surds

• Mar 5th 2009, 09:03 PM
Jhevon
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
• Mar 5th 2009, 09:12 PM
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!
• Mar 5th 2009, 09:50 PM
Jhevon
Quote:

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.
• Mar 7th 2009, 03:06 AM
Laurent
Quote:

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!

Quote:

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).
• Mar 7th 2009, 06:31 AM
Jhevon
Quote:

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
• Mar 7th 2009, 06:41 AM
Jhevon
Quote:

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.