   SEARCH HOME Math Central Quandaries & Queries  What is the remainder when 3^2007 is divided by seven?? Hi Chris,

This type of problem requires an approach I like to call "doing a simpler but related problem". Often a pattern can be found in examining certain cases of these simpler problems.

For example, you want to know the remainder when 3^2007 is divided by 7. Why not start by examining what remainders result when 3^1 is divided by 7, then 3^2, then 3^3 and so on. This is what I mean by "simpler but related".

Chart:
31 = 3, 3/7 gives a remainder of 3
32 = 9, 9/7 gives a remainder of 2
33 = 27, 27/7 gives a remainder of 6 no pattern yet, keep going!
34 = 81, 81/7 gives a remainder of 4
35 = 243, 243/7 gives a remainder of 5 still no pattern, keep going...
36 = 729, 729/7 gives a remainder of 1
37 = 2187, 2187/7 gives a remainder of 3
38 = 6561, 6561/7 gives a remainder of 2

Notice how the last two remainders have already appeared once before. Moreover, they
already appeared in that same order. We can conjecture that now 39 should give us a remainder of 6 when divided by 7. You can verify that this is correct.

Now we can see that the remainders will cycle through 3, 2, 6, 4, 5, 1 in this order, over and over.

The trick now is to determine where 2007 will fall in this cycle. Since there are only 6 possible remainders we need to somehow relate the exponent on 3 with its corresponding remainder.

Note:
Exponents of 1 and 7 yielded a remainder of 3. There is a difference of 6 between 1 and 7. The next exponent to yield a remainder of 3 should be 13 (and then 19 and then 25, etc.) 1, 7, 19, 25, etc are all 1 more than a multiple of 6. If 2007 is 1 more than a multiple of 6 then the remainder when 3^2007 is divided by 7 would be 3.

But 2007 = 6(334) + 3 (or 3 more than a multiple of 6).

Which remainder occurs when the exponent is 3 more than a multiple of 6?

That remainder would be 6!

This approach of "simpler but related" can be used in many of these number type problems that involve large numbers your calculator can't deal with.

Hope this helps,
Leeanne     Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.