I was asked to sketch the proof for the irrationality of sqrt(2) in a quant programming interview. I kind of froze, and explained that though I had learned it, I could not recall.
He prompted me with "Well, what does it mean to be irrational?", and with that little hint I did the rest. Though ultimately I did not end up working there, it was very satisfying to have answered it.
Well, in one case (me), all the information the interviewer had was "this guy happens to know how to implement a quick sort by heart. K.".
In the other case (my friend), he got "this guy is able to understand and implement an algo he never saw before in a reasonable time", which is much more impressive
Assume sqrt(2) is rational and has the reduced form (x/y). Thus we are assuming that x and y are integers and that gcd(x,y) is 1. You square it and get x^2/y^2 which are somehow simultaneously coprime integers and also reducible to 2/1...
> We now show that the equation (1) p^2=2 is not satisfied by any rational p. If there were such a p, we could write p=m/n where m and n are integers that are not both even. Let us assume this is done. Then (1) implies (2) m^2=2n^2. This shows m^2 is even. Hence m is even (if m were odd, m^2 would be odd), and so m^2 is divisible by 4. It follows that the right side of (2) is divisible by 4, so that n^2 is even, which implies that n is even. > The assumption that (1) holds leads to the conclusion that both m and n are even, contrary to our choice of m and n. Hence (1) is impossible for rational p.