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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .