Competition problem — Number theory

Library / /5 of 20

Number theory Difficulty 3.7 AMC 10/12 Find the answer South Africa

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

Your answer

A number or a short expression. Spacing and $ signs are ignored.

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$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.