Teorema de wilson

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Teorema en números primos

En álgebra y teoría de números, Teorema de Wilson declara que un número natural n ■ 1 es un número primo si y sólo si el producto de todos los enteros positivos menos que n es uno menos que un múltiple de n. Es decir (utilizando las notaciones de aritmética modular), el factorial $(n - 1)! = 1 times 2 times 3 times cdots times (n - 1)$ satisfizo

{displaystyle (n-1)! equiv ;-1{pmod {n}}}

exactamente cuando n es un número primo. En otras palabras, cualquier número n es un número primo si, y solo si, (n − 1)! + 1 es divisible por n.

Historia

Este teorema fue enunciado por Ibn al-Haytham (c. 1000 dC) y, en el siglo XVIII, por John Wilson. Edward Waring anunció el teorema en 1770, aunque ni él ni su alumno Wilson pudieron demostrarlo. Lagrange dio la primera prueba en 1771. Hay evidencia de que Leibniz también conocía el resultado un siglo antes, pero nunca lo publicó.

Ejemplo

¡Para cada uno de los valores de n de 2 a 30, la siguiente tabla muestra el número (n − 1)! y el resto cuando (n − 1)! se divide por n. (En la notación de la aritmética modular, el resto cuando m se divide por n se escribe m mod n.) El color de fondo es azul para valores prime de n, dorado para valores compuestos.

Table of factorial and its remainder modulo n
$n$	$(n-1)!$ (secuencia) A000142 en el OEIS)	$(n-1)! bmod n$ (secuencia) A061006 en el OEIS)
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	11240007277607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000	0
27	403291461126605635584000	0
28	10888869450418352160768000	0
29	304888344611713860501504000	28
30	88417619937397019545436000	0

Pruebas

Las demostraciones (para módulos primos) a continuación utilizan el hecho de que las clases de residuos módulo a número primo son un campo; consulta el artículo campo primo para obtener más detalles. El teorema de Lagrange, que establece que en cualquier campo un polinomio de grado n tiene como máximo n raíces, es necesario para todas las demostraciones.

Módulo compuesto

Si n es composite que es divisible por algún número primo q, donde 2 ≤ q ≤ n − 2. Porque... $q$ divideciones $n$ , vamos ${displaystyle n=qk}$ para algunos enteros $k$ . Supongamos por el bien de la contradicción que ()n - 1). eran congruentes con (modelo) n) donde N es composite. Entonces (n-1)! también sería congruente con −1 (modelo) qcomo ${displaystyle (n-1)!equiv -1 ({text{mod}} n)}$ implica que ${displaystyle (n-1)!=nm-1=(qk)m-1=q(km)-1}$ para algunos enteros $m$ que muestra (n-1)! ser congruente con -1 (mod q). Pero...n- 1). (modelo)q) por el hecho de que q es un término en (n-1)! haciendo (n-1)! un múltiplo de q. Ahora se llega a una contradicción.

De hecho, más es verdad. Con la única excepción de 4, donde 3! = 6 ≡ 2 (mod 4), si n es compuesto entonces (n − 1)! es congruente con 0 (mod n). La prueba se divide en dos casos: primero, si n se puede factorizar como el producto de dos números desiguales, n = ab, donde 2 ≤ a < b ≤ n − 2, entonces tanto a como b aparecerán en el producto 1 × 2 ×... × (n − 1) = (n − 1)! y (n − 1)! será divisible por n. Si n no tiene tal factorización, entonces debe ser el cuadrado de algún primo q, q > 2. Pero entonces 2q < q² = n, tanto q como 2q serán factores de (n − 1)!, y de nuevo n divide (n − 1)!.

Módulo primo

Prueba elemental

