Congruence using extended GCD

Question

$$\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

Answer 1

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} $$