Problem Solving

What is the remainder when 32^(32^32) is divided by 7?

A. 5
B. 4
C. 2
D. 0
E. 1

[spoiler]OA:B[/spoiler]

Remainder when 32^(32^32) OR (28+4)^(32^32) is divided by 7 is the same as remainder when 4^(32^32) is divided by 7. This is because all the terms in the expansion will be multiples of 7 except the last one, which is 4^(32^32).

Also 32^32 when divided by 3 gives remainder (-1)^32 OR 1=>32^32 = 3k+1

4^(32^32)= 4^(3k+1)by 7 = 4* (4^3)^k by 7 = 4*1 = 4 by 7.

Hence the required remainder is 4.

Alternate solution

Also if p is prime and N^(p-1) is divided by p, the remainder is 1 (as long as N is not a multiple of p). So, N^6 will always leave remainder 1 when divided by 7 (if N is not a multiple of 7). And so will N*6k, where k is a positive integer.

So, let's explore the remainder when 32^32 by 6 = 2^32 by 6= 2* (2^31 by 3) = 2 (2 by 3) = 4 when divided by 6
Now we have 4^(32^32) by 7 = 4^(6k+4) by 7= 4^4 by 7 (by using the consideration above)= 256 by 7 = 4 when divided by 7

Hence the required remainder is 4.

Since 32 / 7 has remainder 4, we can replace the base 32 with the base 4:

4^(32^32)

Now let's look for a pattern.

4 / 7 => remainder 4
4*4 / 7 => remainder 2
4*4*4 / 7 => remainder 1
4*4*4*4 / 7 => remainder 4

Aha! So the pattern repeats in a block of three: 4, 2, 1, 4, 2, 1, 4, 2, 1, ...

That means we can reduce the problem to "what's the remainder when our exponent is divided by 3"? If that remainder is 1, then OUR remainder is 4; if that remainder is 2, then OUR remainder is 2; if that remainder is 0, then OUR remainder is 1.

32 has a remainder of 2 when divided by 3, so we can use 2³² for our exponent. Looking for a pattern with powers of 2 divided by 3, we find

2 / 3 => remainder 2
4 / 3 => remainder 1
8 / 3 => remainder 2
16 / 3 => remainder 1

OK! That's easy. So if the number is 2^odd, it has remainder 2, and if it's 2^even, it has remainder 1.

2³² is 2^even, so it has remainder 1. That means we're raising our number to something with a remainder of 1 when divided by 3. In our first pattern, we saw that remainder 1 gave us a number with a remainder of 4, so we're done!

I should add that I seriously doubt a question like this would appear on the GMAT: the test does not expect this degree of familiarity with remainders. (The Indian CAT does, though.)