Christmas Questions: No. 4

Let $N=20172018^{2019}$ . We need to find $n = N \bmod 2019$ . We note that both the sum of digits of 20172018 and 2019 are divisible by 3. Therefore, the two numbers are multiples of 3 and are not coprime integers. We have to consider the factors of 2019 separately using the Chinese remainder theorem. $2019 = 3\times 673$ has only two prime factors.

Consider factor 3: $N = 20172018^{2019} \equiv 0 \text{ (mod 3)}$

Consider factor 673:

$\begin{aligned} N & \equiv 20172018^{\color{#3D99F6} 2019 \bmod \phi(673)} \text{ (mod 673)} & \small \color{#3D99F6} \text{Since }\gcd (20172018, 673) = 1 \text{, Euler's theorem applies.} \\ & \equiv 20172018^{\color{#3D99F6} 2019 \bmod 672} \text{ (mod 673)} & \small \color{#3D99F6} \text{Euler's totient function }\phi(673) =672 \\ & \equiv 20172018^{\color{#3D99F6} 3} \text{ (mod 673)} \\ & \equiv (20192019-20001)^3 \text{ (mod 673)} \\ & \equiv (-20001)^3 \text{ (mod 673)} \\ & \equiv (-20190+189)^3 \text{ (mod 673)} \\ & \equiv 189^3 \text{ (mod 673)} \\ & \equiv 189({\color{#3D99F6}35721}) \text{ (mod 673)} & \small \color{#3D99F6} 189^2 = 35721 \\ & \equiv 189({\color{#3D99F6}33650}+2071) \text{ (mod 673)} & \small \color{#3D99F6} 673 \times 50 = 33650 \\ & \equiv 189({\color{#3D99F6}52}) \text{ (mod 673)} & \small \color{#3D99F6} 2071-2019=52 \\ & \equiv 9828 \text{ (mod 673)} \\ & \equiv 406 \text{ (mod 673)} \end{aligned}$

Therefore,

$\begin{aligned} N & \equiv 673k + 406 & \small \color{#3D99F6} \text{where }k \text{ is an integer.} \\ \implies 673k + 406 & \equiv 0 \text{ (mod 3)} \\ k + 1 & \equiv 0 \text{ (mod 3)} \\ k & \equiv -1 \equiv 2 \text{ (mod 3)} \\ \implies N & \equiv 673k + 406 \\ & \equiv \boxed{1752} \text{ (mod 2019)} \end{aligned}$