Find $x$ such that $x^{677} ≡ 3 \mod 2020$.

Question

I have been reviewing number theory questions and there is one problem I am stuck on.

Find $x$ such that $x^{677} ≡ 3 \mod 2020$.

My approach was to start by applying Euler’s Theorem. I know that $\phi(2020) = 800$, but I don’t know if this is very useful... How should I proceed?

Answer 1

As suggested in the comment by lulu, $2020=2^2\times5\times101$,

so solve the problem mod $4,5,$ and $101$ separately,

and then use the Chinese remainder theorem.

I.e., $x\equiv3\bmod4$ , $x\equiv3\bmod 5$, and $x^{77}\equiv3\bmod101$.

$77\times13=1001\equiv1\bmod100$, so $x\equiv3^{13}\equiv38\bmod101$.

So we have $x\equiv3\bmod20$ and $x\equiv38\bmod101$.

Can you now show $x\equiv543\bmod2020$?