Observe that if $\sqrt 2$ is rational, then there is some positive integer q such that $q \times \sqrt 2$ is an integer. Since the positive integers are well ordered, we may suppose that $q$ is the smallest such number.

We next observe that since $1 < \sqrt 2 < 2$, then $\sqrt 2 - 1 < 1$, and consequently $q \times (\sqrt 2 - 1) = (q \times \sqrt 2 - q )$ is less than $q$. Let us call this new number $r$, and observe that it too is a positive integer. But we now have $r \times \sqrt 2$ is also an integer, since $r\times \sqrt 2 = (q \times \sqrt 2-q ) \times \sqrt 2 = (2q - q \times\sqrt 2)$. In short, $r$ is a positive integer less than $q$ and $r \times\sqrt 2$ is an integer. But we said that $q$ was the smallest positive integer with this property, and so we have a contradiction.

The nice thing about this proof is how easily it generalizes. Let us denote by $|\sqrt n|$ the integer part of $\sqrt n$ . For example, since the square root of $5$ is approximately $2.236$, the integer part is $2$. For any $n$ that is not a perfect square, we may prove that is irrational exactly as above by considering $q \times ( \sqrt n -|\sqrt n|)$. (On the other hand, if $n$ is a perfect square (so that $\sqrt n = |\sqrt n|$) then there is no contradiction.)

More generally still, if $x$ is a rational but not integral zero of a monic integer polynomial of degree $d$, let $q$ be the least positive integer so that $qx^j$ is integral for all $j < d$. Then, considering $q(x - n)$ where $n$ is an integer with $n < x < n + 1$, we get a contradiction. In other words, we have proved that every rational “algebraic integer” is an integer.