Teorema de wilson

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 1 de octubre de 2021; las comprobaciones requieren 3 ediciones .

El teorema de Wilson es un teorema de teoría de números que establece que

Si es un número primo, entonces el número es divisible por . Por el contrario, si es divisible por , entonces es un número primo. $pags$ $(p-1)!+1$ $pags$ $(p-1)!+1$ $pags$ $pags$

Este teorema es principalmente de importancia teórica, ya que el factorial es bastante difícil de calcular. Es más fácil de calcular , por lo que las pruebas elementales que determinan si un número es primo se basan en el teorema de Fermat , no en el teorema de Wilson. Por ejemplo, es probable que el número primo más grande encontrado usando el teorema de Wilson sea 1099511628401, e incluso con un enfoque de cálculo optimizado, tomará alrededor de un día de cálculos en procesadores SPARC , y los números con decenas de miles de dígitos pasan la prueba de primalidad usando El teorema de Fermat en menos de una hora. Pero, a diferencia del pequeño teorema de Fermat, el teorema de Wilson es tanto una condición necesaria como suficiente para la simplicidad. $(p-1)!$ $a^{p-1}$ $p!$

Historia

Este teorema fue enunciado por primera vez por Ibn al-Haytham alrededor del año 1000 dC, [1] y en 1770 Waring formuló este teorema en su Meditationes Algebraicae publicado en Cambridge, da el teorema de Wilson sin demostración. Según él, el teorema pertenece a su alumno Wilson . Solo publicó la demostración del teorema en la tercera edición de sus Meditationes en 1782. La primera prueba del teorema de Wilson fue dada en 1771 por Lagrange [2] .

Finalmente, Euler en Opusc. Analyt , volumen 1, pág. 329 dio una prueba, Gauss generalizó el teorema de Wilson al caso de un módulo compuesto. Hay evidencia de que Leibniz conocía el resultado un siglo antes, pero nunca lo publicó.

Ejemplo

La tabla contiene valores para p de 2 a 31, así como el resto de la división por p (el resto de la división de m por p se denota como m mod p ). Los números primos están resaltados en verde . $(p-1)!$ $(p-1)!$

Tabla de residuos módulo n

$pags$	$(p-1)!$	$(p-1)!{\bmod {p}}$
2	una	una
3	2	2
cuatro	6	2
5	24	cuatro
6	120	0
7	720	6
ocho	5040	0
9	40320	0
diez	362880	0
once	3628800	diez
12	39916800	0
13	479001600	12
catorce	6227020800	0
quince	87178291200	0
dieciséis	1307674368000	0
17	20922789888000	dieciséis
Dieciocho	355687428096000	0
19	6402373705728000	Dieciocho
veinte	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	155112100433330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
treinta	8841761993739701954543616000000	0
31	265252859812191058636308480000000	treinta

Prueba

Adecuación

Sea p primo.

Método 1

Considere . El conjunto de clases de residuos distintos de cero módulo p módulo de multiplicación es un grupo , y luego es el producto de todos los elementos del grupo . Como es un grupo, entonces para cada uno de sus elementos existe un único elemento inverso . La correspondencia divide el grupo en clases: si (que es equivalente a , es decir , ya que una ecuación de segundo grado no puede tener más de dos soluciones), entonces la clase contiene un elemento , de lo contrario la clase consta de dos elementos - . Entonces, si una clase contiene un elemento , entonces el producto de todos sus elementos es igual , y si la clase contiene 2 elementos, entonces el producto de todos sus elementos es igual a 1. Ahora, en el producto, agrupamos los elementos por clases, todos los productos por clases de 2 elementos son simplemente iguales a 1: $(p-1)!$ ${\mathbb {Z}}_{p}^{{\veces}}$ $(p-1)!$ ${\mathbb {Z}}_{p}^{{\veces}}$ ${\mathbb {Z}}_{p}^{{\veces}}$ $a$ $a^{{-1}}:aa^{{-1}}\equiv 1{\pmod p}$ $a\a^{{-1}}$ $a=a^{{-1}}$ $un^{2}=1$ $a\en\{1,-1\}$ $a$ $\{a,a^{{-1}}\}$ $a$ $a$ $(p-1)!$

