How to solve $x^3\equiv 10 \pmod{990}$?

How to solve $x^3\equiv 10\pmod{990}$?

It has 3 solutions: 10, 340, 670 (WolframAlpha).

Solutions Collecting From Web of "How to solve $x^3\equiv 10 \pmod{990}$?"

Hint: $$\begin{align}x^3 \equiv 10 \mod 9 \dot \, 11\dot\,10 \iff & x^3 \equiv 10 \mod 9 \equiv 1 \mod 9\\&x^3 \equiv 10 \mod 11 \equiv -1 \mod 11\\&x^3 \equiv 10 \mod 10\equiv 0 \mod 10\end{align} $$

Now observe that

$$x^3 \equiv 1 \mod 9 \iff x = 1,4,7 \iff x \equiv 1 \mod 3 \equiv 10 \mod 3\tag{1}$$

$$x^3 \equiv 0 \mod 10 \iff x \equiv 0 \mod 10 \equiv 10\mod 10\tag{2} $$

$$\begin{align} x^3 \equiv -1 \mod 11 &\iff x \equiv x^{22 -1 } \equiv (-1)^{7} \mod 11 \\&\iff x \equiv -1 \mod 11 \equiv 10 \mod 11\tag{3}\end{align}$$

Now we have that

$$x \equiv 10 \mod 330 \iff x -10 = 330\dot \, p $$

Taking $p = 0,1,2$ gives us $x = 10, 340, 680$.

We have
$$x^3 \equiv 10 \pmod{990} \implies x^3 = 990m + 10 = 10(99m+1)$$
This means $x=10l$. Hence, we need
$$100l^3 = 99m+1 \implies m \equiv 1\pmod{100}$$
Hence, $$x^3 = 10(99(100n+1)+1) = 10(9900n+100) = 1000(99n+1)$$
Hence, we need $99n+1$ to be a perfect cube. This means
$$y^3 \equiv 1\pmod{99} \implies y^3 \equiv 1\pmod9 \text{ and }y^3 \equiv 1\pmod{11}$$
This gives us
$$y \equiv 1,4,7\pmod9 \text{ and }y \equiv 1 \pmod{11} \implies y \equiv 1,34,67\pmod{99}$$
Hence,
$$x \equiv 10y \pmod{990} \equiv 10,340,670\pmod{990}$$

${\rm mod}\ \color{#c00}{11}\!:\ \overbrace{x^3 \equiv -1}^{\Large x^3\,\ \equiv\,\ 10}\iff x\equiv -1\equiv\color{#0a0}{10}\,\ $ by $\ \overbrace{x\equiv x^{3\cdot 7}}^{\Large\color{#a0f}{ 1\ \equiv\ x^{10}}}\equiv (-1)^7\equiv -1\ $ by $\,\rm\color{#a0f}{Fermat}$

${\rm mod}\ \color{#c00}{10}\!:\ x^3\equiv\ \ 0\ \iff x\equiv\ \,0\,\ \equiv\color{#0a0}{10} \ \,$ by $\ 2,5\mid x^3\!\iff 2,5\mid x$

${\rm mod}\ \ \,9\!: \ x^3\equiv \ \ 1\ \iff x\equiv \ \ 1\ \equiv\ \color{#0a0}{10}\pmod{\color{#c00}3}\ $ by Binomial Thm / LTE / brute force

So $\ \ x^3\equiv 10\,\pmod{990}\iff\!\!\! \underbrace{x\, \equiv\color{#0a0}{10}\pmod{\color{#c00}{330}}}_{\large \equiv\, 10,340,670\pmod{990}}\ $ by $\,\color{#c00}{330} = {\rm lcm}(\color{#c00}{11,10,3})$

Clearly $x=10k$ for some $k\in\mathbb Z$. Then $100k^3\equiv 1\pmod {\!99}\,\Leftrightarrow\, k^3\equiv 1\pmod {\!99}$

$$\Rightarrow\, \bmod{3}\!:\ k\equiv 1\text{ or } k^2+k+1\equiv 0$$

In either case, $\ k\equiv 1\pmod {\!3}$. $\:(1)$ $$\Rightarrow\, \bmod{11}\!:\ k\equiv 1\text{ or }k^2+k+1\equiv 0$$

The latter is impossible. To see this, you can simply check by substituting $k\equiv 0,1,\ldots, 10$, but you may also observe that $\Delta\equiv 1-4\equiv -3\equiv 8\pmod{\!11}$ isn’t a quadratic residue (which is because $\left(\frac{-3}{p}\right)=\left(\frac{p}{3}\right)\equiv p\pmod{\!3}$ and $11\equiv -1\pmod{\!3}$)(to see what this means, see my other answer).

This gives $k\equiv 1\pmod {\!11}$. $\:(2)$

$(1)(2)\,\Rightarrow\, k=33l+1$ for some $l\in\mathbb Z$, $\Rightarrow x=10(33l+1)=330l+10$. So the only possible solutions are $x\equiv 10, 340, 670\pmod {\!990}$, and after checking them, they work. $\ \ \ \square$

Notice how I reduced a cubic congruence to linear and quadratic congruences. Right after the first line, I could’ve continued with $\Rightarrow k^3\equiv 1\pmod{\!9},\: k^3\equiv 1\pmod{\!11}$, both of which are easily solvable by substituting all the possible values (mod the number) or by doing it like Bill Dubuque did (using FLT, namely $k^3\equiv 1\pmod{\!9}\,\Rightarrow\, k^3\equiv 1\stackrel{\text{FLT}}\equiv k\pmod{\!3}$ and $(k^3)^7\equiv (1)^7\stackrel{\text{FLT}}\equiv k$ mod $11$). This answer is to show a different way, using the theory of quadratic congruences only.