GR complained to me a few weeks ago that this blog is too technical. Here, then, is something very untechnical.
Problem. Show that for all integers . (Here denotes the GCD as usual.)
This is a well-known cheeky question in elementary number theory; I first learned it when I worked at PROMYS. Anyway, I put this as a 25-point extra credit problem on the final exam in my number theory class this past semester. Two students (out of 54) solved it, but their solutions were both awesome. Here’s what they did:
Hamza’s solution: Induction on . Without loss of generality, we can assume . By Euclidean division, we have for some unique integers with , so clearly and . But then writing shows that , and then by the induction hypothesis we get . But we already know the rhs of the last equation is , so we’re done.
Corey’s solution: Write for brevity. It’s easy to see that divides , so it’s enough to show that divides , or equivalently that . But clearly and , so for all . By Bezout’s lemma, we may choose such that , so we’re done.