How to solve the congruence $x^{59} \equiv 604 \pmod{2013}$?

Question

$$x^{59} \equiv 604 \pmod{2013}$$

Could somebody give me any clue? I have no idea how to start.

I see that $59$ is prime.

Answer 1

Let $t$ be some integer such that $t^{59} \equiv 604 \pmod{2013}$; then, $t^{59} = 604+2013k$ for some integer $k$. Since $\gcd(604,2013) = 1$, Euclidean Algorithm tells us $\gcd(t^{59},2013)=1$ and thus $\gcd(t,2013)=1$. Thus, we can apply Euler's Theorem.

Note that $\varphi(2013) = 1200$ and $\gcd(1200,59) = 1$. By Bézout's Lemma, there exist integers $n,m$ such that $1200n+59m = 1$. Euler's Theorem says $t^{1200} \equiv 1 \pmod{2013}$, so $t^{1200n} \equiv 1 \pmod{2013}$.

$t^{59} \equiv 604 \pmod{2013}$

$t^{59m} \equiv 604^m \pmod{2013}$

$t^{59m} \equiv t^{59m}t^{1200n} \equiv t^{59m+1200n} \equiv t\equiv 604^m \pmod{2013}$

All you have to do is explicitly find $m$ using the Extended Euclidean Algorithm.

Answer 2

As $(604,2013)=1,x$ must be co-prime to $2013$

As $2013=3 \cdot 11 \cdot 61,$ using Carmichael Function,

$$x^{60}\equiv1\pmod{2013}$$

$$x^{59}\equiv604\pmod{2013}\implies x^{60}\equiv604x$$

So, we have $$604x\equiv1\pmod{2013}$$

Can you find $x$ using Euclid's Algorithm?