# Solving a cubic modular congruence

I need to solve this congruence: $$x(x^2-1) \equiv 34 \pmod {35}$$ I noticed that the left hand side is divisible by $3$, namely, $x(x-1)(x+1) \equiv0 \pmod 3$. Also, I thought that using the Chinese remainder theorem might work here. However, I can't find a good way to apply this theorem to single $x$'s.

Any hints will be most appreciated.

Asserting that we have $x(x^2-1)\equiv34\pmod{35}\equiv-1\pmod{35}$ is equivalent to asserting we have both$$x(x^2-1)\equiv-1\pmod5\tag1$$and$$x(x^2-1)\equiv-1\pmod7.\tag2$$Equation $(1)$ has a single solution, which is $3$. And equation $(2)$ also has a single solution, which is $2$. So, you can apply the chinese remainder theorem here and obtain that the answer is: $x\equiv23\pmod{35}$.

• Why are these two assertions equivalent? – Aemilius Mar 8 '18 at 22:52
• @Aemilius I'm just saying that a number $n$ is a multiple of $35$ if and only if it is both a multiple of $5$ and a multiple of $7$. – José Carlos Santos Mar 8 '18 at 22:56

Well $x(x+1)(x-1)$ being the product of three consecutive numbers is pretty cute if we are going to take modulo low terms.

So by CRT we want to solve

$x(x+1)(x-1) \equiv 4\equiv -1 \pmod 5$ and if we have $x\equiv 0,1,4$ we have $x(x+1)(x-1)\equiv 0 \pmod 5$ so we must have $x\equiv 2,3$ so $x(x+1)(x-1) \equiv$ either $1*2*(-2) \equiv 1$ or $2*(-2)*(-1)\equiv -1$. So $x \equiv 3 \pmod 5$.

Similar if $(x-1)x(x+1) \equiv 6\equiv -1 \pmod 7$. We can't have $x \equiv 0, \pm 1$ so $x \equiv \pm 2, \pm 3\pmod 7$. And $(x-1)x(x+1) \equiv 1*2*3;2*3*(-3);3*(-3)*(-2);(-3)*(-2)*(-1)\equiv -1, 3, -3, 1$ so $x \equiv 2 \pmod 7$.

So by CRT $x\equiv 23 \pmod {35}$.

Can't help but wonder if we could have been more efficient.

$x^3- x + 1\equiv 0 \pmod 5$. As $x^4 \equiv 1 \pmod 5$ when $x \ne 0$ then

$\frac 1x - x + 1 \equiv 0 \pmod 5$ so

$x^2 - x - 1 \equiv 0 \pmod 5$ so $x \equiv \frac {1 \pm \sqrt{1 +4}}{2} \equiv \frac {1 \pm 0}{2} = \frac 12\equiv 3 \pmod 5$ but I'd hardly call that efficient.

And $x^6\equiv 1 \pmod 7$ for $x \ne 0$ so $x^3 \equiv 1 \pmod 8 \implies x^3 \equiv \pm 1$. So $x^3 - x + 1\equiv -x;-x + 2 \equiv 0\pmod 7$ means that $x\equiv 2\pmod 7$ as $x\not \equiv 0 \pmod 7$.

True... but definitely not efficient.