Congruence using extended GCD $$\eqalign{ x &\equiv 5 \mod 15\cr
              x &\equiv 8 \mod 21\cr}$$
The extended Euclidean algorithm gives $x≡50 \bmod 105$.
I understand now that if we combine the two it implies $15a-21b = 3$ but I don't understand how to use the extended GCD to go from there to finding $x$ and the corresponding modulus.
This is what I am using for the extended gcd computations:
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

From https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Python
 A: Since the GCD of the moduli is $(15,21)=3$, it is necessary that $x$ be the same thing in both equations mod $3$. That is,
$$
x\equiv5\pmod{15}\implies x\equiv2\pmod{3}
$$
and
$$
x\equiv8\pmod{21}\implies x\equiv2\pmod{3}
$$
If we didn't get that $x\equiv2\pmod{3}$ from both equations, a solution would not be possible.
This prompts us to look at $\frac{x-2}3\pmod{\frac{15}3}$ and $\frac{x-2}3\pmod{\frac{21}3}$. That is,
$$
\frac{x-2}3\equiv1\pmod{5}\tag{1}
$$
and
$$
\frac{x-2}3\equiv2\pmod{7}\tag{2}
$$
Using the Extended Euclidean Algorithm as implemented in this answer,
$$
\begin{array}{r}
&&1&2&2\\\hline
1&0&1&-2&5\\
0&1&-1&3&-7\\
7&5&2&1&0
\end{array}\tag{3}
$$
we get that
$$
\underbrace{5(3)}_{\large\color{#C00000}{15}}+\underbrace{\!7(-2)\!}_{\large\color{#00A000}{-14}}=1\tag{4}
$$
We can use $(4)$ to see that
$$
\begin{align}
\color{#00A000}{-14}&\equiv\color{#0000F0}{1}\pmod{5}\\
\color{#00A000}{-14}&\equiv\color{#0000F0}{0}\pmod{7}
\end{align}\tag{5}
$$
and that
$$
\begin{align}
\color{#C00000}{15}&\equiv\color{#0000F0}{0}\pmod{5}\\
\color{#C00000}{15}&\equiv\color{#0000F0}{1}\pmod{7}
\end{align}\tag{6}
$$
To solve $(1)$ and $(2)$ we can add $1$ times $(5)$ to $2$ times $(6)$ to get
$$
\begin{align}
16&\equiv\color{#0000F0}{1}\pmod{5}\\
16&\equiv\color{#0000F0}{2}\pmod{7}
\end{align}\tag{7}
$$
Equations $(7)$ tell us that $\frac{x-2}3\equiv16\pmod{35}$ or that
$$
\bbox[5px,border:2px solid #C0A000]{x\equiv50\pmod{105}}\tag{8}
$$
A: It's a bit simpler if we proceed as follows
$\bmod 15\!:\,\ 5\equiv x\equiv 8\!+\!21\,\color{#c00}k\equiv 8\!+\!6k\ \ \overbrace{\!\!\iff 6k\equiv -3\iff\bmod\color{#c00} 5\!:\,\ 2k\equiv -1}^{\Large\! 15j\,+\,6k\ =\ -3\ \ \ \ \overset{\LARGE (\ \ )/3}\iff\ \ \ \  5j\,+\,2k\ =\ -1 }\equiv 4\iff \color{#c00}{k\equiv 2}$
So we conclude $\, x = 8\!+\!21(\color{#c00}{2\!+\!5}n) = 50\! +\! 105n$
Remark $ $ See here for the general method of transforming the Bezout solution into a CRT solution.
