Q:

Solve $x^2\equiv a$ mod $\prod P_i^{e_i}$

Suppose we have the solutions to  $x^2\equiv a$ mod $P_i^{e_i}$. How do we find solutions to $x^2\equiv a$ mod $\prod P_i^{e_i}$. For example, I know $x^2\equiv  1$ mod $3$ has solution $\pm 1$ mod $3$ and  $x^2\equiv  1$ mod $5$ has solution $\pm 1$ mod $5$. Can we construct all the solutions to  $x^2\equiv  1$ mod $15$ from them? Can we use Chinese remainder theorem?

A:

Yes, you can. You have to start from a Bézout's relation between $3$ and $5$:
$$2\cdot 3-1\cdot 5=1$$
Now if you have solutions $a$ mod. 3 and $b$ mod. $5$, we deduce  solutions mod. $15$:
$$x\equiv b\cdot 2\cdot 3-a\cdot 1\cdot 5=6b-5a\mod15.$$

