3
$\begingroup$

I wasn't actually taught about cubic congruences equation and was managing with quadratic congruences until I was hit with this: $$x^3 \equiv 53 (\text{ mod } 120)$$ Effort: I tried deconstructing it into a system of congruence equation assuming that there is several congruences towards prime decomposition of $120 = 3\cdot 5\cdot 8$ but ended up using Chinese remainder theorem to solve it into $53$ (which was quite silly).

I also tried putting it into $x^3-53 \equiv 0 (\text{ mod } 120)$ and use Special Algebra Expansions $a^3-b^3$ or $(a-b)^3$ but got stuck. A few useful hints would be appreciated. Thank you.

$\endgroup$
3
  • $\begingroup$ I would start looking for an $n$ such that $53^n \equiv 1 \pmod{120}$ $\endgroup$
    – Doug M
    Mar 13, 2018 at 22:07
  • $\begingroup$ What was wrong with using the Chinese remainder theorem? $\endgroup$
    – Ward Beullens
    Mar 13, 2018 at 22:08
  • $\begingroup$ @WardBeullens i think i used 53 to mod every prime decomposition then work its way back to 53 $\endgroup$
    – Liam
    Mar 13, 2018 at 22:11

2 Answers 2

Reset to default
1
$\begingroup$

Using CRT:

  • $x^3\equiv_3 53\equiv_3 2\Rightarrow x\equiv_3 2$
  • $x^3\equiv_5 53\equiv_5 3\Rightarrow x\equiv_5 2$
  • $x^3\equiv_8 53\equiv_8 5\Rightarrow x\equiv_8 5$

This implies that $x\equiv_{15}2$ and $x\equiv_8 5$, which is the same as saying $x-2\equiv_{15}0$ and $x-2\equiv_8 3$. The first number $8k+3$ that is divisible by $15$ is $75$, so $$x\equiv_{120}77$$

$\endgroup$
2
  • $\begingroup$ how is it that when $x^3\equiv_3 2\Rightarrow x\equiv_3 2$, i didn't know CRT had that $\endgroup$
    – Liam
    Mar 13, 2018 at 22:29
  • $\begingroup$ $2^3\equiv_3 2$, it is perhaps easier to see if you replace $2$ with $-1\equiv_3 2$. $\endgroup$
    – cansomeonehelpmeout
    Mar 13, 2018 at 22:29
1
$\begingroup$

$$\text{Just solve } \mkern 100mu\begin{cases}x^3\equiv -1\mod 3,\\x^3\equiv\phantom{-}3\mod 5,\\x^3\equiv-3\mod 8,\end{cases}\qquad\text{then lift the solutions mod. $120$.}$$ This supposes each elementary equation has solutions.

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