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.

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s