¿Cómo puedo utilizar la eliminación de Gauss para resolver ecuaciones con aritmética Modular?

Question

He dado algunas de las ecuaciones que se parecen a esto.

$a_{1,1} x_1 + a_{1,2} x_2 + a_{1,3} x_3 + ... + a_{1,n} x_n\equiv 1 \mod p$

$a_{2,1} x_1 + a_{2,2} x_2 + a_{2,3} x_3 + ... + a_{2,n} x_n\equiv 1\mod p$

$...$

$a_{m,1} x_1 + a_{m,2} x_2 + a_{m,3} x_3 + ... + a_{m,n} x_n\equiv 1\mod p$

($p$ es primo, sé que los valores de $a_{1..m, 1..n}$, tengo que conseguir un $x_{1..n}$) (todos los valores de $a_{1..m, 1..n}, x_{1..n}$ no debe ser negativo, y que deben ser números enteros)

Creo que puedo resolver esto mediante la eliminación Gaussiana, pero no estoy seguro de cómo utilizar este.

Agradezco cualquier ayuda o sugerencia. Gracias de antemano. :)

Answer 1

Si usted está familiarizado con la eliminación Gaussiana, entonces usted puede hacer esto fácilmente, todas las mismas operaciones son válidas, sólo reducir $\mod{p}$ cualquier momento usted desea simplificar mediante la reducción de tamaño de los números. Si es que las fracciones que le preocupa, entonces, ¿sólo operaciones con números enteros. Por ejemplo, si usted tiene los números 2 y 5, primer restar 2*2 de 5 a 1. Los números más grandes no pueden llegar a 1 tan rápido, pero la idea es la misma. Resta de enteros cantidades que reducir el número y repita el proceso con los números más pequeños hasta que todo se haya reducido.

Es la misma idea, sólo combinar las filas hasta que las cosas se simplifican.