2006 iTest Problems/Problem 6

Problem

What is the remainder when $2^{2006}$ is divided by 7?

$\mathrm{(A)}\,0\quad\mathrm{(B)}\,1\quad\mathrm{(C)}\,2\quad\mathrm{(D)}\,3\quad\mathrm{(E)}\,4\quad\mathrm{(F)}\,5$

Solution

Notice that $2^3 = 8$, and the remainder when divided by 7 is 1. In other words, $2^3 \equiv 1 \pmod{7}$. Thus, $2^{3n} \equiv (2^3)^n \equiv 1^n \equiv 1 \pmod{7}$.

Since $2006 = 3 \cdot 668 + 2$, we find that $2^{2006} \equiv 2^2 \equiv 4 \pmod{7}$, so the remainder when $2^{2006}$ gets divided by 7 is $\boxed{\textbf{(E) } 4}$.

See Also

2006 iTest (Problems, Answer Key)
Preceded by:
Problem 5
Followed by:
Problem 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 U1 U2 U3 U4 U5 U6 U7 U8 U9 U10