Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.
Problem 2
Find the remainder $r$, $1 \le r \le 13$, when $2^{1985}$ is divided by $13$.
Hints
Hint #1
You don’t actually need to compute this directly; can you reduce the problem?
Solution
Open to see the solution; try solving it first or see the hints above!
Let’s consider the ring of integers $\mathbb{Z}_{13}$, in which all arithmetic is done $\mod 13$.
Computing $2^{1985} \mod 13$ can be done over the full set of integers $\mathbb{Z}$ (which is computationally intensive), or it can be done over $\mathbb{Z}_{13}$, which may have a pattern, or a cycle, which may simplify finding the answer.
Let’s compute the first few values of $2^n \mod 13$ in $\mathbb{Z}_{13}$:
$$ \newcommand\redbx[1]{\fcolorbox{red}{none}{$ \displaystyle{ #1 } $}} \newcommand\blubx[1]{\fcolorbox{blue}{none}{$ \displaystyle{ #1 } $}} \begin{align*} 2^0 & \equiv \blubx{1} \mod 13 \\ 2^1 & \equiv \redbx{2} \mod 13 \\ 2^2 & \equiv 4 \mod 13 \\ 2^3 & \equiv 8 \mod 13 \\ 2^4 & \equiv 3 \mod 13 \\ 2^5 & \equiv 6 \mod 13 \\ 2^6 & \equiv 12 \mod 13 \\ 2^7 & \equiv 24 \mod 13 \equiv 11 \mod 13 \\ 2^8 & \equiv 22 \mod 13 \equiv 9 \mod 13 \\ 2^9 & \equiv 18 \mod 13 \equiv 5 \mod 13 \\ 2^{10} & \equiv 10 \mod 13 \\ 2^{11} & \equiv 20 \mod 13 \equiv 7 \mod 13 \\ 2^{12} & \equiv 14 \mod 13 \equiv \blubx{1} \mod 13 \\ 2^{13} & \equiv \redbx{2} \mod 13 \\ \end{align*} $$Thus, we see that there’s a cycle of size $12$ so we need to compute $1985 \mod 12 = 5$ so $2^{1985} \mod 13 = 2^5 \mod 13 = \boxed{6}$. $\qquad \blacksquare$
Verification
The verification also includes the answer; try solving it furst or see the hints above!
We can verify this answer directly via the Python REPL, because Python supports arbitrarily-sized integer arithmetic:
$ python
>>> (2 ** 1985) % 13
6
or as a one-liner directly:
$ python -c "print((2 ** 1985) % 13)"
6