What is the remainder when you divide 2^200 by 7?

[manochsa]

This problem is taken from the MGMAT 7/13/09 Challenge Set. Could you explain the reasoning behind the boldfaced type in the problem copied below? Why would it be wrong for me to reason here that since 200 is a multiple of 5, I should work with the remainder or 2^5, which is 4 in this case? Or for that matter, that since 200 is a multiple of 4, I should work with the remainder of 2^4, which is 2? I've seen this type of problem before, dealing with powers of 12, in which the pattern repeated every four terms, and so we worked there with powers that were multiples of 4. Something tells me it has to do with the property a^m + a^n = a^m+n. Could you please elaborate for me? Thanks!

Question
What is the remainder when you divide 2^200 by 7?

(A) 1
(B) 2
(C) 3
(D) 4
(E) 5
Answer
We cannot compute 2^200 in anywhere near the time allotted, so we should look for a pattern in much simpler problems that we can scale up to 2^200.

The simpler problems we should solve are these:
What is the remainder when you divide 2 by 7?
What is the remainder when you divide 2^2 by 7?
What is the remainder when you divide 2^3 by 7?
What is the remainder when you divide 2^4 by 7?
... and so on with the powers of 2.

The answers follow this pattern:
2 divided by 7 leaves remainder 2.
2^2 (which equals 4) divided by 7 leaves remainder 4.
2^3 (which equals 8) divided by 7 leaves remainder 1.
2^4 (which equals 16) divided by 7 leaves remainder 2.
2^5 (which equals 32) divided by 7 leaves remainder 4.
2^6 (which equals 64) divided by 7 leaves remainder 1.

We should stop as soon as we notice that the cycle will repeat itself forever in this pattern: [2, 4, 1]. Every third remainder is the same. (From here on out, "remainder" always means "remainder after we divide by 7.") Since every third remainder is the same, we should look at the remainder when the power is a multiple of 3. The remainders of 2^3 and 2^6 are 1. Thus, the remainder of 2 raised to a power that is any multiple of 3 is 1.

Now, 200 is not a multiple of 3, but we can look for a multiple of 3 near 200. 201 is a multiple of 3 (its digits add to 3), so 2^201 has a remainder of 1. Finally, we notice that the remainder of 2200 must be one position earlier in the cycle than the remainder of 2^201. Since the cycle is [2, 4, 1], the remainder of 2^200 is 4.

The correct answer is D.

[Ben Ku]

This problem is taken from the MGMAT 7/13/09 Challenge Set. Could you explain the reasoning behind the boldfaced type in the problem copied below? Why would it be wrong for me to reason here that since 200 is a multiple of 5, I should work with the remainder or 2^5, which is 4 in this case? Something tells me it has to do with the property a^m + a^n = a^m+n. Could you please elaborate for me? Thanks!

You want to find the remainder when 2^200 is divided by 7, not 2^5 or 2^4.

Let's carry out your question. You really would re-state the question this way: What is the remainder when (2^5)^40 is divided by 7. [Using the rule that a^mn = (a^m)^n]. However, stating the question in this way does not really help you find the answer.

When approaching problems where you know that performing the actual computation is ridiculous, look for patterns.

[trapanister]

I would know in what chapter of the guides I have to see for this kind of problems with a large exponent and reminder.

I saw the chapter about reminder or divisibility, but nothing

sorry for the question, right now I started to study Gmat math :(

[tim]

The closest thing in our strategy guides appears to be chapter 1 of FDPs..