El resultado es trivial cuando p = 2, así que asume que p es un número primo impar, p ≥ 3. Dado que las clases de residuos (mod p) son un campo, cada a distinto de cero tiene un inverso multiplicativo único, a⁻¹. El teorema de Lagrange implica que los únicos valores de a para los que a ≡ a⁻¹ (mod p) son a ≡ ±1 (mod p) (porque la congruencia a² ≡ 1 puede tener como máximo dos raíces (mod p)). Por lo tanto, con la excepción de ±1, los factores de (p − 1)! se pueden organizar en pares disjuntos de manera que el producto de cada par sea congruente a 1 módulo p. Esto prueba el teorema de Wilson.

Por ejemplo, para p = 11, uno tiene

{displaystyle 10!=[(1cdot 10)]cdot [(2cdot 6)(3cdot 4)(5cdot 9)(7cdot 8)]equiv [-1]cdot [1cdot 1cdot 1cdot 1]equiv -1{pmod {11}}.}

Demostración usando el pequeño teorema de Fermat

De nuevo, el resultado es trivial para p = 2, así que supongamos que p es un número primo impar, p ≥ 3. Considere el polinomio

{displaystyle g(x)=(x-1)(x-2)cdots (x-(p-1)).}

g tiene un grado p − 1, término principal x ^{p − 1} y el término constante (p − 1)! . Sus raíces p − 1 son 1, 2,..., p − 1.

Ahora considere

{displaystyle h(x)=x^{p-1}-1.}

h también tiene el grado p − 1 y el término inicial x^{p − 1}. Módulo p, el pequeño teorema de Fermat dice que también tiene las mismas raíces p − 1, 1, 2,..., p − 1.

Finalmente, considere

{displaystyle f(x)=g(x)-h(x).}

f tiene como máximo el grado p − 2 (ya que los términos principales se cancelan), y el módulo p también tiene la p − 1 raíces 1, 2,..., p − 1. Pero el teorema de Lagrange dice que no puede tener más de p − 2 raíces. Por lo tanto, f debe ser idénticamente cero (mod p), por lo que su término constante es (p − 1)! + 1 ≡ 0 (modificación p). Este es el teorema de Wilson.

Demostración usando los teoremas de Sylow

Es posible deducir el teorema de Wilson de una aplicación particular de los teoremas Sylow. Vamos p Sé un primo. Es inmediato deducir que el grupo simétrico $S_p$ tiene exactamente $(p-1)!$ elementos de orden p, a saber p- ciclos $C_p$ . Por otro lado, cada Sylow p- Subgrupo en $S_p$ es una copia de $C_p$ . De ahí que siga que el número de Sylow p- Subgrupos $n_p=(p-2)!$ . El tercer teorema de Sylow implica

(p-2)!equiv 1{pmod p}.

Multiplicar ambos lados por (p − 1) da

(p-1)!equiv p-1equiv -1{pmod p},

es decir, el resultado.

Aplicaciones

Pruebas de primalidad

En la práctica, el teorema de Wilson es inútil como prueba de primalidad porque calcular (n − 1)! módulo n para grandes n es computacionalmente complejo, y se conocen pruebas de primalidad mucho más rápidas (de hecho, incluso la división de prueba es considerablemente más eficiente).

Usado en la otra dirección, para determinar la primalidad de los sucesores de factoriales grandes, es de hecho un método muy rápido y efectivo. Esto es de utilidad limitada, sin embargo.

Residuos cuadráticos

Usando el teorema de Wilson, para cualquier primo impar p = 2m + 1, podemos reorganizar el lado izquierdo de

{displaystyle 1cdot 2cdots (p-1) equiv -1 {pmod {p}}}

{displaystyle 1cdot (p-1)cdot 2cdot (p-2)cdots mcdot (p-m) equiv 1cdot (-1)cdot 2cdot (-2)cdots mcdot (-m) equiv -1{pmod {p}}.}

{displaystyle prod _{j=1}^{m} j^{2} equiv (-1)^{m+1}{pmod {p}}}

{displaystyle (m!)^{2}equiv (-1)^{m+1}{pmod {p}}.}

pppkkmkm²p

