Solving $x^2 + 96=0$ in $\mathbb{Z}_{100}$

Question

I'm trying to find all solutions to $x^2 + 96=0$ in $\mathbb{Z}_{100}$.

$x^2 + 96 \equiv 0 \bmod 100$ implies that $x^2 + 96 \equiv 0 \bmod 2$ and $x^2 + 96 \equiv 0 \bmod 5$.

$$x^2 + 96 \equiv 0 \bmod 2 \iff x^2 \equiv 0 \bmod 2.$$ This means that $x$ must be even, since the square of an odd number is odd. $$x^2 + 96 \equiv 0 \bmod 5 \iff x^2 \equiv 4 \bmod 5 \implies x=\pm2.$$ Is this correct?

Answer 1

You are correct so far. However, rather than considering $\mod 2$ and $\mod 5$ you should consider $\mod 4$ and $\mod 25$, as these modulos are relatively prime and multiply to get $100$.

Mod $4$, you will conclude that $x \equiv 0 \text{ or } 2$. Mod $25$, you can show that $x \equiv \pm 2 \pmod {25}$. Finally, use Chinese Remainder Theorem to find the possible values for $x$ $\mod 100$.

Answer 2

To fill in a last detail, here's how to work the problem mod $25$: first, solve the equation $x^2-4\equiv0\pmod 5$; you should find $x\equiv\pm2\pmod 5$ as your solutions. Now, we use the technique of Hensel lifting to 'raise' these solutions a degree, from $\pmod 5$ to $\pmod{5^2}$. First look at the $x\equiv 2$ root and write it as $x\equiv 5k+2\pmod{25}$, with $0\leq k\lt 5$. Now, we have $x^2\equiv 25k^2+20k+4\equiv 20k+4\pmod{25}$; so $x^2-4\equiv 20k\pmod{25}$. By easy inspection, the only solution of this in range is $k=0$, so that in fact $x\equiv 2\pmod{25}$. You can use similar algebra to find the root mod $25$ that's $\equiv -2\pmod{5}$.