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

Proof:

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.

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