Manhattan GMAT Challenge Problem of the Week - 13 June 2011

by Manhattan Prep, Jun 13, 2011

Here is a new Challenge Problem! If you want to win prizes, try entering our Challenge Problem Showdown. The more people that enter our challenge, the better the prizes!

Question

If [pmath]n^m[/pmath] leaves a remainder of 1 after division by 7 for all positive integers n that are not multiples of 7, then m could be equal to

(A) 2

(B) 3

(C) 4

(D) 5

(E) 6

Answer

One quick way to solve this problem is to picknumbers for n. Say n = 2 (which is legal, since 2 is not a multiple of 7). Then we just need to test [pmath]2^2[/pmath], [pmath]2^3[/pmath], [pmath]2^4[/pmath], [pmath]2^5[/pmath], and [pmath]2^6[/pmath]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).

[pmath]2^2[/pmath] = 4. The remainder after 4 is divided by 7 is 4, so m cannot be 2. Cross out A.

[pmath]2^3[/pmath] = 8. The remainder after 8 is divided by 7 is 1, so m could be 3. Leave B.

[pmath]2^4[/pmath] = 16. The remainder after 16 is divided by 7 is 2, so m cannot be 4. Cross out C.

[pmath]2^5[/pmath] = 32. The remainder after 32 is divided by 7 is 4, so m cannot be 5. Cross out D.

[pmath]2^6[/pmath] = 64. The remainder after 64 is divided by 7 is 1, so m could be 2. Leave E.

Were down to B and E. Now we just need to check another value of n Say n = 3.

[pmath]3^3[/pmath] = 27.

The remainder after 27 is divided by 7 is 6, so m cannot be 3. Cross out B. The answer must be E.

If we didn't pick numbers, 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. Wee need to recognize 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 dont get {1, 1, 1, 1, 1, 1} until we hit m = 6.

The correct answer is E.

Special Announcement: If you want to win prizes for answering our Challenge Problems, try entering our Challenge Problem Showdown. Each week, we draw a winner from all the correct answers. The winner receives a number of our our Strategy Guides. The more people enter, the better the prize. Provided the winner gives consent, we will post his or her name on our Facebook page.