Solving a congruence $x^{17} \equiv 243 \pmod{257}$ I'm trying to solve the following congruence:
$x^{17} \equiv 243 \pmod{257}$
I have worked out that the $\gcd(243,257)=1$ and that $243=3^5$
So $x^{17} \equiv 3^5 \pmod{257}$
and I don't really understand what to do next.
 A: We want to solve $x^{17} \equiv 3^5 \pmod{257}$. Raise both sides to the power $15$ to get
$$x^{255} \equiv 3^{75} \pmod{257},$$
or equivalently $x^{-1} \equiv 3^{75} \pmod {257}$. Thus $x \equiv 3^{-75} \equiv 28 \pmod{257}$.
A: Since $257$ is a prime number by Fermat's little theorem $a^{256}\equiv 1\mod 257\ \forall a, 257\not|a$ Now, let us find if there is a solution of the form $3^y$. If there is then the equation will become $$3^{17y-5}\equiv 1\mod 257\Rightarrow 256|17y-5$$ $y=181$ is a solution to this. So $x=3^{181}$ is one solution and all the solutions of the form $3^y$ can be obtained by solving the linear Diphontaine equation $$17y-256z=5$$. 
Now, if there are solutions of the form $3^ya$ where $a$ does not contain $3$ as a prime factor then the equation will read as $$a^{17}3^{17y-5}\equiv 1\mod 257$$
But I'm not sure how to solve this.
A: We have the following facts: $\gcd(3,257)=1,\,$ $\varphi(257)=256,\,$ and 3 is a primitive root mod 257. From the first two we know, see e.g. When is $a^n \equiv a^{(n \;\bmod \; \varphi(m))} \pmod m$ valid,
$$3^n \equiv 3^{(n \;\bmod \; \varphi(257))} \equiv 3^{(n \;\bmod \; 256)}  \pmod {257}$$
Make the Ansatz $x=3^y$, then
$$x^{17}\equiv 3^5 \pmod {257} \iff 3^{17y-5}\equiv 1 \equiv 3^0 \pmod {257}$$
Now solve $17y-5\equiv 0 \pmod {256}\,$. The multiplicative inverse is $17^{-1} \equiv 241 \pmod {256}\,$ and $y=5\times 241 \equiv 181 \pmod {256}.\,$ Therefore  a solution is$$x=3^y=3^{181} \equiv 28 \pmod {257}.$$
Now you can check that $28^{17} \equiv 243 \pmod {257}.$
