Solvability of $a \equiv x^2 \mod b$

Question

Suppose you want to prove that $\exists x \in \mathbb{Z}$ with $a \equiv x^2 \mod b$. Write $b = \prod_{i = 1}^{k} p_i^{e_i}$, the prime factorisation of $b$.

Why is the equivalent with finding solutions to $a \equiv x_i^2 \mod p_i$? How does one apply the Chinese Remainder Theorem here?

Thanks in advance!

Answer 1

That is because the ring $\mathbf Z/b\mathbf Z$ is isomorphic to the product of rings $\displaystyle\prod_i\mathbf Z/p_i^{e_i}\mathbf Z$.

Thus a number is a square modulo $b$ if and only if its images in each of the factors is a square.

Furthermore, Bézout's identity is the tool to go back from the set of squares modulo each of $p_i^{e_i}$ to square modulo $b$.

Some details on the workflow:

• Suppose $x_i$ is a square modulo $p_i^{e_i}$, $x_j$ a square modulo $p_j^{e_j}$. We have to find an $x$ such that $$\begin{cases}x\equiv x_i\mod p_i^{e_i}\\x\equiv x_j\mod p_j^{e_j}\end{cases}$$ Let $\;u\mkern1mu p_i^{e_i}+v\mkern1mu p_j^{e_j}=1$ a Bézout relation between $p_i^{e_i}$ and $p_j^{e_j}$. Clearly $\;u\mkern1mu p_i^{e_i}\equiv 1\mod p_j^{e_j}$ and $\;v\mkern1mu p_j^{e_j}\equiv 1\mod p_i^{e_i}$. Hence a solution is:$$u\mkern1mu p_i^{e_i}x_j+v\mkern1mu p_j^{e_j}x_i\bmod p_i^{e_i}\mkern1mu p_j^{e_j}.$$
• Next step: solve the system of congruences: $$\begin{cases}y\equiv x\mod p_i^{e_i}\mkern1mu p_j^{e_j}\\ y\equiv x_k\mod p_k^{e_k}\end{cases}$$
• &c.