Chinese Remainder Theorem RSA I want to solve the following modular quadratic equation:
$x^2 \equiv 188 \pmod {437}$ using the fact that $437$ can be factorized by the primes as: $19⋅23$.
So far I have done:
$$x^2 \equiv 188 \pmod{19} \Rightarrow x^2 \equiv 17 \pmod {19}\\
x^2 \equiv 188 \pmod {23} \Rightarrow x^2 \equiv 4 \pmod {23}$$
$$x^2 \equiv 7 \pmod{ 19} \Rightarrow x \equiv \pm 6 \pmod {19}\\
x^2 \equiv 4 \pmod {23} \Rightarrow x \equiv \pm 2 \pmod {23}$$
And the last step. But I do not understand how to combine:
$$x \equiv  6 \pmod {19} \text{ and } x \equiv  2 \pmod {23} \Rightarrow x \equiv \text{"insert-her"} \pmod {437}\\
x \equiv -6 \pmod {19} \text{ and } x \equiv  2 \pmod {23} \Rightarrow x \equiv \text{"insert-her"} \pmod{ 437}\\
x \equiv  6 \pmod {19} \text{ and } x \equiv -2 \pmod {23} \Rightarrow x \equiv \text{"insert-her"} \pmod {437}\\
x \equiv -6 \pmod {19} \text{ and } x \equiv -2 \pmod {23} \Rightarrow x \equiv \text{"insert-her"} \pmod {437}$$
Please help me fill the "insert-her".
 A: In general, we have distinct primes $p,q$; we have integers $a \in [0,p)$ and $b \in [0,q)$; and we want $x$ such that $x \equiv a$ mod $p$ and $x \equiv b$ mod $q$.
To solve this equation, the first step is to calculate $r = p^{-1}$ mod $q$. Assuming we have done that, the rest is easy: just set $x = (b-a)rp + a$. Then $x \equiv a$ mod $p$, obviously; and $rp \equiv 1$ mod $q$, so $x \equiv (b-a)rp + a \equiv (b-a)+a \equiv b$ mod $q$.
In practice, you will usually want $x$ to satisfy $0 \le x < pq$; this can be done by reduction mod $pq$.
So the only thing left is how to calculate $r = p^{-1}$ mod $q$. This is a well-known application of the Euclidean algorithm, which you can read about in this Wikipedia article.
In your example, we have $p=19, q=23$; and applying the Euclidean algorithm will give you $r=19^{-1}$ mod $23 = 17$. So, for instance, if $x \equiv 6$ mod $19$ and $x \equiv 2$ mod $23$, we have $x = (2-6)\cdot 17 \cdot 19 + 6 = -1286 \equiv 25$ mod $437$.
A: You can find the solution using this calculator just fill in $$ x=6 \mod 19$$ and $$
x=2 \mod 23
$$
Your solution is $25$ and indeed $188 \equiv 25^2 \pmod {437} $
