1322.11 – Giant Powers of 3

What is the remainder when $3^{2020}$ is divided by $13$ ?

Solution

There is a pattern to the remainders when powers of 3 are divided by 13:

\begin{aligned} \textbf{Power } & \textbf{ Remainder} \\ 3^1 = 3 & 3 &\\ 3^2 = 9 & 9 & \\ 3^3 = 27 & 1 & \text{ (!)} \\ 3^4 = 81 & 3 & \\ 3^5 = 243 & 9 & \\ 3^6 = 729 & 1 & \text{ (!!)} \end{aligned}

And so it goes. We observe that the remainder is $1$ when the exponent is a multiple of $3$ , $3$ when the exponent is $1$ more than a multiple of $3$ , and $9$ when the exponent is $2$ more than a multiple of $3$ . Now, $2020 = 3 \times 673 + 1$ , i.e., $2020$ is $1$ more than a multiple of $3$ . So $3^{2020}$ goes with $3^1$ and $3^4$ . The remainder is $3$ .