South African Mathematics Olympiad Second Round

(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\mathrm{mod}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(\mathrm{mod}13)$.

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

Therefore, $$2^{2016}\equiv 2^0\equiv 1(\mathrm{mod}13).$$

So the remainder is $1$.