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

  • $\begingroup$ Why are these two assertions equivalent? $\endgroup$ – Aemilius Mar 8 '18 at 22:52
  • $\begingroup$ @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$. $\endgroup$ – 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.


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.