Back to problem set

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 rr, 1≤r≤131 \le r \le 13, when 219852^{1985} is divided by 1313.

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 Z13\mathbb{Z}_{13}, in which all arithmetic is done mod  13\mod 13.

Computing 21985mod  132^{1985} \mod 13 can be done over the full set of integers Z\mathbb{Z} (which is computationally intensive), or it can be done over Z13\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 2nmod  132^n \mod 13 in Z13\mathbb{Z}_{13}:

20≡1mod  1321≡2mod  1322≡4mod  1323≡8mod  1324≡3mod  1325≡6mod  1326≡12mod  1327≡24mod  13≡11mod  1328≡22mod  13≡9mod  1329≡18mod  13≡5mod  13210≡10mod  13211≡20mod  13≡7mod  13212≡14mod  13≡1mod  13213≡2mod  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 1212 so we need to compute 1985mod  12=51985 \mod 12 = 5 so 21985mod  13=25mod  13=62^{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