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 such that 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.)
Assume, to the contrary, that there are only finitely many integers such that is irrational. Then, there is a largest such integer, call it . By the above lemma, we have that or . Say the former, then that means also, and so is irrational as well, since is not a perfect square. But , and so we have found a larger integer than our largest, a contradiction. Assuming yields a similar contradiction.
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?