How to find solutions to $x^2 \equiv 4 \pmod{91}$? As the title says, I'm looking to find all solutions to $$x^2 \equiv 4 \pmod{91}$$ and I am not exactly sure how to proceed.
The hint was that since 91 is not prime, the Chinese Remainder Theorem might be useful.
So I've started by separating into two separate congruences:
$$x^2 \equiv 4 \pmod{7}$$ $$x^2 \equiv 4 \pmod{13}$$
but now I'm confused about how to apply the CRT so I'm a bit stuck, and I'd appreciate any help or hints!
 A: We begin with your system of equations: $$\begin{cases} x^2 \equiv 4 \pmod{7} \\ x^2 \equiv 4 \pmod{13} \end{cases}$$
Then, solving each congruence, we obtain the system: $$\begin{cases} x \equiv \pm 2 \pmod{7} \\ x \equiv \pm 2 \pmod{13} \end{cases}$$
We therefore have four systems of linear congruences, each with a unique solution by the Chinese Remainder Theorem:
$$\begin{cases} x \equiv  2 \pmod{7} \\ x \equiv  2 \pmod{13} \end{cases} \tag{1}$$
$$\begin{cases} x \equiv  2 \pmod{7} \\ x \equiv - 2 \pmod{13} \end{cases} \tag{2}$$
$$\begin{cases} x \equiv - 2 \pmod{7} \\ x \equiv  2 \pmod{13} \end{cases} \tag{3}$$
$$\begin{cases} x \equiv - 2 \pmod{7} \\ x \equiv -2 \pmod{13} \end{cases} \tag{4}$$
These four solutions will be distinct modulo $91$, it remains to find them!
A: By the Chinese remainder theorem you get an isomorphism between those two rings :
$$\psi:\frac{\mathbb{Z}}{91\mathbb{Z}}\rightarrow \frac{\mathbb{Z}}{7\mathbb{Z}}\times \frac{\mathbb{Z}}{13\mathbb{Z}} $$
$$x\mapsto (x\text{ mod } 7,x\text{ mod } 13) $$
it means that to solve $4=s^2$ mod $91$ you only need to solve $\psi(4)=\psi(s)^2$ which in turn gives $4=s_1^2$ mod $7$ and $4=s_2^2$ mod $13$. Now we are mod some prime numbers, because we have two obvious solutions those are the only one. In other word $\psi(s)=(\epsilon_12,\epsilon_22)$ where $\epsilon_i\in\{\pm 1\}$. This give four solutions. Now you only need to find the inverse function of $\psi$ (it is a classical computation) to explicitely have the four solutions to the equation $4=s^2$ mod $91$. 
