Teorema de Wilson

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En matemáticas, el teorema de Wilson es un teorema clásico relacionado con la divisibilidad. Se enuncia de la siguiente manera:

Si p es un número primo, entonces (p − 1)! ≡ -1 (mod p)


John Wilson


El recíproco también es cierto, por lo que puede afirmarse que un número n>1 es primo si y sólo si (n− 1)! ≡ − 1 (mod n). Sin embargo, sólo la implicación de arriba es conocida como teorema de Wilson (o Congruencia de Wilson).

Historia[editar]

Fue atribuido a John Wilson por Edward Waring, quien en 1770 realizó un comentario acerca de que Wilson había dejado anotado el resultado. No hay evidencia de que Wilson hubiese hallado la demostración, y ciertamente Waring no la halló. Fue Lagrange quien, en 1771 dio la primera demostración. Con toda propiedad, el teorema debe ser atribuido a Abu 'Ali al-Hasan ibn al-Haytham, llamado en Occidente Alhazen, quien lo formuló a comienzos del siglo XI.

Ejemplo[editar]

La siguiente tabla muestra los valores de n desde 2 a 30, (n-1)!, Y el resto al (n-1)! se divide por n. (El resto cuando m se divide por n se escribe m mod n). El color de fondo es de color rosa para los valores primos de n, color verde claro para valores compuestos.

Tabla de resto módulo n
n (n-1)! (n-1)!\ \bmod\ n
2 1 1
3 2 2
4 6 2
5 24 4
6 120 0
7 720 6
8 5040 0
9 40320 0
10 362880 0
11 3628800 10
12 39916800 0
13 479001600 12
14 6227020800 0
15 87178291200 0
16 1307674368000 0
17 20922789888000 16
18 355687428096000 0
19 6402373705728000 18
20 121645100408832000 0
21 2432902008176640000 0
22 51090942171709440000 0
23 1124000727777607680000 22
24 25852016738884976640000 0
25 620448401733239439360000 0
26 15511210043330985984000000 0
27 403291461126605635584000000 0
28 10888869450418352160768000000 0
29 304888344611713860501504000000 28
30 8841761993739701954543616000000 0

Demostración[editar]

Usando aritmética modular[editar]

De derecha a izquierda[editar]

Por contradicción. Suponga que  p \geq 2, (p-1)!\equiv (p-1) \ \mbox{mod}\ p\, y  p \, no es primo. Dado que  p \, no es primo, existe  a \in \{1,\ldots,p-1\}.\, tal que  a\,|\,p\,, es decir,  \mbox{MCD}\ (a, p) \neq 1. Además, no es difícil ver que (p-1)!=a\cdot (a-1)!\cdot \prod_{i=a+1}^{p-1}i.\,. Si escribimos  \alpha=(a-1)!\cdot \prod_{i=a+1}^{p-1}i.\, entonces, a partir de la hipótesis se concluye que  a \cdot \alpha \equiv (p-1)\ \mbox{mod}\ p.\,

Además, aprovechando el hecho de que  (p-1) \equiv -1 \ \mbox{mod}\ p\, se deduce que  (p-1)^2 \equiv 1 \ \mbox{mod}\ p\, y luego  ( a \cdot \alpha )^2 \equiv (p-1)^2 \equiv 1 \ \mbox{mod}\ p.\, Vemos que  \ a^2 \, tiene inverso en módulo  \ p\,, lo cual no puede ser cierto pues  \mbox{MCD}\ (a^2, p) \neq 1.\, Esta contradicción proviene de suponer que  p \, no es primo.

De izquierda a derecha[editar]

Sea  p \geq 2 un número primo. Dado que  p es primo, entonces para todo  a \in \{1, \ldots, p-1 \} se tiene que  \mbox{MCD}\ (a, p) = 1\, y entonces cada  a \in \{1, \ldots, p-1 \} tiene un único inverso módulo  p\, en el conjunto  a \in \{1, \ldots, p-1 \}.

Para ver que es único, supongamos  b, c \in \{1,\ldots, p-1\} tales que  b > c, a\cdot b \equiv\ 1\ \mbox{mod}\ p y  a\cdot c \equiv\ 1\ \mbox{mod}\ p . Luego se tiene  a\cdot b \cdot c \equiv\ c\ \mbox{mod}\ p , de donde   b \equiv\ c\ \mbox{mod}\ p.

De lo anterior se colige que  p\,|\, (b-c). Además, del supuesto se tiene que  (b-c) \in  \{1, \ldots, p-1 \}. Sin embargo, para cada  a \in \{1, \ldots, p-1 \} se tiene que  \mbox{MCD}\ (a, p) = 1\,, es decir,  p \not | (b-c). , lo cual es una contradicción. Lo mismo ocurre si  c > b .\, Vemos entonces que  b=c , lo que garantiza la unicidad.

Ahora, es claro que  1, (p-1) son inversos de sí mismos en módulo  p , y para todo otro elemento en  \{1,\ldots, p-1\} se tiene un inverso en módulo  p diferente al de los demás (por la unicidad). Así, podemos agrupar cada elemento con su inverso, de modo que  \prod_{i=2}^{p-2} i \equiv\ 1\ \mbox{mod}\ p .

De aquí, multiplicando a ambos lados por  (p-1) se concluye  (p-1)!\equiv\ (p-1)\ \mbox{mod}\ p , lo que finaliza la demostración.

Usando teoría de grupos[editar]

Esta demostración usa el hecho de que si p es un número primo, entonces el conjunto de números G = (Z/pZ)× = {1, 2, ... p − 1} forma un grupo bajo la multiplicación. Esto significa que para cada elemento a de G, hay un único inverso multiplicativo b en G tal que ab ≡ 1 (mod p). Si ab (mod p), entonces a2 ≡ 1 (mod p), que se puede factorizar en a2 − 1 = (a + 1)(a − 1) ≡ 0 (mod p), y puesto que p es primo, entonces a ≡ 1 o −1 (mod p), por ejemplo a = 1 o a = p − 1.

