1
$\begingroup$

Here is my attempt at it:

We observe that $105=3\cdot 5\cdot 7$, so the Chinese remainder theorem allows us to decompose the equation into the following $$x^3+x^2+x\equiv 0\bmod 3,$$ $$x^3+x^2+x\equiv 0\bmod 5,$$ $$x^3+x^2+x\equiv 0\bmod 7.$$ Now, if we take each equation in turn, we observe $$x^3+x^2+x\equiv 0\bmod 3\Rightarrow x\in\{0,1\},$$ $$x^3+x^2+x\equiv 0\bmod 5\Rightarrow x\in\{0\},$$ $$x^3+x^2+x\equiv 0\bmod 7\Rightarrow x\in\{0,2,4\}.$$ We start by solving modulo $15$ first, that is, combining the answers we got modulo $3$ and modulo $5$.

  • $[0]_3$ and $[0]_5$. This is equivalent to $x$ being divisible by $15$, that is $x\equiv0\bmod 15$.

    • $[1]_3$ and $[0]_5$. Observe $$x\equiv 1\bmod 3\Rightarrow x=3m+1\equiv 0\bmod 5\Rightarrow 3m\equiv 4\bmod 5\Rightarrow m\equiv 3\bmod 5,$$ $$m=5n+3\Rightarrow x=3(5n+3)+1=15n+10\Rightarrow x\equiv 10\bmod 15.$$

      Now, we have the solutions $$x\equiv0\bmod 15,\quad x\equiv 5\bmod 15,\quad x\equiv 10\bmod 15$$ and $$x\equiv 0\bmod 7,\quad 2\bmod 7,\quad 4\bmod 7.$$ By the Chinese remainder theorem (since $15$ and $7$ are coprime), we combine these congruences to get solutions modulo $105$.

      • $[0]_{15}$ and $[0]_7$. This is equivalent to being divisible by $105$, that is $x\equiv0\bmod 105$.
      • $[0]_{15}$ and $[2]_7$. Observe $$x\equiv 2\bmod 7\Rightarrow x=7m+2\equiv 0\bmod 15\Rightarrow m\equiv 4\bmod 15,$$ $$m=15n+4\Rightarrow x=7(15n+4)+2=105n+30\equiv x\equiv 30\bmod 105.$$
      • $[0]_{15}$ and $[4]_7$. Observe $$x\equiv 4\bmod 7\Rightarrow x=7m+4\equiv 0\bmod 15\Rightarrow m\equiv 8\bmod 15,$$ $$m=15n+8\Rightarrow x=7(15n+8)+4=105n+60\Rightarrow x\equiv 60\bmod 105.$$
      • $[10]_{15}$ and $[0]_7$. Observe $$x\equiv 10\bmod 15\Rightarrow x=15m+10\equiv 0\bmod 7\Rightarrow m\equiv 4\bmod 7,$$ $$m=7n+4\Rightarrow x=15(7n+4)+10\Rightarrow x=105n+70\Rightarrow x\equiv 70\bmod 105.$$
      • $[10]_{15}$ and $[2]_7$. Observe $$x\equiv 10\bmod 15\Rightarrow x=15m+10\equiv 2\bmod 7\Rightarrow m\equiv 6\bmod 7,$$ $$m=7n+6\Rightarrow x=15(7n+6)+10\Rightarrow x=105n+100\Rightarrow x\equiv 100\bmod 105.$$
      • $[10]_{15}$ and $[4]_7$. Observe $$x\equiv 10\bmod 15\Rightarrow x=15m+10\equiv 4\bmod 7\Rightarrow m\equiv 1\bmod 7,$$ $$m=7n+1\Rightarrow x=15(7n+1)+10\Rightarrow x=105n+25\Rightarrow x\equiv 25\bmod 105.$$

