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

by starrystarryday   Last Updated May 22, 2020 23:20 PM

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?

Tags :

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$$?

J. W. Tanner
May 22, 2020 23:13 PM