Teorema de Wilson

Avatar de Usuario
3,14

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Medalla de Plata-OFO 2018
FOFO 9 años - Jurado-FOFO 9 años
Mensajes: 457
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 6
Nivel: Exolímpico

Teorema de Wilson

Mensaje sin leer por 3,14 »

El teorema de Wilson, que constituye un test determinístico de primalidad (no usado debido a la dificultad computacional que presenta) establece que:
Un número [math] es primo sí y solo sí [math]

Demostración:
Spoiler: mostrar
Veamos que ocurre si [math]. Si [math] fuera compuesto, entonces tendría un factor primo que lo divide, digamos [math]. Como [math] se encuentra en los factores de [math], sigue que [math] y [math], lo cual es imposible. Por lo tanto [math] es primo.
Ahora demostremos que cualquier primo cumple la condición. Para ello veamos la clase de congruencia de [math] módulo [math], siendo éste último un número primo.
En este factorial, todos los restos no nulos módulo n cuyo inverso multiplicativo no es el mismo resto, se anulan. Entonces debemos buscar aquellos restos que coinciden con su inverso. Llamando [math] a la clase que se anula a sí misma, tenemos que:
[math]
[math]
[math]
Como [math] es primo, ocurre que [math] o [math], en cuyo caso los valores posibles de a son 1 y -1 mod n. En el caso del uno, este no contribuyen con el producto, mientras que el -1 sí. Quedaría que:
[math]
De donde se desprende inmediatamente lo enunciado.
[math]
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Teorema de Wilson

Mensaje sin leer por Turko Arias »

Che el post este ya está, fijate en el archivo para no repetir la teoría... http://omaforos.com.ar/viewtopic.php?f=7&t=235
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
3,14

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Medalla de Plata-OFO 2018
FOFO 9 años - Jurado-FOFO 9 años
Mensajes: 457
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 6
Nivel: Exolímpico

Re: Teorema de Wilson

Mensaje sin leer por 3,14 »

Disculpas, lo busqué y no lo encontré
[math]
Responder