mod 2018

Relevant wiki: Euler's Theorem

Let $N = 2^{2018}-20$ . We need to find $N \bmod 2018$ . Since $\gcd(2,20,2018) \ne 1$ , we have to consider the prime factors 2 and 1009 of 2018 separately using the Chinese remainder theorem .

Consider factor 2: $2^{2018}-20 \equiv 0 \text{ (mod 2)}$

Consider factor 1009:

$\begin{aligned} N & \equiv 2^{\color{#3D99F6} 2018 \bmod \phi(1009)} - 20 \text{ (mod 1009)} & \small \color{#3D99F6} \text{Since }\gcd(2,1009) = 1 \text{, Euler's theorem applies.} \\ & \equiv 2^{\color{#3D99F6} 2018 \bmod 1008} - 20 \text{ (mod 1009)} & \small \color{#3D99F6} \text{Euler's totient function }\phi(1009) = 1008 \\ & \equiv 2^2 - 20 \text{ (mod 1009)} \\ & \equiv - 16 \text{ (mod 1009)} \\ & \equiv 993 \text{ (mod 1009)} \end{aligned}$

This implies that:

$\begin{aligned} N & \equiv 1009n+993 & \small \color{#3D99F6} \text{where }n \text{ is an integer.} \\ \implies 1009n + 993 & \equiv 0 \text{ (mod 2)} \\ n +1 & \equiv 0 \text{ (mod 2)} \\ \implies n & \equiv - 1 \\ \implies N & \equiv 1009(-1) + 993 \text{ (mod 2018)} \\ & \equiv - 16 \text{ (mod 2018)} \\ & \equiv \boxed{2002} \text{ (mod 2018)} \end{aligned}$