Calculating Modulo of powers

Question

I am trying to solve 14^20192019 mod 60 without using a calculator.

To do this, I am using the logarithm: a = b^x -> x = log_ba => 14^20192019 mod 60 => lg(14) a = 2019²⁰¹⁹ mod 60

a = 14^20192019 mod 60

2019²⁰¹⁹ mod 60

The problem is that gcd(2019, 60) = 3 and NOT 1. So I can't use Euler's Theorem.

How do I solve this?

Answer 1

Using Chinese Remainder Theorem with $60 = 4 \times 15$. Note that $\gcd(4,15) = 1$.

• $$14^{2019^{2019}} \equiv 2^{2019^{2019}} \equiv 0 \pmod{4}$$
• $$14^{2019^{2019}} \equiv (-1)^{2019^{2019}} \equiv -1 \pmod{15}$$

Therefore, $$14^{2019^{2019}} \equiv 44 \pmod{60}.$$

Answer 2

Hint : $60 = 3 \times 4 \times 5$, so we can use Chinese remainder theorem (without this, the problem is difficult, since $60$ is a very large modulus, and $14^x$ is difficult to evaluate mod $60$ to find patterns).

Clearly, if $L = 14^{\left(2019^{2019}\right)}$ then $L \equiv 0 \mod 4$. Since $14 \equiv -1 \mod 3$ and $14 \equiv -1 \mod 5$, we have that $L \equiv (-1)^{\left(2019^{2019}\right)} = -1$ both mod $3$ and mod $5$.

Thus,$L \equiv 0 \mod 4, L \equiv -1 \mod 3, L \equiv -1 \mod 5$. By CRT, this determines $L \mod 60$, an it is not difficult to see that $L \equiv 44 \mod 60$.

NOTE : Below $60 = 4 \times 15$ has been used : this is also fine as CRT just requires a product of coprimes.