3
$\begingroup$

I am trying to solve $3x^3\equiv 7\pmod{925}$.

I thought of using brute force, but $925$ is too big for that.

I also tried raising both sides of the equation to the power of $3$, but it didn't help.

How can I solve it?

$\endgroup$
  • $\begingroup$ Hint: $3^{-1}\pmod{925}$ exists, and shouldn't be too difficult to find. $\endgroup$ – abiessu May 22 '15 at 15:28
  • $\begingroup$ i got $114,189,289$ $\endgroup$ – Dr. Sonnhard Graubner May 22 '15 at 15:37
  • $\begingroup$ so using $3^{-1}$ i got $x^3 \equiv 626 \pmod {925}$ but what to do from here? $\endgroup$ – user2993422 Jun 23 '15 at 22:51
5
$\begingroup$

With these, it's often easier to consider the problem after breaking the moduli down and then recombining the results using the Chinese Remainder Theorem.

So we consider the pair of problems $$ \begin{align} 3x^3 &\equiv 7 \pmod {37}\\ 3x^3 &\equiv 7 \pmod {25}. \end{align}$$

In the first, it's easy to check that the inverse of $3$ mod $37$ is $25$ (as $3 \cdot 25 = 75 = 1 + 2\cdot 37$), so multiplying through by $25$, we get $$x^3 \equiv 27 \pmod {37}.$$

This yields the obvious solution $x \equiv 3 \pmod {37}$. But we can find two more. In particular, since $3^3 \equiv 27 \pmod {37}$, Fermat's Little Theorem gives us that $3^{3 + 36} = 3^{13 \cdot 3} \equiv 27 \pmod {37}$ and $3^{3 + 72} = 3^{25 \cdot 3} \equiv 27 \pmod{37}$. So we have the three solutions $$3, 3^{13} \equiv 30, 3^{25} \equiv 4 \pmod{37}.$$

In the second, it's easy to check that the inverse of $3 \pmod {25}$ is $17$ (as $3\cdot 17 = 1 + 2\cdot 25$), so multiplying by $17$ we get $$ x^3 \equiv 19 \pmod {25}.$$ There is no obvious solution here. If we note this also means that $$ x^3 \equiv 4 \pmod 5,$$ then we can quickly check by hand that the only solution mod $5$ is $4$. This at least indicates that mod $25$, we only need to check $4,9,14,19,24$. A few quick pen strokes later, we can conclude that $$x \equiv 14 \pmod {25}$$ is the only solution here.

Now we patch these together using the Chinese Remainder Theorem. We have three choices mod $37$ and one choice mod $25$, so we will get three answers overall. Executing the Chinese Remainder Theorem reveals the three answers to be

$$ 114, 189, 289,$$

as claimed above. $\diamondsuit$

$\endgroup$
1
$\begingroup$

Notice that $925=37*5^2$. From here you can deduce that $x\equiv4\pmod 5$ and $x\equiv3\pmod{37}$. The first number which satisfies both equalities is $114$, which is as well the first solution to the equation.

$\endgroup$
  • $\begingroup$ but then $189,289$ are not the solutions as @Dr. Sonnhard Graubner wrote. $\endgroup$ – sam May 22 '15 at 16:08
  • $\begingroup$ @sam, they are, they are just not the first solution. $\endgroup$ – kleineg May 22 '15 at 17:24
  • $\begingroup$ how do you get to the rest of the solutions from here? $\endgroup$ – user2993422 Jun 23 '15 at 22:52

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.