Congruencia mediante el GCD ampliado

Question

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$

El algoritmo euclidiano ampliado da $x50 \bmod 105$ .

Ahora entiendo que si combinamos los dos implica $15a-21b = 3$ pero no entiendo cómo usar el GCD extendido para pasar de ahí a encontrar $x$ y el módulo correspondiente.

Esto es lo que estoy usando para los cálculos extendidos de gcd:

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)

Desde https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Python

Answer 1

Como el GCD de los módulos es $(15,21)=3$ es necesario que $x$ sea lo mismo en ambas ecuaciones mod $3$ . Es decir, $$ x\equiv5\pmod{15}\implies x\equiv2\pmod{3} $$ y $$ x\equiv8\pmod{21}\implies x\equiv2\pmod{3} $$ Si no conseguimos eso $x\equiv2\pmod{3}$ de ambas ecuaciones, no sería posible una solución.

Esto nos lleva a analizar $\frac{x-2}3\pmod{\frac{15}3}$ y $\frac{x-2}3\pmod{\frac{21}3}$ . Es decir, $$ \frac{x-2}3\equiv1\pmod{5}\tag{1} $$ y $$ \frac{x-2}3\equiv2\pmod{7}\tag{2} $$

Utilizando el Algoritmo Euclidiano Extendido tal y como se implementa en esta respuesta , $$ \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} $$ conseguimos que $$ \underbrace{5(3)}_{\large\color{#C00000}{15}}+\underbrace{\!7(-2)\!}_{\large\color{#00A000}{-14}}=1\tag{4} $$ Podemos utilizar $(4)$ para ver que $$ \begin{align} \color{#00A000}{-14}&\equiv\color{#0000F0}{1}\pmod{5}\\ \color{#00A000}{-14}&\equiv\color{#0000F0}{0}\pmod{7} \end{align}\tag{5} $$ y que $$ \begin{align} \color{#C00000}{15}&\equiv\color{#0000F0}{0}\pmod{5}\\ \color{#C00000}{15}&\equiv\color{#0000F0}{1}\pmod{7} \end{align}\tag{6} $$ Para resolver $(1)$ y $(2)$ podemos añadir $1$ veces $(5)$ a $2$ veces $(6)$ para conseguir $$ \begin{align} 16&\equiv\color{#0000F0}{1}\pmod{5}\\ 16&\equiv\color{#0000F0}{2}\pmod{7} \end{align}\tag{7} $$ Ecuaciones $(7)$ nos dicen que $\frac{x-2}3\equiv16\pmod{35}$ o que $$ \bbox[5px,border:2px solid #C0A000]{x\equiv50\pmod{105}}\tag{8} $$

Answer 2

Es un poco más sencillo si procedemos de la siguiente manera

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

Así que concluimos $\, x = 8\!+\!21(\color{#c00}{2\!+\!5}n) = 50\! +\! 105n$

Nota: $ $ Ver aquí para el método general de transformación de la solución Bezout en una solución CRT.