Solving $3x^3\equiv 7\pmod{925}$

Question

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?

Answer 1

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.

Answer 2

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$