Resolución de sistemas de ecuaciones lineales sobre un anillo finito

Question

Quiero resolver ecuaciones como esta (mod $2^n$ ):

$$\begin{array}{rcrcrcr} 3x&+&4y&+&13z&=&3&\pmod{16} \\ x&+&5y&+&3z&=&5&\pmod{16} \\ 4x&+&7y&+&11z&=&12&\pmod{16}\end{array}$$

Como estamos trabajando sobre un anillo y no sobre un campo, la eliminación gaussiana no funciona. Entonces, ¿cómo puedo seguir resolviendo este tipo de ecuaciones?

Answer 1

Puedes seguir utilizando la eliminación gaussiana siempre que no "dividas" por cosas que no sean relativamente primos del módulo. En este caso, puedes "dividir" por cualquier número impar, y realizar todos los cálculos habituales. En este caso, puedes realizar la gaussiana bastante bien: \begin{align*} \left(\begin{array}{ccc|c} 3 & 4 & 13 & 3\\ 1 & 5 & 3 & 5\\ 4 & 7 & 11 & 12 \end{array} \derecha) &\a la derecha-flecha \izquierda( \begin{array}{ccc|c} 1 & 5 & 3 & 5\\ 3 & 4 & 13 & 3\\ 4 & 8 & 11 & 12 \end{array} \derecha) && \N-flecha derecha \izquierda( \begin{array}{ccr|c} 1 & 5 & 3 & 5\\ 0 & 5 & 4 & 4\\ 0 & 4 & -1 & 8 \end{array} \derecha) flecha derecha \izquierda( \begin{array}{ccr|r} 1 & 5 & 3 & 5\\ 0 & 1 & 5 & -4\\ 0 & 4 & -1 & 8 \end{array} \N - derecha) &&flecha derecha \izquierda( \begin{array}{ccr|r} 1 & 5 & 3 & 5\\ 0 & 1 & 5 & -4\\ 0 & 0 & 11 & 8 \end{array} \N - derecha). |align*} Así que aquí se obtiene que $11z\equiv 8 \pmod{16}$ . Desde $11^{-1} \equiv 3\pmod{16}$ Esto significa que $z \equiv 24 \equiv 8\pmod{16}$ . Entonces puedes hacer una sustitución inversa y resolver. (Suponiendo que no haya cometido ningún error con mi aritmética modular, de todos modos...)

Si tienes la mala suerte de obtener una congruencia en la que todos los coeficientes sean pares, entonces puedes dividir por $2$ y obtener una congruencia módulo $8$ (en lugar de $16$ ); lo que dará lugar a dos soluciones módulo $16$ (si consigues $x\equiv 4 \pmod{8}$ , lo que significa que $x\equiv 4 \pmod{16}$ o $x\equiv 8+4=12\pmod{16}$ por ejemplo).

Básicamente, mientras tengas cuidado, puedes ciertamente hacer la eliminación gaussiana. Incluso se puede hacer sobre anillos más generales, aunque en ese caso hay que tener otras restricciones sobre lo que se puede o no concluir.

Answer 2

Básicamente se hace la eliminación gaussiana como siempre, aunque se puede atascar si en algún momento todos los coeficientes de una variable son, digamos, pares. Esto sólo significa que tendrás dos soluciones para esa variable. En general, elegirás la fila en la que el coeficiente tenga la menor potencia de $2$ .