Solving $x^{17}=17$ modulo 23

Question

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$.

Answer 1

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.

Answer 2

By Fermat's Little Theorem $x^{22} \equiv 1 \mod 23$

So if $17*m \equiv 1 \mod 22$ then

So $x^{17} \equiv 17 \mod 23 \implies$

$(x^{17m} \equiv x \equiv 17^m \mod 23 $

So let's solve $17*m \equiv 1 \mod 22$.

We use Euclid's Algorithm:

$22 = 17 + 5$

$17 = 3*5 + 2$

$5 = 2*2 + 1$

$1 = 5 - 2*2=$

$(22-17) - 2(17- 3*5) = (22-17) - 2(17 - 3(22 - 17)) = 7*22 - 9*17$

So $7*22 - 9 *17 1$ so $-9*17 \equiv 1\mod 22$

So $13*17 \equiv 1 \mod 22$.

So $x^17\equiv 17 \mod 23 \implies$

$(x^{17})^{13} \equiv 17^{13} \mod 23$

$ x\equiv 17^{13} \mod 23$

$17^{22} \equiv 1 \mod 23$ so $17^{11} \equiv \pm 1 \mod 23$ and $17^{13} \equiv \pm 17^2 \mod 23$.

$17^2 \equiv (-6)^2 \equiv 36 \equiv 13 \mod 23$

$17^4 \equiv 13^2 \equiv (-10)^2 \equiv 100 \equiv 8 \mod 23$

$17^8 \equiv 8^2 \equiv 64 \equiv 18 \mod 23$

$17^{12} \equiv 8*18 \equiv 144 \equiv 6 \equiv -17 \mod 23$.

So $17^{11} \equiv -1 \mod 23$ after all.

So $17^{13}\equiv 17^{11}*17^2 \equiv -13 \equiv 10 \mod 23$.

So $x^17 \equiv 17 \mod 23 \implies x\equiv 10 \mod 23$