Fórmulas para números primos

El teorema de Wilson se ha utilizado para construir fórmulas para números primos, pero son demasiado lentos para tener valor práctico.

Función gamma P-ádica

El teorema de Wilson permite definir la función gamma p-ádica.

Gauss' generalización

La generalización de Gauss del Teorema de Wilson afirma que si $n$ es cuatro, un poder primitivo impar, o dos veces un poder primitivo impar, entonces el producto de enteros relativamente primos menos de sí añadir uno es divisible por $n$ . Va más allá de decir que de lo contrario, el mismo subtracto de producto es divisible por $n$ .

Para indicar la generalización de Gauss del teorema de Wilson, utilizamos la función totient de Euler, denotada ${displaystyle varphi (n)}$ , que se define como el número de números enteros positivos menos o igual a $n$ que también son relativamente primos con $n$ . Vamos a llamar a tales números ${displaystyle a_{i}}$ , donde ${displaystyle gcd(a_{i},n)=1}$ .

Gauss demostró haber dado un primo extraño $p$ y algunos enteros $0}" xmlns="http://www.w3.org/1998/Math/MathML">α α ■0{displaystyle alpha œ0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/edd4f784b6e8bb68fa774213ceacbab2d97825dc" style="vertical-align: -0.338ex; width:5.749ex; height:2.176ex;"/>$ , entonces

{displaystyle prod _{k=1}^{varphi (n)}!!a_{k} ={begin{cases}-1{pmod {n}}&{text{if }}n=4,;p^{alpha },;2p^{alpha }\;;,1{pmod {n}}&{text{otherwise}}end{cases}}}

Primero, veamos que esta es la prueba de casos $2}" xmlns="http://www.w3.org/1998/Math/MathML">n■2{displaystyle n confiado2}2}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/44e71ac55b9fbf1e9f341b946cda63d61d3ef2cd" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;"/>$ , ya que los resultados son triviales para ${displaystyle n={1,2}}$ .

Para todos ${displaystyle a_{i}}$ , sabemos que hay algunos ${displaystyle a_{j}}$ , donde ${displaystyle ineq j}$ y ${displaystyle gcd(a_{j},n)=1}$ , tal que ${displaystyle a_{i}a_{j}=1}$ . Esto nos permite emparejar cada uno de los elementos junto con su inverso. Nos quedamos ahora con ${displaystyle a_{i}}$ siendo su propio inverso. Así que en otras palabras ${displaystyle a_{i}}$ es una raíz de ${displaystyle f(x)=x^{2}-1}$ dentro ${displaystyle mathbb {Z} /nmathbb {Z} }$ , y ${displaystyle f(x)=(x-1)(x+1)}$ , en el anillo polinomio ${displaystyle mathbb {Z} /nmathbb {Z} [X]}$ . Si ${displaystyle a_{i}}$ es una raíz, sigue que ${displaystyle n-a_{i}}$ es también una raíz. Nuestro objetivo es demostrar que el número de raíces es divisible por cuatro, a menos que sea ${displaystyle n=4,n=p^{alpha }}$ , o ${displaystyle n=2p^{alpha }}$ .

Consideremos ${displaystyle n=2}$ . Entonces notamos que tenemos una raíz desde entonces ${displaystyle 1equiv -1{pmod {2}}}$ .

Considerar ${displaystyle n=4}$ . Entonces, está claro que hay dos raíces, específicamente, ${displaystyle xequiv 1{pmod {4}}}$ y ${displaystyle xequiv -1{pmod {4}}}$ .

Di. ${displaystyle n=p^{alpha }}$ . Otra vez está claro que hay dos soluciones.