So my solution set modulo $105$ is $$x\in\{0, 30, 60, 70, 100, 25\}.$$ However I know this to be wrong as, when I checked my answer in an online congruence calculator, it gave me $$x\in\{0,25,30,60,70,100\}.$$ Any help as to where I went wrong?

EDIT: So me being an utter moron wrote that $2$ is a solution $\bmod 3$. Omitting this from my attempt now gives the following amendment and cuts out three elements in my solution set.

Now, the last thing is to see what went wrong to get $20\bmod 105$ instead of $25\bmod 105$.

EDIT (2): You know what, I actually am a moron. Silly error. I've got it now!

$\endgroup$
  • 1
    $\begingroup$ 2 isn't a solution mod 3. $\endgroup$ – Matthew Daly Oct 13 '19 at 18:03
  • $\begingroup$ wow, that was very lazy of me. thank you very much! $\endgroup$ – thesmallprint Oct 13 '19 at 18:03
1
$\begingroup$

$x^3 + x^2 + x = x(x^2 + x + 1)\equiv p$ for prime $p$ is only solveable by either $x \equiv p$ or $x^2 + x+1\equiv p$.

For $p = 3$ then then $x\equiv 0\pmod p$ is a solution.

If $x \not \equiv 0\pmod p$ then for

So $p=3$:

by FLT $x^3 + x^2 + x \equiv x + 1 +x\equiv 2x + 1\pmod 3$ and so $x\equiv 1 \pmod 3$ is a solution and $x\equiv 2 \pmod 3$ is not.

So solutions $\mod 3$ are $x \equiv 0,1$

$p\ne 3$:

Then $x\equiv 1$ will not be a solution to $x^2 + x + 1\equiv 0\pmod p$.

$(x-1)(x^2 + x + 1) = x^3 -1$ this will have solutions when $x^3 \equiv 1\pmod p$ but $x\not \equiv 1$.

$p= 5$

$x^3 \equiv 1$ by FLT means $\gcd(|x|, 5-1)|3$ so $|x| =1$ so $x \equiv 1$ so there are no solutions other than $x\equiv 0$.

So solutions $\mod 5$ are $x\equiv 0$

$p=7$

$(\pm2)^3 \equiv \pm1\pmod 7$ and $(\pm 3)^3\equiv \mp 1 \pmod 7$

So the solutions $\mod 7$ are $x \equiv 0,2,4$

....

So by CRT there thre should be $2*1*3=6$ unique solutions ot $x\equiv (0,1) \pmod 3; x\equiv 0 \pmod 5$ and $x \equiv 0,2,4\pmod 7$

They are

If $x\equiv 0\pmod 3,5$ then $x\equiv 0\equiv 15\pmod 15$ and as $15\equiv 1 \pmod 7$ the $15k\equiv k\pmod 7$.

So the soluitions to

$x \equiv 0,0,0 \pmod 3,5,7$ is $x \equiv 0\pmod{105}$

$x \equiv 0,0,2\pmod 3,5,7$ is $x \equiv 30\pmod{105}$

$x\equiv 0,0,4\pmod 3,5,7$ is $x\equiv 60\pmod{105}$.

And the solution to $x \equiv 1,0 \pmod 3,5$ is $x\equiv 10\pmod{15}$ so

And as $10 + 15k\equiv 3+k\equiv m\pmod 7$ then $k\equiv m-3\pmod 7$ so

$x\equiv 1,0,0\pmod 3,5,7$ has solution $10-3*15\equiv 70\pmod {105}$.

$x \equiv 1,0,2\pmod 7$ solution is $x\equiv 10-15\equiv 100\pmod {105}$

And $x\equiv 1,0,4 \equiv 10+15 \equiv 25\pmod {105}$

$x\equiv 0 \pmod 3,5,7$ are $x \equiv 0 \pmod{105}$

$x\equiv 0\pmod 3,5$ and $x\equiv 2\pmod 7$ is $x\equiv 30$.

| cite | improve this answer | |
$\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.