Track / Stage 3 / 204 of 260 #204 of 1964

Problem 204

AMC 10/12, early questions

Number theory Difficulty 3.7 Find the answer South African Mathematics Olympiad Second Round · South Africa

What is the remainder when $2^{2016}$ is divided by $13$ ?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

(We do this by inspection, by trying out some values until we can see the pattern.) Draw up a list of the remainders left by the powers of $2$ after division by $13$ :

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12
$2^n \bmod 13$	1	2	4	8	3	6	12	11	9	5	10	7	1

We see that the remainders repeat every

12

terms, since

2^{12} \equiv 1 \pmod{13}

Now, $2016 \div 12 = 168$ with remainder $0$ , so $2016 = 12 \times 168 + 0$ .

Therefore,
$2^{2016} \equiv 2^0 \equiv 1 \pmod{13}.$

So the remainder is $1$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.