Can you find the remainder when divided by 1990?

We need to find $2^{1990} \bmod 1990$ . Note that $1990 = 2\times 5 \times 199$ has three prime factors. Let us find the remainder using Chinese remainder theorem .

For prime factor 2: $\ 2^{1990} \equiv 0 \text{ (mod 2)}$

For prime factor 5: $\ 2^{1990} \equiv 4^{995} \equiv (5-1)^{995} \equiv - 1 \equiv 4 \text{ (mod 5)}$

For prime factor 199: Since $\gcd(2, 199) = 1$ , we can apply Euler's theorem . Note that Euler's totient function $\phi(199) = 199-1 = 198$ .

$\begin{aligned} 2^{1990} & \equiv 2^{1990 \bmod \phi(199)} \text{ (mod 199)} \\ & \equiv 2^{1990 \bmod 198} \text{ (mod 199)} \\ & \equiv 2^{10} \text{ (mod 199)} \end{aligned}$

Since $2^{10} \equiv 0 \text{ (mod 2)}$ and $2^{10} \equiv 4 \text{ (mod 5)}$ , implying that $2^{1990} \bmod 1990 = \boxed{2^{10} = 1024}$ .

wolfram