How to solve $x^3 = 3$ (mod $257)$ while knowing that $3$ is a primitive root mod $257$?

Question

We were given the hint that $3$ is a primitive root of unity, meaning that for all $y$ such that $\gcd(y,257)=1$, we can find a power $k$ such that $3^k \equiv y$ (mod $257)$. But I have no idea how to deal with the third power in my equation.

Could you please help me with this problem?

Answer 1

Let $x < 257$, then we know that $\gcd(x,257) = 1$. So there exist a $k$ such that $x = 3^k \mod 257$. Then $x^{3} = 3^{3k} \mod 257 =3$.

Thus, $3^{3k-1} = 1 \mod 257$.

Since $257$ is prime and $3$ is primitive root of it, we should have $3k = 1 \mod 256$. We can easily find that $k = 171$, so $x = 3^{171} = 147 \mod 257$

Answer 2

If $3$ is a primitive root then $x \equiv 3^k$ or some integer $k$. And as $257$ is prime $3^{256} \equiv 1$ and $3^m \equiv 3 \pmod{257}\iff m\equiv 1 \pmod {256}$.

So we have $x^3 \equiv (3^k)^3 \equiv 3^{3k} \equiv 3 \pmod {257}$ so

$3k \equiv 1 \pmod {256}$. So there is an $m$ so that $3k = 1 + 256m$. But as $256\equiv 1 \pmod 3$ $m = 2$ will do it. $3k \equiv 1 + 256\cdot 2\equiv 513 \pmod {256}$ and $k \equiv 171\pmod{256}$.

And $x \equiv 3^{171}\pmod {257}$.

Answer 3

$3^{256}\equiv 1 \bmod 257$

$\Rightarrow 3^{128}\equiv 1\bmod 257$

multiplying both sides by 3 we get:

$3^{129=3\times 43}=(3^{43})^3\equiv 3\bmod 257$

$\Rightarrow x=3^{43}$