RMO 2015! 12

Strategy: to determine $x^n$ mod $a$ , we split $a$ into (powers) of distinct primes and determine the value of $x^n$ mod each of these factors. For $a = 100$ , these factors are 4 and 25.

Moreover, for the value of $x^n$ mod $a$ we only need to know $n$ mod $\phi(a)$ , where $\phi$ is the totient function. For instance, for $x^n$ mod 25 we only need to know $n$ mod 20.

x = 17:

$A = 17^B \equiv 1$ mod 4. We wish to determine the remainder of $A = 17^B \equiv (-8)^B$ mod 25. Since $\phi(25) = 20$ , we know that we only need to know $B$ modulo 20.

Split 20 as $4\times 5$ . The exponent $B = 17^C \equiv 1$ mod 4. We need to find $B = 17^C \equiv 2^C$ mod 5. Since $\phi(5) = 4$ , we only need to know $C$ modulo 4. This is easy: $C = 17^D \equiv 1$ mod 4, so that $B \equiv 2^1 \equiv 2$ mod 5.

Now, since $B \equiv 2$ mod 5 and $B \equiv 1$ mod 4, we have $B \equiv 17 \equiv -3$ mod 20. This means that $A \equiv (-8)^{-3} = -(2^{-1})^9$ mod 25. Using $-12\cdot 2 = -24 \equiv 1$ mod 25, we have $2^{-1} = -12$ and $A \equiv 12^9 \equiv 3^3 \equiv 2$ mod 25.

Finally, from $A \equiv 1$ mod 4 and $A \equiv 2$ mod 25 it follows that $A \equiv \boxed{77}$ mod 100.

x = 18:

$A = 18^B \equiv 0$ mod 4, since certainly $B \geq 2$ . To determine $A = 18^B \equiv (-7)^B$ mod 25, we could again determine $B$ to modulo 20. However, since $7^2 = 49 \equiv -1$ mod 25, we only need to know $B$ to modulo 4. This is easy because 18 is even: $B = 18^C \equiv 0$ mod 4, and $A \equiv (-7)^0 = \equiv 1$ mod 25.

Since $A \equiv 0$ mod 4 and $A \equiv 1$ mod 25, we have $A \equiv \boxed{76}$ mod 100.

x = 19:

$A = 19^B \equiv (-1)^B \equiv -1$ mod 4; we use the fact that $B = 19^C$ is odd. Also, $A = 19^B \equiv (-6)^B$ mod 25. We will once again determine $B$ modulo 20. (Calculation of $19^n$ mod 25 shows that we really only need $B$ mod 10.)

Now $B = 19^C \equiv (-1)^C \equiv -1$ mod 4; likewise, $B = 19^C \equiv (-1)^C$ mod 5. It follows that $B \equiv -1$ mod 20. Therefore $A \equiv (-6)^{-1} \equiv 4$ mod 25. (We use $(-6)\cdot 4 = -24 \equiv 1$ mod 25.)

Combining $A\equiv -1$ mod 4 and $A \equiv 4$ mod 25, we easily find $A \equiv \boxed{79}$ mod 100.

x = 20: This is easy since $20^B \equiv \boxed{0}$ mod 100 for $B \geq 2$ .

Finally, Adding, we get $79 + 76 + 77 + 0 \equiv \boxed{32}$ mod 100.