Why is this congruence true? $$\eqalign{ x &\equiv 5 \mod 15\cr
              x &\equiv 8 \mod 21\cr}$$
The extended Euclidean algorithm gives $x≡50 \bmod 105$.
How/why? I am trying to understand how this is true when the Euclidean algorithm typically needs only two inputs $a,b$. I see four numbers in these two congruences.
 A: $x \equiv 5 \bmod 15$ means that $x=5+15a$.
$x \equiv 8 \bmod 21$ then means that $5+15a=8+21b$.
So, you're looking for $a,b$ such that $15a-21b=3$.
Here enters the extended Euclidean algorithm.
We get $a=3$ and $b=2$ and so $x=50$. This solution is unique mod lcm$(15,21)=105$.
A: When you say $x\equiv 5 \mod 15$ you are saying that $x$ is in some coset of $15\mathbb{Z}$, let's call it $15\mathbb{Z}+5=\{...,-10,5,20,...\}$.
When you say $x\equiv 8 \mod 21$ you are saying that $x$ is in some coset of $21\mathbb{Z}$, that is $21\mathbb{Z}+8=\{...,-13,8,29,...\}$, and you're looking for the intersection of both cosets.
The proof of the chinese remainder theorem shows that the solution is given modulo the product of the moduli in each congruence. The most important thing is that the solution is indeed a coset of some $u\mathbb{Z}$, given that the moduli are relatively prime.
Note: This is one of my not common answers, if I missed something, or something is not clear, please comment and I will try to extend/modify it.
