GGMAT760 wrote:

What is the remainder when 2^86 is divided by 9?

(A) 1

(B) 2

(C) 3

(D) 4

(E) 8

Find the cyclicity of the

remainders. The units digit cyclicity approach works every time only when the divisor is 2, 5, or 10People who used units digits only in this question got lucky.

Here is one problem in which units digit cyclicity does NOT give the right answer.

Cyclicity of remaindersIncrease 2, power by power. Divide each number by 9 and find the remainder. Continue until you see a repeating pattern.

\(2^1=2\), and \(\frac{2}{9}=0,\) Remainder 2

\(2^2=4\), and \(\frac{4}{9}=0\) Remainder 4

\(2^3=8\), and \(\frac{8}{9}=0\) Remainder 8

\(2^4=16\), and \(\frac{16}{9}=1\) Remainder 7

\(2^5=32\), and \(\frac{32}{9}=3\) Remainder 5

\(2^6=64\), and \(\frac{64}{9}=7\) Remainder 1

\(2^7=128\), and \(\frac{128}{9}=14\) Remainder 2

\(2^8=256\), and \(\frac{256}{9}=28\) Remainder 4

\(2^9=512\), and \(\frac{512}{9}=56\) Remainder 8

The remainder pattern started to repeat after \(2^6\): (2, 4, 8, 7, 5, 1)

So the cyclicity of remainders is 6

Divide the exponent, 86, by cyclicity of 6.

If there is a remainder, that remainder number is the power of 2 that yields our answer.

(Example: exponent/cyclicity leaves a remainder of 5? We use 2\(^5\) to find our answer.)

If 86/6 leaves no remainder, then we find our answer at the end of the cycle, at 2\(^6.\)

\(\frac{86}{6}=14\) + remainder of 2, therefore:

\(2^{86}\), when divided by 9, will have the same remainder as \(2^2\)*

From above, when \(2^2\) is divided by 9,

the remainder is 4

Answer D

*Divide the exponent by the cycle number to figure out where, in the cycle of 6, the exponent would fall.

(6*14)=84, so 2\(^{84}\) would "hit" the cycle in the same position as 2\(^6\) (84 is a multiple of 6).

Start the cycle of 6 over.

2\(^{85}\) = same remainder as 2\(^1\), and

2\(^{86}\) = same remainder as 2\(^2\)

_________________

The only thing more dangerous than ignorance is arrogance.

-- Albert Einstein