5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ try $$x=32$$ or $$x=93$$ $\endgroup$ – Dr. Sonnhard Graubner May 10 at 16:40
  • 2
    $\begingroup$ Ok, both of them are okay, but how you got that? @Dr.SonnhardGraubner $\endgroup$ – trolley May 10 at 16:44
  • 4
    $\begingroup$ @Dr.SonnhardGraubner The answer on its own is often worthless. People aren't here because they want questions answered (or, at least, hopefully they aren't). This is one of the times where an answer post preferably should take more than a minute to write. $\endgroup$ – Arthur May 10 at 16:46
  • $\begingroup$ Euler's theorem can be applied only if $x$ is not divisible by $5$. $\endgroup$ – Bernard May 10 at 16:55
  • $\begingroup$ indeed, I haven't checked that case... without this transform exercise is getting much harder... $\endgroup$ – trolley May 10 at 17:10
5
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – trolley May 10 at 17:09
  • $\begingroup$ $99 (2 + 5 y)^2 - 1 \equiv (-1)(4 + 20 y + 25 y^2) - 1 \equiv 5 y + 20 \mod 25$. $\endgroup$ – Robert Israel May 10 at 17:23
  • $\begingroup$ 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$ $\endgroup$ – trolley May 10 at 18:07
  • $\begingroup$ Do $5^2$, $2$, $3$ separately and combine using Chinese Remainder Theorem. $\endgroup$ – Robert Israel May 11 at 0:06
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.