## Students rule

GR complained to me a few weeks ago that this blog is too technical. Here, then, is something very untechnical.

Problem. Show that $(2^m-1,2^n-1)=2^{(m,n)}-1$ for all integers $m,n \geq 1$. (Here $(a,b)$ 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 $\sup\left\{m,n\right\}$. Without loss of generality, we can assume $m>n$.  By Euclidean division, we have $m=qn+r$ for some unique integers $q,r$ with $0 < r \leq n$, so clearly $(m,n)=(r,n)$ and $2^{(m,n)}-1 = 2^{(r,n)}-1$. But then writing $2^m-1=2^r \cdot (1+2^n + \cdots + 2^{(q-1)n})\cdot (2^n-1)+2^r-1$ shows that $(2^m-1,2^n-1)=(2^r-1,2^n-1)$, and then by the induction hypothesis we get $(2^r-1,2^n-1)=2^{(r,n)}-1$. But we already know the rhs of the last equation is $2^{(m,n)}-1$, so we’re done.

Corey’s solution: Write $k=(2^m-1,2^n-1)$ for brevity.  It’s easy to see that $2^{(m,n)}-1$ divides $k$, so it’s enough to show that $k$ divides $2^{(m,n)}-1$, or equivalently that $2^{(m,n)} = 1\, \mathrm{mod}\,k$. But clearly $2^m = 1\,\mathrm{mod}\,k$ and $2^n = 1\,\mathrm{mod}\,k$, so $2^{am+bn} = 1\,\mathrm{mod}\,k$ for all $a,b \in \mathbf{Z}$. By Bezout’s lemma, we may choose $a,b$ such that $am+bn = (m,n)$, so we’re done.