Solve $99x^2 \equiv 1 \mod 125$

Question

Solve $$x^{98} \equiv 99 \mod 125$$

Is there any easy way to solve equations like that? My observation is that from Euler's theorem we know that $$ x^{100} \equiv 1 \mod 125 $$ so $$x^{98} \equiv 99 \mod 125 \\ x^{100} \equiv 99x^2 \mod 125 \\ 99x^2 \equiv 1 \mod 125$$ but what is general method how to deal with equations like that?

Answer 1

Start mod $5$, and then lift...

$$99 x^2 \equiv 4 x^2 \equiv (2x)^2 \equiv 1 \mod 5$$ so $2 x \equiv \pm 1 \mod 5$, i.e. $x \equiv 2$ or $3 \mod 5$.

If $x \equiv 2 \mod 5$, $x \equiv 2 + 5 y \mod 25$, and then $$ 99 x^2 - 1 \equiv 5 y + 20 \equiv 0 \mod 25$$ $$ y + 4 \equiv 0 \mod 5$$ $$ y \equiv 1 \mod 5$$ So now $x \equiv 2 + 5 + 25 z \equiv 7 + 25 z \mod 125$, and then $$ 99 x^2 - 1 \equiv 25 z + 100 \equiv 0 \mod 125$$ $$ z + 4 \equiv 0 \mod 5$$ $$ z \equiv 1 \mod 5$$ Thus one solution is $x \equiv 2 + 5 + 25 \equiv 32 \mod 125$

Answer 2

Using Euclid or similar methods, you can get $24$ is the inverse of $99$ mod $125$. Thus \begin{align*} 99x^2 & \equiv 1 \pmod{125}\\ x^2 & \equiv 24 \pmod{125}. \end{align*}

For this to have a solution we should also have $x^2 \equiv 24 \equiv 4 \pmod{5}$. The last congruence has two solutions: $x=2 \pmod{5}$ and $x \equiv 3 \pmod{5}$. Now these can be "lifted" to (see Hensel's lifting lemma) solutions modulo $5^k$.