En otras palabras, 1 y p − 1 son cada uno su propio inverso, pero para cualquier otro elemento de G hay un inverso, también en G, así que si tomamos todos los elementos de G por parejas y los multiplicamos todos ellos juntos, el producto será igual a −1 (módulo p). Por ejemplo, si p = 11, tenemos que:

10! = 1(10)(2 \cdot 6)(3 \cdot 4)(5 \cdot 9)(7 \cdot 8) \ \equiv\ -1\ (\mbox{mod}\ 11).\,

Las propiedades conmutativas y asociativas son usadas en el procedimiento de arriba. Todos los elementos en el producto anterior serán de la forma g g −1 ≡ 1 (mod p) excepto 1 (p − 1), que están al principio del producto.

Si p = 2, el resultado es trivial e inmediato.

Para demostrar el inverso del teorema (ver siguiente sección), supóngase que la congruencia se cumple para un número compuesto n, nótese entonces que n tiene un divisor propio d con 1 < d < n. Claramente, d divide a (n − 1)! pero por la congruencia, d también divide a (n − 1)! + 1, así que d divide a 1, con lo que se llega a una contradicción.

Usando polinomios[editar]

Sea p un número primo. Consideremos el polinomio

g(x)=(x-1)(x-2) \cdots (x-(p-1)).\,

Recordemos que si f(x) es un polinomio no nulo de grado d sobre un cuerpo F, entonces f(x) tiene un máximo de d raíces en F, y recordemos que el conjunto de todos los restos módulo un primo, con las operaciones de suma y multiplicación, es un cuerpo. Ahora, siendo g(x)

f(x)=g(x)-(x^{p-1}-1).\,

Puesto que los coeficientes de mayor orden se cancelan, f(x) es un polinomio de grado p − 2 como mucho. Por tanto, si tomamos restos módulo p, f(x) tendrá a lo sumo p − 2 raíces módulo p. Sin embargo, a la vista de la definición de f(x), del pequeño teorema de Fermat se sigue que cada elemento 1, 2, ..., p − 1 es una raíz de f(x) (por lo que, a fortiori, es una raíz de f(x) módulo p). Esto es imposible a menos que f(x) sea idénticamente cero módulo p, esto es, a menos que cada coeficiente de f(x) sea divisible por p.

Dado que el término constante de f(x) es justamente (p − 1)! + 1,

Inverso[editar]

El inverso del teorema de Wilson dice que para cualquier número compuesto n > 5,

n divide a (n − 1)!.

Se deja el caso n = 4, para el cual 3! no es divisible por 4 (es únicamente divisible por 2).

En efecto, si q es un factor primo de n, de tal manera que n = qa, los números

1, 2, ..., n − 1

incluyendo a − 1 múltiplos de q. Por lo tanto, las potencias de q que dividen al factorial son al menos n/q − 1; y las potencias que dividen a n son a lo máximo

log n/log q.

La inecuación

log n/log qn/q − 1

se cumple en general, excepto para el caso q = 2 y n = 4.

Test de primalidad[editar]

El teorema de Wilson no se utiliza como test de primalidad en la práctica, ya que para calcular (n − 1)! modulo n para un número n grande es costoso (computacionalmente hablando), y se conocen tests más sencillos y rápidos.

Usando el teorema del Wilson, se tiene que para cada número primo p:

1\cdot 2\cdots (p-1)\ \equiv\ -1\ (\mbox{mod}\ p)
1\cdot(p-1)\cdot 2\cdot (p-2)\cdots n\cdot (p-n)\ \equiv\ 1\cdot (-1)\cdot 2\cdot (-2)\cdots n\cdot (-n)\ \equiv\  -1\ (\mbox{mod}\ p)

donde p = 2n + 1. Esto se convierte en

\prod_{j=1}^n\ j^2\ \equiv(-1)^{n+1}\ (\mbox{mod}\ p).

Así, la primalidad del número se determina mediante los residuos cuadráticos de p. Esto se puede usar de hecho para probar parte de otro famoso resultado: −1 es un cuadrado (residuo cuadrático) mod p si p ≡ 1 (mod 4). Para la suposición, p = 4k + 1 para algún entero k. Entonces, tomando n = 2k y sustituyendo, se concluye que:

\left( \prod_{j=1}^{2k}\ j \right)^{2} = \prod_{j=1}^{2k}\ j^2\ \equiv (-1)^{2k+1}\ = -1(\mbox{mod}\ p).

El teorema de Wilson ha sido utilizado para generar fórmulas para los primos, pero es demasido lento como para tener valor práctico.

Generalización[editar]

El teorema de Wilson se puede generalizar, como mostró Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae:


\prod_{1 \le a < n \atop (a,n)=1} \!\!a \ \equiv \ \left \{ \begin{matrix} -1\ (\mbox{mod }n) & \mbox{si } n=4,\;p^k,\;2p^k \\ \ \ 1\ (\mbox{mod }n) & \mbox{en otro caso} \end{matrix} \right.

donde p es un número primo impar, y k pertenece a los números naturales, es decir, k \in \left \{1,2,3,...\right \}. El teorema se generaliza más por el hecho de que en cualquier grupo abeliano finito, ya sea el producto de todos los elementos es la identidad, o precisamente hay un elemento a de orden 2. En este último caso, el producto de todos los elementos es igual a.

Véase también[editar]

Referencias[editar]

  • Reid, Constance (2006). From Zero to Infinity: What Makes Numbers Interesting. Massachusetts (USA): AK Peters. ISBN 1568812736.