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 $\displaystyle n$ such that $\displaystyle \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 $\displaystyle n$ such that $\displaystyle \sqrt{n}$ is irrational. Then, there is a largest such integer, call it $\displaystyle x$. By the above lemma, we have that $\displaystyle x \equiv 2 ~(\text{mod }4)$ or $\displaystyle x \equiv 3~( \text{mod }4)$. Say the former, then that means $\displaystyle x + 4 \equiv 2 ~(\text{mod }4)$ also, and so $\displaystyle \sqrt{x + 4}$ is irrational as well, since $\displaystyle x + 4$ is not a perfect square. But $\displaystyle x + 4 > x$, and so we have found a larger integer than our largest, a contradiction. Assuming $\displaystyle 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