(p-1)!\equiv \prod \limits _{{{a^{2}=1}}a\cdot \prod \limits _{{{a^{2}\neq 1}}a\equiv \prod \ límites _{{a^{2}=1}}a\equiv 1\cdot (-1)\equiv -1{\pmod p}.

■

Método 2

El grupo es cíclico , es decir, hay un elemento tal que para cualquier elemento existe tal que . Como tiene un elemento, recorre los valores desde 0 hasta cuando recorre todo el grupo de residuos. Después ${\mathbb {Z}}_{p}^{{\veces}}$ $gramo$ $a$ $k$ $a=g^{k}$ ${\mathbb {Z}}_{p}^{{\veces}}$ $p-1$ $k$ $p-1$ $a$

(p-1)!\equiv g^{1}g^{2}\ldots g^{{p-1}}\equiv g^{{1+2+\ldots +(p-1)}}= g^{{{\frac {p-1}{2}}p}}\equiv (-1)^{p}\equiv -1{\pmod p}.

■

Método 3

${\mathbb {Z}}_{p}^{{\veces}}$ - campo , por lo tanto, en él tiene lugar el teorema de Lagrange , es decir, el polinomio de grado no tiene más que raíces. Considere polinomios y . Ambos polinomios tienen raíces (porque esto se obtiene por el pequeño teorema de Fermat ), los grados de los polinomios son iguales , los coeficientes principales son los mismos. Entonces el polinomio tiene al menos las mismas raíces, pero su grado es como máximo . Por tanto, según el teorema de Bezout, es idénticamente igual a cero, es decir, para todos será , en particular , lo que equivale a . Obtenemos la afirmación del teorema para , ya que es par y por lo tanto . ■ $norte$ $norte$ $f(x)=(x-1)\ldots (x-(p-1))$ $g(x)=x^{{p-1}}-1$ $1,2,\ldots,p-1$ $g(x)$ $p-1$ $h(x)=f(x)-g(x)$ $p-1$ $p-2$ $h(x)$ $X$ $f(x)=g(x)$ $f(0)=g(0)$ $(-1)^{{p-1}}(p-1)!\equiv -1{\pmod p}$ $pag>2$ $p-1$ $(-1)^{{p-1}}=1$

Necesitar

Si y es compuesto , entonces , y para , obtenemos . $pags$ ${\ estilo de visualización p \ neq 4}$ $(p-1)!\equiv 0{\pmod {p))$ ${\ estilo de visualización p = 4}$ $(4-1)!\equiv 2{\pmod 4}$

Prueba geométrica de suficiencia

Sea p un número primo. Volvamos a numerar los vértices de un p -gon regular en el orden de atravesar el contorno: 1, 2, 3, ..., p . Si los conectamos por diagonales en serie a través de uno, luego a través de dos, a través de tres, etc., entonces además del polígono regular 123..., también obtenemos ( p − 2) polígonos 135..., 147.. ., 159.. etc. Estos ( p − 1) polígonos son idénticos por parejas, ya que uniendo los vértices por k y por ( p − k − 2) obtenemos polígonos idénticos. El número de polígonos regulares diferentes obtenidos de esta forma es ; $(p-1)/2$
Si conectamos los vértices en algún otro orden, por ejemplo en el orden 13245..., entonces obtenemos un polígono irregular; rotando este polígono de modo que los números de sus vértices sean reemplazados por los siguientes números en orden (el número p es reemplazado por uno), obtenemos p polígonos irregulares. En el ejemplo anterior, estos serán los polígonos 13245..., 24356..., 35467..., ..., 2134... Si formamos todos los polígonos irregulares posibles de esta forma, entonces su número será un múltiplo de p , pero, como en el caso de los polígonos regulares, son dos idénticos; son dos sucesiones de vértices, directa e inversa, que dan un mismo polígono;
Si hacemos todas las permutaciones posibles ( p − 1) de los vértices 23... en la secuencia de vértices 123... , entonces obtenemos todos los polígonos posibles (regulares e irregulares); su número será ; volverán a ser idénticos en pares, por lo que su número real es ; $1\cdot 2\cdot 3\cdots (p-1)=(p-1)!'$ ${\ estilo de visualización (p-1)!/2}$
Comparando los resultados de los puntos 1 y 3, vemos que el número de polígonos irregulares será igual a: . Desde el punto 2, este número debe ser divisible por p ; por lo tanto ( p − 1)! + 1 múltiplo p .: ■ $1/2(p-1)!-1/2(p-1)=1/2((p-1)!+1-p)$

Aplicación

Usamos el teorema de Wilson

1\cdot 2\cdots (p-1)\equiv -1{\pmod {p)).

Para un primo impar p = 2 m + 1 , obtenemos

1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (pm)\equiv 1\cdot (-1)\cdot 2\cdot (-2)\cdots m \cdot (-m)\equiv -1{\pmod {p}}.

Como resultado

\prod_{j=1}^{m}j^{2}\equiv (-1)^{m+1}{\pmod {p)).

Podemos usar este hecho para probar un resultado bien conocido: para cualquier primo p tal que p ≡ 1 (mod 4), el número (−1) es un cuadrado ( residuo cuadrático ) mod p . De hecho, sea p = 4 k + 1 para alguna k natural . Entonces m = 2 k , por lo tanto

{\biggl (}\prod_{j=1}^{2k}\ j{\biggr)}^{2}=\prod_{j=1}^{2k}j^{2}\ equivalente (-1)^{2k+1}=-1{\pmod {p)).

El teorema de Wilson se usa para generar números primos, pero es demasiado lento para un uso práctico.

Generalización

Usando el teorema de Euler como ejemplo , intentemos generalizar el teorema de Wilson al caso p = n , donde n es un número natural arbitrario. ¡ Un simple cambio ( p − 1)! el producto n 1 n 2 ... n k de todos los números menores que n y primos relativos a n no pasa: en el caso de n = 8, este producto es 1 × 3 × 5 × 7 = 105, y 106 es no divisible por 8 Pero resulta que n 1 n 2 … n k + 1, o n 1 n 2 … n k − 1 es necesariamente divisible por n .

Considere el conjunto E n de números menores que n y primos relativos a n . Bajo el producto de dos elementos de este conjunto ab , nos referimos al resto de dividir el producto habitual ab por n . Está claro que si a , b pertenece a E n , entonces ab pertenece a E n . El conjunto E n con respecto a la operación de multiplicación es un grupo. A diferencia del caso en que n es primo, el grupo E n puede contener elementos que no son iguales a 1 y ( n − 1) tales que su cuadrado es igual a 1: por ejemplo, si n = 8, entonces 3 × 3 = 1.5 × 5 = 1, 7 × 7 = 1. Por lo tanto, en el caso general, el producto de todos los elementos de E n no es igual a ( n − 1). Demostremos que entonces es igual a 1.

Llamamos especial a un elemento a del grupo E n si aa = 1. En este caso, el elemento n − a también es especial. Por lo tanto, el grupo E n contiene un número par de elementos especiales: ( a , n − a ) es el conjunto de tales elementos, y ningún elemento puede ser un par por sí mismo. Sean n 1 , n 2 , …, n k todos los elementos del grupo E n , es decir, un conjunto completo de números menores que n y primos relativos a n . El conjunto de elementos que no son especiales se divide en pares de elementos mutuamente inversos, por lo que el producto de tales elementos es igual a 1. Por otro lado, el producto de elementos especiales que forman el par ( a , n − a ) es igual a n − 1. Dado que ( n − 1)( n − 1) = 1, entonces el producto de todos los elementos especiales es igual a 1 o n − 1, dependiendo de si el número de pares de la forma ( a , n − a ) es par o impar. ■

El teorema fue probado y generalizado por primera vez por Gauss , para cualquier n > 2, para el producto de todos los números naturales que no excedan de n y coprimos con n , se lleva a cabo una comparación:

\prod _{{k=1 \atop (k,n)=1}}^{{n}}\!\!k\equiv {\begin{casos}-1{\pmod {n)),&n= 4,\;p^{\alpha },\;2p^{\alpha }\,;\\\;\;\,1{\pmod {n)),&n\neq 4,\;p^{\ alfa },\;2p^{\alfa }\,,\end{casos}}

donde es un número primo impar, es un indicador natural. $pags$ $\alfa$

Posteriormente se encontró otra generalización formal del teorema de Wilson (V. Vinograd):

$(pm)!*(m-1)!\equiv (-1)^{m}{\pmod {p))$

En , se obtiene el teorema de Wilson. $metro=1$

Cuando resulta , es decir. $m=\left({\frac {p+1}{2}}\right)$ $\left({\frac {p-1}{2}}\right)!^{2}+(-1)^{\left({\frac {p-1}{2}}\right )}\equiv 0{\pmod {p}}$

$\left({\frac {p-1}{2}}\right)!^{2}+1\equiv 0{\pmod {p}}$ , si $p\equiv 1{\pmod {4}}$

$\left({\frac {p-1}{2}}\right)!^{2}-1\equiv 0{\pmod {p}}$ , si $p\equiv 3{\pmod {4}}$

Véase también

Notas

↑ John J. O'Connor y Edmund F. Robertson . Abu Ali al-Hasan ibn al-Haytham (inglés) es una biografía en el archivo MacTutor .
↑ Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers" Archivado el 11 de mayo de 2022 en Wayback Machine (Prueba de un nuevo teorema sobre los números primos), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres ( Berlín), vol. 2, páginas 125-137 (1771)

Literatura

Bukhshtab A. A. Teoría de los números, 2ª edición, M., 1966
Trost E. Números primos, trad. del alemán, M., 1959
Vinogradov I.M. Fundamentos de la teoría de números . - 5ª ed.- M. - L .: Gostekhizdat, 1952.
R. Crandall, K. Dilcher y C. Pomerance El glosario principal
Ore, O. Teoría de números y su historia. McGraw-Hill, 1948.
Bonchkovsky R. N. y Chistyakov I. I. Educación matemática, número 01

diccionarios y enciclopedias	Gran danés Gran soviet (1 ed.) Britannica (en línea)