Fracciones en la aritmética modular

Question

Supongamos que tenemos $$\frac{2}{3} \equiv x \bmod 5$$

Entiendo que el primer paso que hay que dar es: $$2 \equiv 3x \bmod 5$$

Pero a partir de ahí me cuesta entender la lógica de cómo resolver para $x$ . Obviamente, con números simples como este ejemplo, la respuesta es $4$ pero ¿cómo puedo abstraer el proceso para resolver $x$ cuando los números son muy grandes?

Answer 1

La aritmética del módulo suele tratar con números enteros, no con fracciones. En lugar de dividir, se multiplica por el inverso. Por ejemplo, no se tendría $\frac2 3\equiv x\mod 5$ , tendrías $2\cdot 3^{-1}\equiv x\mod 5$ . En este caso, $3^{-1}\equiv 2\mod 5$ , por lo que tendrías $2\cdot 2\equiv 4\mod5$ . La inversa de un número $a$ en aritmética modular es el número $a^{-1}$ tal que $a\cdot a^{-1}\equiv 1\mod n$ .

Answer 2

Primero es importante saber si alguien hace utilizar una declaración $\frac 23 \equiv x \mod 5$ es sólo notación para la solución (si la hay) de $2 \equiv 3x \mod 5$ y no tiene nada que ver con el número racional $\frac 23$ .

Segundo $ax \equiv b \mod N$ no tendrá ninguna solución a menos que $\gcd(a,N)|b$ . Lo que significa que $N$ y $a$ son coprimos o $\frac ab$ fue no en términos mínimos.

Si $ax \equiv b \mod N $ entonces $a/\gcd (a,N)x \equiv b/\gcd (a,N) \mod N/\gcd (a,N) $

Así que basta con suponer $N$ y $a$ son coprimos:

$ay \equiv 1 \mod N$ que será suficiente como $x \equiv ab \mod N$ resolverá nuestra ecuación original. Llamamos $y$ para que $ay \equiv \mod N$ $a^{-1}$ y sólo existe si $N$ y $a$ son coprimos.

Lo primero que hay que probar es el Pequeño Teorema de Fermats.

$a^{\phi (N)}\equiv 1 \mod N $ así que $a^{-1}\equiv a^{\phi (N)-1}\mod N $ .

Pero si eso no es práctico....

$ay = 1 \mod N$

$ay = wN + 1$

$wN = ay -1$

$wN \equiv -1 \mod a$

Repetir para tratar de resolver $w$ .

Así, por ejemplo:

$27x \equiv 35 \mod 71; x = 35y \mod 71$

$27y \equiv 1 \mod 71; 27y = 71z + 1$

Por el pequeño teorema de Fermats $27^{70} = 1 \mod 71$ así que $y \equiv 27^{69}$ pero no hay manera de que lo hagamos.

$71z \equiv -1 \mod 27$

$17z \equiv -1 \mod 27; 17z = 27w -1$

$27w \equiv 1 \mod 17$

$10w \equiv 1 \mod 17; 10w = 17a +1$

$17a \equiv -1 \mod 10$

$7a \equiv -1 \mod 10; 7a = 10b -1$

$10b \equiv 1 \mod 7$

$3b \equiv 1 \mod 7; $ 3b =7c + 1$

$7c \equiv -1 \mod 3$

$c \equiv - 1 \mod 3$

$3b = -7 + 1; b=-2$

$7a = 10(-2) -1; a = -3$

$10w = 17(-3) +1; w = -5$

$17z = 27(-5) -1=-136; z = -8$

$27y = 71(-8) + 1=-68; y = -21$

Así que $y=27^{-1}=50$

$x \equiv 35(-21) \mod 71 \equiv 46 \mod 71$

Y vamos a comprobar $27*46 = 1242 \equiv 35 \mod 71$

Answer 3

Si $a$ y $N$ son coprimos, entonces (al menos en $\mathbb Z$ y otros anillos en los que se cumple la división con resto), se puede utilizar el algoritmo de Euclides para fingir números $y,b$ tal que $a\;y + N\;b =1$ Así que $a\;y \equiv 1 \bmod N$ .