If is a given rational number, the process

write p/q = n + k/q, where 0 ≤ k/q < 1, equiv 0 ≤ k < q. if k = 0: halt; else return q/k, and loop.

is guaranteed to halt, since we must eventually hit , as the denominator is strictly smaller after each non-terminating cycle.

Assume is a rational number satisfying . By inspection, . Apply the process above:

r = 1 + (r-1) --> 1/(r-1) = (r+1)/(r^2 - 1) = r+1 = 2 + (r-1) --> 1/(r-1)

Which will never halt, so no such rational number can exist.

I learned this nice proof from Doron Zeilberger’s manuscript *Two Motivated Concrete Proofs (much better than the usual one) that the Square-Root of 2 is Irrational* .