Ahora consideramos $2}" xmlns="http://www.w3.org/1998/Math/MathML">n=2β β ,β β ■2{displaystyle n=2^{beta },beta2}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/deba90b8fd2c71d39e94fc29ad7cef0381754c7a" style="vertical-align: -0.671ex; width:13.457ex; height:3.009ex;"/>$ . Si uno de los factores ${displaystyle f(x)}$ es divisible por 2, así es el otro. Tome el factor ${displaystyle (x+1)}$ ser divisible por ${displaystyle 2^{1}}$ . Entonces, sigue que hay 4 raíces distintas ${displaystyle f(x)}$ , a saber ${displaystyle xequiv 1{pmod {n}}}$ , ${displaystyle xequiv 1+2^{beta -1}{pmod {n}}}$ , ${displaystyle xequiv -1{pmod {n}}}$ , y ${displaystyle xequiv -1-2^{beta -1}{pmod {n}}}$ , cuando $2}" xmlns="http://www.w3.org/1998/Math/MathML">n=2β β ,β β ■2{displaystyle n=2^{beta },beta2}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/deba90b8fd2c71d39e94fc29ad7cef0381754c7a" style="vertical-align: -0.671ex; width:13.457ex; height:3.009ex;"/>$ .

Finalmente, vamos a ver el caso general donde ${displaystyle n=2^{beta }p_{1}{^{gamma _{1}}}p_{2}{^{gamma _{2}}}dots p_{k}{^{gamma _{k}}}}$ . Encontramos 2 raíces ${displaystyle f(x)}$ sobre cada uno ${displaystyle mathbb {Z} /2^{beta }mathbb {Z} }$ y ${displaystyle mathbb {Z} /p_{r}^{gamma _{r}}mathbb {Z} }$ , excepto cuando $2}" xmlns="http://www.w3.org/1998/Math/MathML">β β ■2{displaystyle beta >2}2}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d3b1d933041e4bc4f80449e3f36c922351881e74" style="vertical-align: -0.671ex; width:5.593ex; height:2.509ex;"/>$ . Usando el teorema del resto chino, encontramos que cuando ${displaystyle n}$ no es divisible por 2, tenemos un total de ${displaystyle 2^{k}}$ soluciones de ${displaystyle f(x)}$ . Sumas ${displaystyle beta =1}$ , dentro ${displaystyle mathbb {Z} /2mathbb {Z} }$ , tenemos una raíz, así que todavía tenemos un total de ${displaystyle 2^{k}}$ soluciones. Cuando ${displaystyle beta =2}$ , tenemos 2 raíces en ${displaystyle mathbb {Z} /4mathbb {Z} }$ , así que hay un total de ${displaystyle 2^{k+1}}$ raíces de ${displaystyle f(x)}$ . Para todos los casos $2}" xmlns="http://www.w3.org/1998/Math/MathML">β β ■2{displaystyle beta >2}2}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d3b1d933041e4bc4f80449e3f36c922351881e74" style="vertical-align: -0.671ex; width:5.593ex; height:2.509ex;"/>$ , hay 4 raíces en ${displaystyle mathbb {Z} /2^{beta }mathbb {Z} }$ con un total de ${displaystyle 2^{k+2}}$ soluciones. Esto muestra que el número de raíces son divisibles por 4, a menos que ${displaystyle n=4,n=p^{alpha }}$ , o ${displaystyle n=2p^{alpha }}$ .

Di. ${displaystyle a_{i}}$ es una raíz de ${displaystyle f(x)}$ dentro ${displaystyle mathbb {Z} /nmathbb {Z} }$ . Entonces... ${displaystyle a_{i}(n-a_{i})=-a_{i}^{2}=-1}$ . Así que, si el número de raíces de ${displaystyle f(x)}$ es divisible por 4, entonces podemos decir el producto de las raíces si 1. De lo contrario, podemos decir que el producto es -1. Así podemos concluir que

${displaystyle prod _{k=1}^{varphi (n)}!!a_{k} ={begin{cases}-1{pmod {n}}&{text{if }}n=4,;p^{alpha },;2p^{alpha }\;;,1{pmod {n}}&{text{otherwise}}end{cases}}}$ .

Contenido relacionado

Más resultados...