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?

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

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

Related Questions

Function that describes certain modulo function values

Updated October 22, 2017 20:20 PM

A simple modulo arithmetic problem

Updated July 29, 2018 23:20 PM

An elementary number theory problem

Updated August 19, 2017 08:20 AM