5

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?

Bernard
  • 175,478
trolley
  • 815

2 Answers2

5

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$

Robert Israel
  • 448,999
  • 1
    I don't understand few thing here. 1. When you wrote $99x^2-1$ you probably got $4x^2-1 \equiv 4(5y+2)^2-1 \equiv 80y+15$ and how you got from this $5y+20 \equiv 0$? 2. For example, you got that $y \equiv 1$ and if I understood correctly, you just put that to $x\equiv 2+5\cdot 1 $, yes? – trolley May 10 '19 at 17:09
  • $99 (2 + 5 y)^2 - 1 \equiv (-1)(4 + 20 y + 25 y^2) - 1 \equiv 5 y + 20 \mod 25$. – Robert Israel May 10 '19 at 17:23
  • Ok, currently I understand case when I have for example $a^n$. Then I consider $a$, $a^2$ etc. But how to deal when I do modulo operations on something which is not just power of other number? For example $150 = 5^2\cdot2\cdot3$ – trolley May 10 '19 at 18:07
  • Do $5^2$, $2$, $3$ separately and combine using Chinese Remainder Theorem. – Robert Israel May 11 '19 at 00:06
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$.

Anurag A
  • 41,067