Solving $x^{17}=17$ modulo 23 Solve $x^{17}=17$ modulo 23.
I have tried brute force (the only solution is 10), but I want to ask if there are any literature or method solving this kind of question, particularly like $x^p=a$ modulo $q$.
 A: Suppose $x^{17} \equiv 17 \mod 23$ ,then $x^{17k} \equiv 17^k \mod 23$ for all $k \geq 1$. Now, pick $k$ such that $17k \equiv 1 \mod 22$, which is easily seen to be $k= 13$.(Easily, in that we just keep trying $22l+1$ for divisibility by $17$, and its easy to keep adding $22$ and checking divisibility, rather than go for Euclid's method here). 
It follows that $x^{17 \times 13} \equiv 17^{13} \mod 22$, but then $x^{17 \times 13} \equiv x^{22 \times 10 + 1} \equiv x \mod 23$ by Fermat's little theorem, so we get $x  \equiv 17^{13} \mod 23$.
It is a question of calculating $17^{13} \mod 23$, one we shall do by repeated squaring. 
$17^2 = 289 \equiv 13 \mod 23$, $17^4 \equiv 169 \equiv 8 \mod 23$, $17^8 \equiv 64 \equiv 18 \mod 23$.
So , the answer is : since $13 = 8+4+1$, we have $18 \times 8 \times 17 \equiv -5 \times -6 \times 8 \equiv 240 \equiv 10 \mod 23$.
EDIT : If you want to solve $x^3 \equiv 3 \mod 73$, then this has a complication, in that there is no $k$ such that $3k \equiv 1 \mod 72$, so we cannot raise our congruence to such a power and get a positive result.
What we cannot even say, is if there is a solution or not, and if it is even unique. Thankfully, we can do a little "small multiples and small cubes" introspection, and then it's not difficult to see that $-6$ is actually a solution, since $(-6)^3 = -216$ and $71 \times -3 = -213$. Of course, this is only a heuristic, because not every problem will have a small solution, or even a solution for that matter.
I cannot find out if there are other solutions without being given enough time, really.
In general, I think this problem is called the discrete logarithm problem.From what I know, this belongs(in general) to a hard class of problems in computer science. In fact, there are algorithms (usually for making codes) which make use of the fact that this problem is hard. So I personally think that this problem is to be cracked case-by-case : you have to look at the problem given to you, and see what is special about the numbers given i.e. is the modulus prime, is the exponent co-prime to the modulus minus one, etc. If anybody has a general solution to this problem which takes short time, I expect it to be a big thing.
