Teorema de Wilson

El teorema de Wilson establece que un número natural p > 1 es un número primo si y solo si

    (p - 1) ! ≡  -1   mod p 
OR  (p - 1) ! ≡  (p-1) mod p
 

Ejemplos:

p  = 5
(p-1)! = 24
24 % 5  = 4

p  = 7
(p-1)! = 6! = 720
720 % 7  = 6

¿Como funciona?
1) Podemos verificar rápidamente el resultado de p = 2 o p = 3.

2) Para p > 3: Si p es compuesto, entonces sus divisores positivos están entre los enteros 1, 2, 3, 4, … , p-1 y es claro que mcd((p-1)!,p) > 1, por lo que no podemos tener (p-1)! = -1 (mod p).

3) Ahora veamos cómo es exactamente -1 cuando p es un número primo. Si p es primo, entonces todos los números en [1, p-1] son ​​primos relativos a p. Y para cada número x en el rango [2, p-2], debe existir un par y tal que (x*y)%p = 1. Entonces

    [1 * 2 * 3 * ... (p-1)]%p 
 =  [1 * 1 * 1 ... (p-1)] // Group all x and y in [2..p-2] 
                          // such that (x*y)%p = 1
 = (p-1)

¿Cómo puede ser útil?
Considere el problema de calcular el factorial bajo el módulo de un número primo que está cerca del número de entrada, es decir, queremos encontrar el valor de “n! % p” tal que n < p, p es un primo y n es cercano a p. Por ejemplo (25! % 29). Por el teorema de Wilson, sabemos que 28! es -1. Así que básicamente necesitamos encontrar [(-1) * inverse(28, 29) * inverse(27, 29) * inverse(26) ] % 29. La función inversa inverse(x, p) devuelve el inverso de x bajo módulo p (Ver esto para más detalles).

Ver esto para más aplicaciones del teorema de Wilson.

Referencias:
https://en.wikipedia.org/wiki/Wilson’s_theorem
https://primes.utm.edu/notes/proofs/Wilsons.html

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.