Teorema de Wilson

Lo primero será establecer el signo de congruencia. Ya hace días que vengo usando esto, no se parece mucho pero no he encontrado otro que me guste

a ~: b (mod m)

Luego el ~: es el símbolo de congruente.

El teorema de Wilson dice que si p es primo entonces

(p-1)! ~: -1 (mod p)

como 59 es primo tenemos

58! ~: -1 (mod 59)

58·57·56·55·54·53! ~: -1 (mod 59)

Una de las propiedades de las congruencias dice,

a ~: b mod n ==> ac ~: bc (mod n)

fácil de demostrar

a=b+kn

ac = bc + knc

como knc es múltiplo de n se tiene

ac ~: bc (mod n)

Entonces los números 58,57,56,55,54 los sustituimos por otros congruentes que permiten operar más fácilmente

58 ~: -1 (mod 59)

57 ~: -2 (mod 59)

...

54 ~: -5 (mod 59)

La vieja congruencia

58·57·56·55·54·53! ~: -1 (mod 59)

Se transforma en

(-1)(-2)(-3)(-4)(-5)53! ~: -1 (mod 59)

-120·53! ~: -1 (mod 59)

Vamos a sumar 2·59·53! En la izquierda, se mantiene la congruencia porque sumamos un múltiplo de 59. O sea, sumamos 118·53!

-2·53! ~: -1 (mod 59)

2·53! ~: 1 (mod 59)

Y ahora consiste en quedarnos a la izquierda con 53! Se podría usar el algoritmo de extendido de Euclides para resolver la congruencia poniendo x donde el 53!

2x ~: 1 (mod 59)

Pero le tengo alergia al algoritmo ese.

Lo que haré es mediante algún producto y restas dejar ese 53! En la izquierda

Y sale a la primera, si multiplico por 30 me queda

60·53! ~: 30 (mod 59)

Le resto 59·53!

53! ~: 30 (mod 59)

Luego 30 es el residuo de 53! Módulo 59.

Y eso es todo.