<s>[INST] Fastest way to solve $x^3\equiv x \pmod{105}$ $$x^3\equiv x \pmod{105}$$
I'm trying to solve this equation. Here's what I tried so far:
$$x^3\equiv x \pmod{105} \iff x^2\equiv 1 \pmod{105}$$
Then, applying the Chinese remainder theorem, I got the system:
$$\cases{x^2 \equiv 1 \pmod{5}\\x^2 \equiv 1 \pmod{7}\\x^2 \equiv 1 \pmod{3}}$$
With the following solutions:
$$\cases{x \equiv \pm1 \pmod{5}\\x \equiv \pm1 \pmod{7}\\x \equiv \pm1 \pmod{3}}$$
At this point, I think I need to pretty much solve these eight systems:
$$\cases{x \equiv 1 \pmod{5}\\x \equiv 1 \pmod{7}\\x \equiv 1 \pmod{3}}
\cases{x \equiv 1 \pmod{5}\\x \equiv 1 \pmod{7}\\x \equiv -1 \pmod{3}}
\cases{x \equiv 1 \pmod{5}\\x \equiv -1 \pmod{7}\\x \equiv 1 \pmod{3}}
\cases{x \equiv -1 \pmod{5}\\x \equiv 1 \pmod{7}\\x \equiv 1 \pmod{3}}$$$$
\cases{x \equiv -1 \pmod{5}\\x \equiv 1 \pmod{7}\\x \equiv -1 \pmod{3}}
\cases{x \equiv -1 \pmod{5}\\x \equiv -1 \pmod{7}\\x \equiv 1 \pmod{3}}
\cases{x \equiv 1 \pmod{5}\\x \equiv -1 \pmod{7}\\x \equiv -1 \pmod{3}}
\cases{x \equiv -1 \pmod{5}\\x \equiv -1 \pmod{7}\\x \equiv -1 \pmod{3}}$$
Here's how I solved the first one:
Considering the first two equations, we get:
$$x=5k+1=7h+1$$ from which $k = 7+7y, h = 5+5y$, with $y \in \mathbb{Z}$. Therefore, $$x=36+35y\iff x\equiv1\pmod{35}$$
Adding in the third equation, we have that $36+35y = 1+3 w$, from which $x = 1281 + 35w \iff x \equiv1\pmod{105}$.
However, this one seems like a really tedious method as I'd have to do the same calculations for seven more systems. Is there anything I'm missing? Is there a faster way to do this?
 [/INST] Hint $ $ It's always true mod $3,\,$ so by CRT we need only combine all roots $\{0,\pm1\}$ mod $5$ and $7,\,$ and $\,x\equiv a\pmod{\!5},\,x\equiv b\pmod{\!7}\!\iff\! x\equiv b+14(b-a)\pmod{\!35}.\,$ For $\,a,b\in \{0,\pm1\}$ this yields $\,x\equiv \pm \{0,1,6,14,15\}\pmod{\!35}$
</s>