Resolver un sistema de congruencia (que tiene otras soluciones)

Question

Estoy tratando de resolver este sistema de congruencia : $$\begin{cases} 3x+7y\equiv 5[11]\\ 8x+4y\equiv6[11] \end{cases} $$ Primero multiplico por $8$ y $3$ ambas ecuaciones resp. $$\begin{cases} 24x+56y\equiv40[11]\equiv7 [11]\\ 24x+12y\equiv18[11]\equiv7 [11] \end{cases} $$ A continuación, restamos la segunda ecuación de la primera. $$44y\equiv0[11],$$ Desde $gcd(11,44)=11$ , entonces la ecuación anterior es equivalente a : $4y\equiv0[11]$ y entonces encontramos que : $$y\equiv0[11],$$ y ahora lo reemplazo en la siguiente ecuación : $3x+7\times 0\equiv5[11]$ lo que equivale a : $3x\equiv5[11]$ Por lo tanto $$x\equiv 9[11]$$ Como resultado $(9+11k,0+11k')$ con $k,k' \in \mathbb{Z}$ son soluciones del sistema.

Ahora mi comentario es el siguiente: me he dado cuenta de que también $(0+11k,7+11k')$ con $k,k' \in \mathbb{Z}$ y también $(7+11k,4+11k')$ con $k,k' \in \mathbb{Z}$ también son soluciones del sistema que no entiendo.

Answer 1

Ya que al eliminar las dos ecuaciones resulta $44y \equiv 0 \pmod {11}$ que es cierto para todos los enteros $y$ las dos ecuaciones no son independientes. En consecuencia, debemos expresar los valores de $x$ en términos de $y$ utilizando una de las ecuaciones. Por ejemplo:

$$3x+7y\equiv 5 \pmod {11} \implies 12x + 28y \equiv 20 \pmod {11} \implies x\equiv 9+5y\pmod {11}$$

Para verificar que $(9+5y,y)$ da todas las soluciones, sustituimos esto a la segunda ecuación, y tenemos:

$$8x+4y \equiv 72+44y\equiv 6\pmod {11}$$

por lo que ambas ecuaciones se satisfacen. $(9,0), (0,7), (7,4)$ son soluciones particulares, modulo $11$ .

Answer 2

Una nota sobre la reducción $\quad ax\equiv b\pmod m\quad$ y un divisor $\quad d$

• si $\gcd(m,d)=1$ entonces se puede dividir $a,b$ por $d$ y mantener el mismo módulo

Por ejemplo $\quad 6x\equiv 9\pmod{11}\iff 2x\equiv 3\pmod{11}$

• si $\gcd(m,d)\neq 1$ y $d$ divide $a,b$ entonces se puede reducir la ecuación a un módulo inferior

Por ejemplo $\quad 6x\equiv 9\pmod{15}\iff 2x\equiv 3\pmod{5}$

• En todos los demás casos, intente multiplicar por $a^{-1}$ o $b^{-1}$ dependiendo de que sea relativamente primo con el módulo.

Por ejemplo $\, 2^{-1}\equiv 6\pmod{11}\, $ así $\, 2x\equiv 3\pmod{11}\iff 12x\equiv x\equiv 18\equiv 7\pmod {11}$

En el presente caso $44y\equiv 0\pmod{11}$ se obtiene en el primer caso para $d=4$ y el segundo caso para $d=11$ .

$44y\equiv 0\pmod{11}\iff 11y\equiv 0\pmod{11}\iff y\equiv 0\pmod 1\quad$ que siempre es cierto para un entero aleatorio $y$ .

Tenga en cuenta que como $44$ es un múltiplo de $11$ la ecuación también es simplemente $0y\equiv 0\pmod{11}$ y esto es sólo un poco de $0=0$ ecuación, no aportando combustible al problema (o más bien que $y$ es una variable libre).

Answer 3

El determinante de la matriz $\left[ \begin{array}{cc} 3 & 7 \\ 8 & 4 \end{array} \right]$ es $3 \cdot 4 - 8 \cdot 7 = 1 - 1 = 0 \pmod{11}$

Por lo tanto, las dos ecuaciones son linealmente dependientes.

Un poco de trabajo da como resultado $10(3x+7y) = 30x + 70y = 8x + 4y \pmod{11}$

Por lo tanto, no hay solución.