Yesterday, Manhattan GMAT posted a GMAT question on our blog. Today, they have followed up with the answer:
One quick way to solve this problem is to pick numbers for n. Say n = 2 (which is legal, since 2 is not a multiple of 7). Then we just need to test 22, 23, 24, 25, and 26—that is, divide them by 7 and check the remainder. If the remainder is not 1, then m cannot be that exponent (since the remainder must be 1 for every allowed value of n).
22 = 4. The remainder after 4 is divided by 7 is 4, so m cannot be 2. Cross out A.
23 = 8. The remainder after 8 is divided by 7 is 1, so m could be 3. Leave B.
24 = 16. The remainder after 16 is divided by 7 is 2, so m cannot be 4. Cross out C.
25 = 32. The remainder after 32 is divided by 7 is 4, so m cannot be 5. Cross out D.
26 = 64. The remainder after 64 is divided by 7 is 1, so m could be 2. Leave E.
We’re down to B and E. Now we just need to check another value of n. Say n = 3.
33 = 27. The remainder after 27 is divided by 7 is 6, so m cannot be 3. Cross out B. The answer must be E.
Now, the way to prove that the sixth power of any legal value of n leaves a remainder of 1 after division by 7 is not too onerous. What we need to recognize is that we can apply powers to remainders.
The possible remainders after we divide a non-multiple of 7 by 7 are {1, 2, 3, 4, 5, 6}.
When we square those numbers (for m = 2), we get {1, 4, 9, 16, 25, 36}. Now we take remainders after dividing by 7; we get {1, 4, 2, 2, 4, 1}.
We can multiply that set by the {1, 2, 3, 4, 5, 6} set to get the cubes (m = 3) and get {1, 1, 6, 1, 6, 6} after we take remainders.
Continuing, we don’t get {1, 1, 1, 1, 1, 1} until we hit m = 6.
The correct answer is E.
