HMMT Spring Guts Round, 2021

Solution:

Note that $f(a, b)$ is the remainder of $b$ when divided by $a$. If $a>b$ then $f(a, b)$ is exactly $b \bmod a$. If instead $a \leq b$, our "algorithm" doubles our $a$ by $n$ times until we have $a \times 2^{n}>b$. At this point, we subtract $a^{\overline{2 n-1}}$ from $f\left(a \cdot 2^{n}, b\right)$ and iterate back down until we get $a>b-a \cdot k>0$ and $f(a, b)=b-a \cdot k$ for some positive integer $k$. This expression is equivalent to $b-a \cdot k \bmod a$, or $b \bmod a$.

Thus, we want to compute $3^{2021} \bmod 1000$. This is equal to $3 \bmod 8$ and $78 \bmod 125$. By CRT, this implies that the answer is 203.