resolver sistemas de Congruencias lineales mod 13

Question

Dado el sistema: $$ 2x+5y \equiv 1 \textrm{mod} 13 $ $ $$ 5x+y \equiv 2 \textrm{mod} 13 $ $

¿Cuál es el valor de $$ 5x+7y \equiv \textrm{mod} 13 $ $?

¿tengo que resolver las dos primeras ecuaciones, es decir, $x=11+5t, y=1-2t$ para la primera ecuación, hacer lo mismo con el segundo, obtener los valores comunes de $x, y $ y hacer el cálculo? ¿o hay otro método?

Answer 1

No tienes que resolver las dos primeras ecuaciones. $5x+7y=(5+26)x+(7+13)y=3(2x+5y)+5(5x+y)=3+10=0 \mod 13$.

Answer 2

$$I\;\;\;\;\;2x+5y=1\pmod {13}$$

$$II\;\;\;\;5x+2y=2\pmod {13}$$

Multiplicar la EC. I -5 y eq.II por 2 y añadir los resultados (por simplicidad todos los siguientes se hace modulo 13):

$$(-5)\cdot I\;\;\;\;\;-10x-25y=-5$$

$$2\cdot II\;\;\;\;\;\;\;10x+4y=4$$

$$-21y=-1\Longrightarrow y=\frac1{21}=\frac18=5$$

Y sustituye ahora, decir en I:

$$2x+5(5)=1\Longrightarrow2x=-24=2\Longrightarrow x=1$$

Answer 3

$2x+5y\equiv 1\pmod{13}\implies 2x+5y=1-13a$

$5x+y\equiv 2\pmod{13}\implies 5x+y=2-13b$ $a,b$enteros por ciento.

Resolución de $x,y,$ llegar, $x=\frac{9+13(a-5b)}{23},y=\frac{1+13(2b-5a)}{23}$

$23(5x+7y)=5(9+13(a-5b))+7(1+13(2b-5a))\equiv 5\cdot9+7\pmod{13}\equiv 0$

$\implies 5x+7y\equiv 0\pmod{13} $ $(13,23)=1$

$ 5x+7y$ No había sido $\equiv 0\pmod{13} $ necesitamos multiplicar el lado derecho con $(23)^{-1}\pmod{13}\equiv (-3)^{-1}$.

Ahora, $(-3)^2=9,(-3)^3=-27\equiv -1\pmod{13}\implies (-3)^{-1}\equiv -(-3)^2\equiv 4$

Answer 4

En general para este tipo de problema:

$ax+by=c$

$dx+ey=f$

$gx+hy=z$

Para encontrar el valor de $z$ sin que la primera conclusión a la que $x,y$.

Calcular el determinante de la matriz con filas

$[a, b, c]$

$[d, e, f]$

$[g, h, z].$

Multiplicar y obtener el factor de en frente de z (esta mejor que ser distinto de cero mod n), y mueva el punto de vista numérico, el factor determinante para el otro lado. Ahora divida por lo que está delante de $z$ conseguir $z$ mod $n$.

Para el ejemplo anterior, las filas se [2,5,1],[5,1,2],[5,7,z] y el factor determinante es $-23z+52.$ por Lo que z = 52/23 = 0 desde el 13 de divide 52 y 23 no es cero mod 13. En general este método consiste en encontrar la inversa de mod $n$ del coeficiente de $z$

La razón de que el método funciona, es que las tres ecuaciones son equivalentes a decir que de las tres filas de la matriz son todos ortogonal al vector $[x,y,-1]$. Por lo tanto se encuentran en un subespacio de dos dimensiones de $R^3$ y son linealmente dependientes, haciendo que el determinante $0$.

Answer 5

Para hacer la técnica explícita (mediante coffeemath de nomenclatura):

Se le da tambièn $a, b, c, d, e, f, g$ $h$ y las incógnitas $x$ $y$ de tal manera que (todas las igualdades son modulo algunos prime $p$) $a x + b y = c$ $d x + e y = f$, y desea evaluar $g x + h y$ sin determinar primero $x$$y$.

Una manera de hacer esto es encontrar los valores de $u$ $v$ tal que $u$ veces la primera ecuación además de $v$ veces la segunda ecuación da, por el lado izquierdo, el lado izquierdo de la tercera ecuación. Entonces, la resultante lado derecho da el resultado deseado (de nuevo, todos los cálculos están modulo $p$).

Por lo tanto, queremos (con un poco de abuso de notación) u(a x+b y = c) + v(d x + e y + f) = g x + h y = ?$.

Esto produce las dos ecuaciones $u a + v d = g$ $u b + v e = h$ para ser resuelto por $u$$v$. Una vez hecho esto, el valor que se desea es $u c + v f$, las de la derecha lados.