noticias y última hora

El teorema de Wilson

Introducción

El teorema de Wilson es un resultado de teoría de números relacionado con la primalidad de un número entero positivo. Fue atribuido a John Wilson por su profesor Edward Waring. Éste último comentó que Wilson había dejado anotado este resultado en un cuaderno pero que no lo había demostrado (os suena esta historia, ¿verdad?). El propio Waring tampoco pudo hacerlo y tuvo que ser Lagrange en 1771 quien dio la primera prueba.

En esta entrada vamos a dar una sencilla demostración que utiliza propiedades más o menos elementales de teoría de números.

El teorema de Wilson

Teorema: Sea p un número entero mayor que 1. Entonces p es primo si y sólo si

(p-1)! \equiv -1 \; (mod \; p)

Demostración:

De forma sencilla puede comprobarse que este resultado es cierto para p=2 y para p=3. Supongamos entonces que p > 3.

Para demostrar la implicación de derecha a izquierda (si (p-1)! \equiv -1 \; (mod \; p) entonces p es primo) vamos a demostrar su contrarrecíproco, es decir, vamos a demostrar que si p es compuesto entonces no se cumple esa igualdad:

\Longleftarrow) Supongamos que p es compuesto. Entonces sus divisores positivos se encuentran entre los enteros 1,2, \ldots ,p-1. Por tanto es claro que mcd ((p-1)!,p >1$. En particular p tiene algún divisor d > 1.

Supongamos ahora que el resultado es cierto, es decir, que (p-1)! \equiv -1 \; (mod \; p). Como d divide a p entonces d también divide a (p-1)! y, por la congruencia, d divide a (p-1)!+1. Por tanto d divide a 1, hecho que nos lleva a una contradicción con la condición d >1. En consecuencia la implicación de derecha a izquierda es cierta.

\Longrightarrow) Supongamos ahora que p es primo. Por tanto todos los enteros 1,2, \ldots , p-1 son primos relativos con p. Por otra parte ese conjunto de números forma un grupo con la multiplicación, en concreto el grupo \mathbb{Z}_p de los enteros módulo p (en realidad, al ser p primo ese conjunto es un cuerpo, pero ahora sólo nos interesa su condición de grupo con esa operación). Entre otras cosas eso significa que para todo a \in \mathbb{Z}_P existe un único b \in \mathbb{Z}_p tal que a \cdot b \equiv 1 \; (mod \; p). También por ser p primo se tiene que a=b si y sólo si a=1 ó a=p-1, es decir, 1 y p-1 son inversos el uno del otro. Por tanto para cualquier otro elemento del grupo distinto de éstos se tiene que su inverso también es distinto de éstos. En consecuencia podemos agrupar el resto de elementos por parejas (cada uno junto a su inverso) para que se cumpla lo siguiente:

2 \cdot 3 \cdot \ldots \cdot p-2 \equiv 1 \; (mod \; p)

Esto es, (p-2)! \equiv 1 \; (mod \; p). Multiplicando ahora a ambos lados por (p-1) y utilizando que p-1 \equiv -1 \; (mod \; p) obtenemos el resultado buscado.

Utilidad del teorema

El teorema tiene principalmente valor teórico ya que en la práctica es relativamente complicado calcular (p-1)! para valores grandes de p. Por eso generalmente antes que este teorema suelen usarse otros tests de primalidad, como el pequeño teorema de Fermat.

De todas formas es útil para generar a partir de él fórmulas de primos, es decir, fórmulas que generar números primos (en Gaussianos ya vimos algo así con los números primos pseudogemelos). Aunque, como en el caso anterior, suelen ser fórmulas poco prácticas por lo costoso que es calcular (p-1)! para p muy grande.

De todas formas, como dije antes, la belleza del resultado reside en su valor teórico. Y algunas, en ocasiones, tenemos suficiente con ello.

Fuentes:


Posts aleatorios

Autor: ^DiAmOnD^  |  Publicado el 20 de October de 2008
Categorías: Demostraciones, Números enteros, Números primos, Teoremas  |  Imprime este post Imprime este post

Sin comentarios

  1. Trackback | 20 Oct, 2008

    Bitacoras.com

  2. dude | 21 de October de 2008 | 03:44

    Este ya lo habia visto en la escuela, aunque no sabia que era “un si y solo si”. Chido teorema.
    Ok saludos

  3. Jonas Castillo Toloza | 22 de October de 2008 | 23:25

    Creì haber demostrado que no existen los mal llamados “nùmeros primos pseudogemelos”, sòlo existen nùmeros primos n, m que cumplen que (n*m + 2) divide (n^2 + m^2), claro que cuando m = n+2 entonces (n^2 + m^2)/(n*m + 2) = siempre un entero(siempre es 2).
    Estos primos n y m cuando su diferencia es mayor que 2 son los mal llamados primos seudogemelos.

    He hallado esta fòrmula para comprobar primos gemelos

    n y (n+2) son primos gemelos si y solamente si
    n(n+2) divide a (n-2)(n-1)! – 2.

    Fàcil de demostrar por medio del teorema de Wilson.
    Por el momento dejo la demostraciòn a cargo de algun gaussiano.

Comentarios cerrados.