Necesito ayuda para encontrar restos cuando $5!25!$ se divide por $31$ ?

Question

Estoy muy confundido con la congruencia. Me esforcé, pero seguí fallando :(

$$30! \equiv -1 \pmod{31} \text{ by Wilson's Theorem}$$ $$ \Longleftrightarrow 30.29.28.27.26.25! \equiv -1 \pmod{31}$$ $$ \Longleftrightarrow (-1).15.10.(-8).6.25! \equiv -1 \pmod{31}$$ $$ \Longleftrightarrow 15.4.5!.25! \equiv -1 \pmod{31}$$ $$ \Longleftrightarrow 60.5!.25! \equiv -1 \pmod{31}$$ $$ \Longleftrightarrow 15.5!.25! \equiv -1 \pmod{31}$$

Y me quedé atascado aquí :( Además, tengo que utilizar el ordenador para encontrar un par de soluciones de la ecuación diofantina $ax + 31y = 1$ para cada número: $30, 29, 28, 27, 26 ... $ ¿Me pregunto si hay una forma más fácil de hacerlo? Porque creo que esta forma consume mucho tiempo. ¿Alguna idea?

Gracias,
Chan

Answer 1

Así que por el Teorema de Wilson, tienes $$ 30\cdot 29\cdot 28\cdot 27\cdot 26\cdot 25!\equiv -1\pmod{31}. $$ Pero fíjate que esto implica $$ (-1)(-2)(-3)(-4)(-5)25!\equiv (-1)^5 5!25!\equiv -1\pmod{31}, $$ desde $30\equiv -1\pmod{31}$ , $29\equiv -2\pmod{31}$ , $\dots$ y $26\equiv -5\pmod{31}$ .

Answer 2

Si está buscando $x$ tal que $15x = 1 \mod 31$ , fíjese que $15 \times 2 = 30 = -1 \mod 31$

Por lo tanto, $15 \times (-2) = 1 \mod 31$ .

Pero, como muestra la respuesta de yunone, tienes un error en alguna parte.

Answer 3

Como señalé en su pregunta previa, El teorema de Wilson da como resultado el fórmula de reflexión

$$\ \ \ \ \rm (p\!-\!1\!-\!k)\:!\ \equiv\ \frac{(-1)^{k+1}}{k!}\ \ (mod\ p),\ \ for\ p\ prime $$

Por lo tanto, deducimos $\bmod 31\!:\,\ 25!\equiv \dfrac{1}{\color{#c00}5!}\equiv\dfrac{32}{\color{#c00}{-4}}\equiv -8,\, $ por $\ \color{#c00}{5!}\equiv 4\ (5\cdot3\cdot2)\equiv \color{#c00}{4(-1)}$

Answer 4

Sé que esto ya se ha respondido con Wilson, pero me gustaría ser un poco más explícito con la respuesta. Seguro que @Chan ya lo tiene claro hace 6 años...

30! = 30*29*28*27*26*25!

30 es congruente con -1 mod 31

29 es congruente con -2 mod 31

28 es congruente con -3 mod 31

27 es congruente con -4 mod 31

26 es congruente con -5 mod 31

Ahora observa que ¡30! es congruente con -1 (mod p)

Entonces 30*29*28*27*26*25! es congruente con -1 (mod p)

Pero entonces tomando las inversas, tenemos que -1*-2*-3*-4*-5*25! es congruente con -1 (mod p).

Esto es posible porque para a congruente con b (mod p), b congruente con a (mod p). Así que 30*29*28*27*26*25! es congruente con -1*-2*-3*-4*-5*25! es congruente con -1 (mod p)

¡simplificando el lado izquierdo de la ecuación, obtenemos, (-1^5) * 5! ¡* 25!

¡Así que (-1^5) * 5! * 25! es congruente con (-1 mod p)

Ya casi estamos, ¡pues necesitamos 5! * 25!, no 5! ¡* 25! * -1

dividiendo cada lado por -1, tenemos que ¡5! * 25! es congruente con 1 (mod p)

A partir de esto, es obvio que el resto es 1.