Pruebas del pequeño teorema de Fermat

Este artículo recopila una variedad de pruebas del pequeño teorema de Fermat , que establece que

${\displaystyle a^{p}\equiv a{\pmod {p}}}$

para cada número primo p y cada entero a (ver aritmética modular ).

Simplificaciones

Algunas de las pruebas del pequeño teorema de Fermat que se dan a continuación dependen de dos simplificaciones.

La primera es que podemos suponer que a está en el rango 0 ≤ a ≤ p − 1 . Esta es una consecuencia simple de las leyes de la aritmética modular ; simplemente estamos diciendo que primero podemos reducir a módulo  p . Esto es consistente con la reducción módulo  p , como se puede comprobar. ${\displaystyle a^{p}}$

En segundo lugar, basta demostrar que

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

para a en el rango 1 ≤ a ≤ p − 1 . De hecho, si la afirmación anterior es válida para tal a , multiplicar ambos lados por a da como resultado la forma original del teorema,

${\displaystyle a^{p}\equiv a{\pmod {p}}}$

Por otra parte, si a = 0 o a = 1 , el teorema se cumple trivialmente.

Pruebas combinatorias

Prueba contando collares

Esta es quizás la prueba más simple conocida, que requiere menos conocimientos matemáticos. Es un ejemplo atractivo de una prueba combinatoria (una prueba que implica contar una colección de objetos de dos maneras diferentes ).

La prueba que se da aquí es una adaptación de la prueba de Golomb . ^[1]

Para simplificar, supongamos que a es un entero positivo . Consideremos todas las posibles cadenas de símbolos p , utilizando un alfabeto con símbolos a diferentes. El número total de dichas cadenas es a ^p, ya que hay a posibilidades para cada una de las p posiciones (ver regla del producto ).

Por ejemplo, si p  = 5 y a = 2 , entonces podemos usar un alfabeto con dos símbolos (digamos A y B ), y hay 2 ⁵  = 32 cadenas de longitud 5:

AAAAA , AAAAB , AAABA , AAABB , AABAA , AABAB , AABBA , AABBB ,

ABAAA , ABAAB , ABABA , ABABB , ABBAA , ABBAB , ABBBA , ABBBB ,

BAAAA , BAAAB , BAABA , BAABB , BABAA , BABAB , BABBA , BABBB ,

BBAAA , BBAAB , BBABA , BBABB , BBBAA , BBBAB , BBBBA , BBBBB .

A continuación, argumentaremos que si eliminamos de la lista las cadenas que constan de un solo símbolo (en nuestro ejemplo, AAAAA y BBBBB ), las cadenas p − a restantes se ^pueden organizar en grupos, cada grupo conteniendo exactamente p cadenas. De ello se deduce que a ^p − a es divisible por  p .

Collares

Collar que representa siete cuerdas diferentes ( ABCBAAC , BCBAACA , CBAACAB , BAACABC , AACABCB , ACABCBA , CABCBAA )

Collar que representa solo una cuerda ( AAAAAAA )

Pensemos que cada una de estas cadenas representa un collar . Es decir, conectamos los dos extremos de la cadena y consideramos que las dos cadenas son el mismo collar si podemos girar una de ellas para obtener la segunda; en este caso, diremos que las dos cadenas son amigas . En nuestro ejemplo, las siguientes cadenas son todas amigas:

AAAAB , AAABA , AABAA , ABAAA , BAAAA .

En su totalidad, cada línea de la siguiente lista corresponde a un único collar, y la lista completa comprende las 32 cuerdas.

AAAAB , AAABA , AABAA , ABAAA , BAAAA ,

AAABB , AABBA , ABBAA , BBAAA , BAAAB ,

AABAB , ABABA , BABAA , ABAAB , BAABA ,

AABBB , ABBBA , BBBAA , BBAAB , BAABB ,

ABABB , BABBA , ABBAB , BBABA , BABAB ,

ABBBB , BBBBA , BBBAB , BBABB , BABBB ,

AAAAA ,

¡BBBBB !

Observe que en la lista anterior, cada collar con más de un símbolo está representado por 5 cuerdas diferentes, y el número de collares representados por una sola cuerda es 2, es decir, es el número de símbolos distintos. Por lo tanto, la lista muestra muy claramente por qué 32 − 2 es divisible por 5 .

Se puede utilizar la siguiente regla para calcular cuántos amigos tiene una cadena S dada :

Si S está formado por varias copias de la cadena T , y T no puede dividirse en cadenas repetidas, entonces el número de amigos de S ( incluido el propio S ) es igual a la longitud de T.

Por ejemplo, supongamos que empezamos con la cadena S  =  ABBABBABBABB , que está formada por varias copias de la cadena más corta T  =  ABB . Si la rotamos un símbolo a la vez, obtenemos las siguientes 3 cadenas:

ABBABBABBABB ,

BBABABBABBA ,

BABBABBABBAB .

No hay otros porque ABB tiene exactamente 3 símbolos de longitud y no se puede dividir en más cadenas repetidas.

Completando la prueba

Usando la regla anterior, podemos completar la prueba del pequeño teorema de Fermat con bastante facilidad, de la siguiente manera. Nuestro grupo inicial de cadenas ^p puede dividirse en dos categorías:

• Algunas cadenas contienen p símbolos idénticos. Hay exactamente a de estos, uno por cada símbolo del alfabeto. (En nuestro ejemplo actual, son las cadenas AAAAA y BBBBB ).
• El resto de las cadenas utilizan al menos dos símbolos distintos del alfabeto. Si podemos dividir S en copias repetidas de alguna cadena T , la longitud de T debe dividir la longitud de S. Pero como la longitud de S es el primo p , la única longitud posible para T también es p . Por lo tanto, la regla anterior nos dice que S tiene exactamente p amigos (incluido el propio S ).

La segunda categoría contiene cadenas ^p − a , y se pueden organizar en grupos de cadenas p , un grupo por cada collar. Por lo tanto, a ^p − a debe ser divisible por p , como se prometió.

Demostración mediante sistemas dinámicos

Esta prueba utiliza algunos conceptos básicos de sistemas dinámicos . ^[2]

Comenzamos considerando una familia de funciones T _n ( x ), donde n ≥ 2 es un entero , mapeando el intervalo [0, 1] a sí mismo mediante la fórmula

${\displaystyle T_{n}(x)={\begin{cases}\{nx\}&0\leq x<1,\\1&x=1,\end{cases}}}$

donde { y } denota la parte fraccionaria de y . Por ejemplo, la función T ₃ ( x ) se ilustra a continuación:

Un ejemplo de una función T _n

Se dice que un número x ₀ es un punto fijo de una función f ( x ) si f ( x ₀ ) = x ₀ ; en otras palabras, si f deja x ₀ fijo. Los puntos fijos de una función se pueden encontrar fácilmente gráficamente: son simplemente las coordenadas x de los puntos donde la gráfica de f ( x ) interseca la gráfica de la línea y = x . Por ejemplo, los puntos fijos de la función T ₃ ( x ) son 0, 1/2 y 1; están marcados con círculos negros en el siguiente diagrama:

Puntos fijos de una función T _n

Necesitaremos los siguientes dos lemas.

Lema 1. Para cualquier n ≥ 2, la función T _n ( x ) tiene exactamente n puntos fijos.

Demostración. Hay tres puntos fijos en la ilustración anterior y el mismo tipo de argumento geométrico se aplica para cualquier n ≥ 2.

Lema 2. Para cualesquiera números enteros positivos n y m , y cualquier 0 ≤ x ≤ 1,

${\displaystyle T_{m}(T_{n}(x))=T_{mn}(x).}$

En otras palabras, T _mn ( x ) es la composición de T _n ( x ) y T _m ( x ).

Demostración. La demostración de este lema no es difícil, pero debemos tener un poco de cuidado con el punto final x = 1. Para este punto el lema es claramente cierto, ya que

${\displaystyle T_{m}(T_{n}(1))=T_{m}(1)=1=T_{mn}(1).}$

Supongamos entonces que 0 ≤ x < 1. En este caso,

${\displaystyle T_{n}(x)=\{nx\}<1,}$

Entonces T _m ( T _n ( x )) está dado por

${\displaystyle T_{m}(T_{n}(x))=\{m\{nx\}\}.}$

Por lo tanto, lo que realmente necesitamos demostrar es que

${\displaystyle \{m\{nx\}\}=\{mnx\}.}$

Para ello observamos que { nx } = nx − k , donde k es la parte entera de nx ; entonces

${\displaystyle \{m\{nx\}\}=\{mnx-mk\}=\{mnx\},}$

ya que mk es un entero.

Comencemos ahora propiamente la demostración del pequeño teorema de Fermat estudiando la función T _{a ^p} ( x ) ^. Supondremos que a ≥ 2. Del Lema 1 sabemos que tiene p puntos fijos. Por el Lema 2 sabemos que

${\displaystyle T_{a^{p}}(x)=\underbrace {T_{a}(T_{a}(\cdots T_{a}(x)\cdots ))} _{p{\text{ times}}},}$

Por lo tanto, cualquier punto fijo de T _a ( x ) es automáticamente un punto fijo de T _{a ^p} ( x ).

Nos interesan los puntos fijos de T _{a ^p} ( x ) que no son puntos fijos de T _a ( x ). Llamemos al conjunto de tales puntos S . Hay a ^p − a puntos en S , porque por el Lema 1 de nuevo, T _a ( x ) tiene exactamente a puntos fijos. El siguiente diagrama ilustra la situación para a = 3 y p = 2. Los círculos negros son los puntos de S , de los cuales hay 3 ² − 3 = 6.

Puntos fijos en el conjunto S

La idea principal de la prueba es ahora dividir el conjunto S en sus órbitas bajo T _a . Esto significa que elegimos un punto x ₀ en S y le aplicamos repetidamente T _{a (x) para obtener la secuencia de puntos}

${\displaystyle x_{0},T_{a}(x_{0}),T_{a}(T_{a}(x_{0})),T_{a}(T_{a}(T_{a}(x_{0}))),\ldots .}$

Esta secuencia se llama órbita de x ₀ bajo T _a . Por el Lema 2, esta secuencia se puede reescribir como

${\displaystyle x_{0},T_{a}(x_{0}),T_{a^{2}}(x_{0}),T_{a^{3}}(x_{0}),\ldots .}$

Como asumimos que x ₀ es un punto fijo de T _{a ^p} ( x ), después de p pasos llegamos a T _{a ^p} ( x ₀ ) = x ₀ , y desde ese punto en adelante la secuencia se repite.

Sin embargo, la secuencia no puede comenzar a repetirse antes de eso. Si lo hiciera, la longitud de la sección repetida tendría que ser un divisor de p , por lo que tendría que ser 1 (ya que p es primo). Pero esto contradice nuestra suposición de que x ₀ no es un punto fijo de T _a .

En otras palabras, la órbita contiene exactamente p puntos distintos. Esto es válido para cada órbita de S . Por lo tanto, el conjunto S , que contiene a ^p  −  a puntos, se puede dividir en órbitas, cada una de las cuales contiene p puntos, por lo que a ^p  −  a es divisible por p .

(Esta prueba es esencialmente la misma que la prueba del conteo de collares dada anteriormente, simplemente vista a través de una lente diferente: uno puede pensar en el intervalo [0, 1] como dado por secuencias de dígitos en base a (nuestra distinción entre 0 y 1 corresponde a la distinción familiar entre representar números enteros que terminan en ".0000..." y ".9999..."). T _{a ⁿ} equivale a desplazar dicha secuencia por n dígitos. Los puntos fijos de esto serán secuencias que son cíclicas con un período que divide a n . En particular, los puntos fijos de T _{a ^p} pueden considerarse como los collares de longitud p , con T _{a ⁿ} correspondiente a la rotación de dichos collares por n puntos.

Esta prueba también podría presentarse sin distinguir entre 0 y 1, simplemente usando el intervalo semiabierto [0, 1); entonces T _n solo tendría n − 1 puntos fijos, pero T _{a ^p} − T _a todavía funcionaría como a ^p − a , según sea necesario.)

Pruebas multinomiales

Demostraciones utilizando el teorema del binomio

Prueba 1

Esta prueba, debida a Euler , ^[3] utiliza la inducción para demostrar el teorema para todos los números enteros a  ≥ 0 .

El paso base, que 0 ^p  ≡ 0 (mod  p ) , es trivial. A continuación, debemos demostrar que si el teorema es verdadero para a  =  k , entonces también es verdadero para a  =  k  + 1 . Para este paso inductivo, necesitamos el siguiente lema.

Lema . Para cualesquiera números enteros x e y y para cualquier primo p , ( x  +  y ) ^p  ≡  x ^p  +  y ^p  (mod  p ) .

El lema es un ejemplo del sueño de un estudiante de primer año . Dejando la demostración para más adelante, procedemos con la inducción.

Demostración . Supongamos que k ^p ≡ k (mod p ), y consideremos ( k +1) ^p . Por el lema tenemos

${\displaystyle (k+1)^{p}\equiv k^{p}+1^{p}{\pmod {p}}.}$

Utilizando la hipótesis de inducción, tenemos que k ^p ≡ k (mod p ); y, trivialmente, 1 ^p = 1. Por lo tanto

${\displaystyle (k+1)^{p}\equiv k+1{\pmod {p}},}$

cual es el enunciado del teorema para a = k +1. ∎

Para demostrar el lema, debemos introducir el teorema del binomio , que establece que para cualquier entero positivo n ,

${\displaystyle (x+y)^{n}=\sum _{i=0}^{n}{n \choose i}x^{n-i}y^{i},}$

donde los coeficientes son los coeficientes binomiales ,

${\displaystyle {n \choose i}={\frac {n!}{i!(n-i)!}},}$

descrito en términos de la función factorial , n ! = 1×2×3×⋯× n .

Demostración del lema. Consideramos el coeficiente binomial cuando el exponente es un primo p :

${\displaystyle {p \choose i}={\frac {p!}{i!(p-i)!}}}$

Los coeficientes binomiales son todos números enteros. El numerador contiene un factor p por la definición de factorial. Cuando 0 < i < p , ninguno de los términos en el denominador incluye un factor de p (confiando en la primalidad de p ), dejando que el coeficiente en sí posea un factor primo de p del numerador, lo que implica que

${\displaystyle {p \choose i}\equiv 0{\pmod {p}},\qquad 0<i<p.}$

Módulo p , esto elimina todos los términos excepto el primero y el último de la suma en el lado derecho del teorema binomial para el primo p . ∎

La primalidad de p es esencial para el lema; de lo contrario, tenemos ejemplos como

${\displaystyle {4 \choose 2}=6,}$

que no es divisible por 4.

Prueba 2

Usando el Lema, tenemos:

${\displaystyle k^{p}\equiv ((k-1)+1)^{p}\equiv (k-1)^{p}+1\equiv ((k-2)+1)^{p}+1\equiv (k-2)^{p}+2\equiv \dots \equiv k{\pmod {p}}}$.

Demostración mediante la expansión multinomial

La prueba, que fue descubierta por primera vez por Leibniz (quien no la publicó) ^[4] y luego redescubierta por Euler ^[3] , es una aplicación muy simple del teorema multinomial , que establece

${\displaystyle (x_{1}+x_{2}+\cdots +x_{m})^{n}=\sum _{k_{1},k_{2},\dots ,k_{m} \atop k_{1}+k_{2}+\dots +k_{m}=n}{n \choose k_{1},k_{2},\ldots ,k_{m}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}}$

dónde

${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!k_{2}!\dots k_{m}!}}}$

y la suma se realiza sobre todas las secuencias de índices enteros no negativos k ₁ , k ₂ , ..., k _m tales que la suma de todos los k _i es n .

Así, si expresamos a como suma de 1s (unos), obtenemos

${\displaystyle a^{p}=(1+1+...+1)^{p}=\sum _{k_{1},k_{2},\dots ,k_{a} \atop k_{1}+k_{2}+\dots +k_{a}=p}{p \choose k_{1},k_{2},\ldots ,k_{a}}}$

Claramente, si p es primo, y si k _j no es igual a p para cualquier j , tenemos

${\displaystyle {p \choose k_{1},k_{2},\ldots ,k_{a}}\equiv 0{\pmod {p}},}$

y si k _j es igual a p para algún j entonces

${\displaystyle {p \choose k_{1},k_{2},\ldots ,k_{a}}=1.}$

Puesto que hay exactamente a elementos tales que k _j  =  p para algún j , se cumple el teorema.

(Esta prueba es esencialmente una variante de grano más grueso de la prueba de conteo de collares dada anteriormente; los coeficientes multinomiales cuentan el número de formas en que una cadena puede permutarse en anagramas arbitrarios, mientras que el argumento del collar cuenta el número de formas en que una cadena puede rotarse en anagramas cíclicos. Es decir, que los coeficientes multinomiales no triviales aquí sean divisibles por p puede verse como una consecuencia del hecho de que cada collar no trivial de longitud p puede desenrollarse en una cadena de p muchas maneras.

Esta expansión multinomial es también, por supuesto, lo que esencialmente sustenta la prueba basada en el teorema binomial anterior)

Demostración mediante expansiones de productos de potencia

^{Giedrius Alkauskas [5]} presentó una prueba aditiva-combinatoria basada en desarrollos formales de productos de potencia. Esta prueba no utiliza ni el algoritmo euclidiano ni el teorema binomial , sino que emplea series de potencia formales con coeficientes racionales .

Demostración como caso particular del teorema de Euler

Esta prueba, ^{[3] [6]} descubierta por James Ivory ^[7] y redescubierta por Dirichlet ^[8] , requiere algunos conocimientos básicos de aritmética modular .

Supongamos que a es positivo y no divisible por p .

La idea es que si escribimos la secuencia de números

y reducimos cada uno módulo p , la secuencia resultante resulta ser un reordenamiento de

Por lo tanto, si multiplicamos entre sí los números de cada secuencia, los resultados deben ser idénticos módulo p :

${\displaystyle a\times 2a\times 3a\times \cdots \times (p-1)a\equiv 1\times 2\times 3\times \cdots \times (p-1){\pmod {p}}.}$

Reuniendo los términos a se obtiene

${\displaystyle a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p}}.}$

Finalmente, podemos “cancelar” los números 1, 2, ..., p − 1 de ambos lados de esta ecuación, obteniendo

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

Hay dos pasos en la prueba anterior que debemos justificar:

• ¿Por qué los elementos de la secuencia ( A ), reducida módulo p , son un reordenamiento de ( B ), y
• Por qué es válido “cancelar” en el contexto de la aritmética modular.

Probaremos estas cosas a continuación; veamos primero un ejemplo de esta prueba en acción.

Un ejemplo

Si a  = 3 y p  = 7 , entonces la secuencia en cuestión es

${\displaystyle 3,6,9,12,15,18;}$

reduciendo módulo 7 da

${\displaystyle 3,6,2,5,1,4,}$

que es simplemente un reordenamiento de

${\displaystyle 1,2,3,4,5,6.}$

Multiplicándolos juntos obtenemos

${\displaystyle 3\times 6\times 9\times 12\times 15\times 18\equiv 3\times 6\times 2\times 5\times 1\times 4\equiv 1\times 2\times 3\times 4\times 5\times 6{\pmod {7}};}$

eso es,

${\displaystyle 3^{6}(1\times 2\times 3\times 4\times 5\times 6)\equiv (1\times 2\times 3\times 4\times 5\times 6){\pmod {7}}.}$

Cancelando 1 × 2 × 3 × 4 × 5 × 6 obtenemos

${\displaystyle 3^{6}\equiv 1{\pmod {7}},}$

que es el pequeño teorema de Fermat para el caso a  = 3 y  p  = 7 .

La ley de cancelación

Expliquemos primero por qué es válido, en determinadas situaciones, “cancelar”. El enunciado exacto es el siguiente. Si u , x e y  son números enteros, y u no es divisible por un número primo p , y si

entonces podemos “cancelar” u para obtener

Nuestro uso de esta ley de cancelación en la prueba anterior del pequeño teorema de Fermat fue válido porque los números 1, 2, ..., p  − 1 ciertamente no son divisibles por p (de hecho, son más pequeños que p ).

Podemos demostrar la ley de cancelación fácilmente usando el lema de Euclides , que generalmente establece que si un primo p divide a un producto ab (donde a y b son números enteros), entonces p debe dividir a a o b . De hecho, la afirmación ( C ) simplemente significa que p divide a ux − uy = u ( x − y ) . Como p es un primo que no divide a u , el lema de Euclides nos dice que debe dividir a x  −  y en su lugar; es decir, ( D ) es válido.

Nótese que las condiciones bajo las cuales se cumple la ley de cancelación son bastante estrictas, y esto explica por qué el pequeño teorema de Fermat exige que p sea un primo. Por ejemplo, 2×2 ≡ 2×5 (mod 6) , pero no es cierto que 2 ≡ 5 (mod 6) . Sin embargo, la siguiente generalización de la ley de cancelación se cumple: si u , x , y y z son números enteros, si u y z son primos relativos y si

${\displaystyle ux\equiv uy{\pmod {z}},}$

entonces podemos “cancelar” u para obtener

${\displaystyle x\equiv y{\pmod {z}}.}$

Esto se desprende de una generalización del lema de Euclides .

La propiedad de reordenamiento

Finalmente, debemos explicar por qué la secuencia

${\displaystyle a,2a,3a,\ldots ,(p-1)a,}$

Cuando se reduce módulo p , se convierte en un reordenamiento de la secuencia.

${\displaystyle 1,2,3,\ldots ,p-1.}$

Para empezar, ninguno de los términos a , 2 a , ..., ( p  − 1) a puede ser congruente con cero módulo p , ya que si k es uno de los números 1, 2, ...,  p  − 1 , entonces k es relativamente primo con p , y también lo es a , por lo que el lema de Euclides nos dice que ka no comparte ningún factor con p . Por lo tanto, al menos sabemos que los números a , 2 a , ..., ( p  − 1) a , al reducirlos módulo p , deben encontrarse entre los números 1, 2, 3, ...,  p  − 1 .

Además, los números a , 2 a , ..., ( p  − 1) a deben ser todos distintos después de reducirlos módulo p , porque si

${\displaystyle ka\equiv ma{\pmod {p}},}$

donde k y m son uno de 1, 2, ...,  p  − 1 , entonces la ley de cancelación nos dice que

${\displaystyle k\equiv m{\pmod {p}}.}$

Como tanto k como m están entre 1 y p  − 1 , deben ser iguales. Por lo tanto, los términos a , 2 a , ..., ( p  − 1) a cuando se reducen módulo p deben ser distintos. Para resumir: cuando reducimos los p  − 1 números a , 2 a , ..., ( p  − 1) a módulo p , obtenemos miembros distintos de la secuencia 1 ,  2 , ...,  p  − 1 . Como hay exactamente p  − 1 de estos, la única posibilidad es que los primeros sean un reordenamiento de los últimos.

Aplicaciones del teorema de Euler

Este método también se puede utilizar para demostrar el teorema de Euler , con una ligera modificación: los números de 1 a p − 1 se sustituyen por los números menores que y coprimos con algún número m (no necesariamente primo). Tanto la propiedad de reordenamiento como la ley de cancelación (bajo la forma generalizada mencionada anteriormente) todavía se satisfacen y se pueden utilizar.

Por ejemplo, si m = 10 , entonces los números menores que  m y coprimos con m son 1 , 3 , 7 y 9. Por lo tanto, tenemos:

${\displaystyle a\times 3a\times 7a\times 9a\equiv 1\times 3\times 7\times 9{\pmod {10}}.}$

Por lo tanto,

${\displaystyle {a^{\varphi (10)}}\equiv 1{\pmod {10}}.}$

La demostración como corolario del criterio de Euler

Pruebas utilizando la teoría de grupos

Prueba estándar

Esta prueba ^[9] requiere los elementos más básicos de la teoría de grupos .

La idea es reconocer que el conjunto G  = {1, 2, ..., p − 1 }, con la operación de multiplicación (tomada módulo p ), forma un grupo . El único axioma de grupo que requiere cierto esfuerzo para verificar es que cada elemento de G es invertible. Tomando esto como algo de fe por el momento, supongamos que a está en el rango 1 ≤ a ≤ p − 1 , es decir, a es un elemento de G . Sea k el orden de a , es decir, k es el entero positivo más pequeño tal que a ^k  ≡ 1 (mod  p ) . Entonces los números 1, a , a ² , ..., a ^{k  −1} reducido módulo  p forman un subgrupo de  G cuyo orden es  k y por lo tanto, por el teorema de Lagrange , k divide el orden de G , que es p  − 1 . Entonces p  − 1 =  km para algún entero positivo m y luego

${\displaystyle a^{p-1}\equiv a^{km}\equiv (a^{k})^{m}\equiv 1^{m}\equiv 1{\pmod {p}}.}$

Para demostrar que cada elemento b de G es invertible, podemos proceder de la siguiente manera. Primero, b es coprimo de p . Por lo tanto, la identidad de Bézout nos asegura que hay números enteros x e y tales que bx  +  py  = 1 . Leyendo esta igualdad módulo p , vemos que x es una inversa para b , ya que bx  ≡ 1 (mod  p ) . Por lo tanto, cada elemento de G es invertible. Entonces, como se señaló anteriormente, G es un grupo.

Por ejemplo, cuando p = 11 , las inversas de cada elemento se dan de la siguiente manera:

Prueba de Euler

Si tomamos la demostración anterior y, en lugar de utilizar el teorema de Lagrange, tratamos de demostrarlo en esta situación específica, entonces obtenemos la tercera demostración de Euler, que es la que le pareció más natural. ^{[10] [11]} Sea A el conjunto cuyos elementos son los números 1, a , a ² , ..., a ^{k  − 1} reducido módulo  p . Si A  =  G , entonces k  =  p  − 1 y por lo tanto k divide a p  −1 . En caso contrario, existe algún b ₁  ∈  G \ A .

Sea A ₁ el conjunto cuyos elementos son los números b ₁ , ab ₁ , a ² b ₁ , ..., a ^{k − 1} b ₁ reducido módulo  p . Entonces A ₁ tiene k elementos distintos porque de lo contrario habría dos números distintos m , n  ∈ {0, 1, ..., k − 1 } tales que a ^m b ₁ ≡ a ⁿ b ₁ (mod p ) , lo cual es imposible, ya que se seguiría que a ^m ≡ a ⁿ (mod p ) . Por otra parte, ningún elemento de A ₁ puede ser elemento de A , porque de lo contrario habría números m , n  ∈ {0, 1, ..., k  − 1 } tales que a ^m b ₁ ≡ a ⁿ (mod p ) , y entonces b ₁ ≡ a ⁿ a ^{k − m} ≡ a ^{n + k − m} (mod p ) , lo cual es imposible, ya que b ₁ ∉ A .

Así, el conjunto A ∪ A ₁ tiene 2 k elementos. Si resulta igual a  G , entonces 2 k  =  p  −1 y por tanto k divide a p  −1 . En caso contrario, existe algún b ₂  ∈  G \( A ∪ A ₁ ) y podemos empezar de nuevo, definiendo A ₂ como el conjunto cuyos elementos son los números b ₂ , ab ₂ , a ² b ₂ , ..., a ^{k  − 1} b ₂ reducido módulo  p . Como G es finito, este proceso debe detenerse en algún punto y esto demuestra que k divide a p  − 1 .

Por ejemplo, si a = 5 y p = 13 , entonces, dado que

• 5 ²  = 25 ≡ 12 (mód 13) ,
• 5 ³  = 125 ≡ 8 (mód 13) ,
• 5 ⁴  = 625 ≡ 1 (mód 13) ,

tenemos k  = 4 y A  = {1, 5, 8, 12 }. Claramente, A  ≠  G  = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }. Sea b ₁ un elemento de G \ A ; por ejemplo, tomemos b ₁  = 2 . Entonces, como

• 2×1 = 2 ,
• 2×5 = 10 ,
• 2×8 = 16 ≡ 3 (mód 13) ,
• 2×12 = 24 ≡ 11 (mód 13) ,

tenemos A ₁  = {2, 3, 10, 11 }. Claramente, A ∪ A ₁ ≠ G . Sea b ₂ un elemento de G \( A ∪ A ₁ ) ; por ejemplo, tomemos b ₂ = 4 . Entonces, como

• 4×1 = 4 ,
• 4×5 = 20 ≡ 7 (mód 13) ,
• 4×8 = 32 ≡ 6 (mód 13) ,
• 4×12 = 48 ≡ 9 (mód 13) ,

tenemos A ₂  = {4, 6, 7, 9 }. Y ahora G  =  A ∪ A ₁ ∪ A ₂ .

Nótese que los conjuntos A , A ₁ , etc. son, de hecho, los clases laterales de A en G.

Notas

1. Golomb, Solomon W. (1956), "Demostración combinatoria del "pequeño" teorema de Fermat" (PDF) , American Mathematical Monthly , 63 (10): 718, doi :10.2307/2309563, JSTOR  2309563
2. Iga, Kevin (2003), "Una prueba de sistemas dinámicos del pequeño teorema de Fermat", Mathematics Magazine , 76 (1): 48–51, doi :10.2307/3219132, JSTOR  3219132
3. Dickson, Leonard Eugene (2005) [1919], "Teoremas, generalizaciones y recíprocos de Fermat y Wilson; funciones simétricas de 1, 2, ..., p  − 1 módulo p ", Historia de la teoría de números , vol. I, Dover , ISBN 978-0-486-44232-7, Zbl1214.11001 ​
4. Vacca, Giovanni (1894), "Intorno alla prima dimostrazione di un teorema di Fermat", Bibliotheca Mathematica , segunda serie (en italiano), 8 (2): 46–48
5. Alkauskas, Giedrius (2009), "Una prueba curiosa del pequeño teorema de Fermat", American Mathematical Monthly , 116 (4): 362–364, arXiv : 0801.0805 , doi :10.4169/193009709x470236, JSTOR  40391097
6. Hardy, GH ; Wright, EM (2008), "El teorema de Fermat y sus consecuencias", Introducción a la teoría de números (6.ª ed.), Oxford University Press , ISBN 978-0-19-921986-5
7. Ivory, James (1806), "Demostración de un teorema sobre números primos", The Mathematical Repository , Nueva serie, 1 (II): 6–8
8. Lejeune Dirichlet, Peter Gustav (1828), "Démonstrations nouvelles de quelques théorèmes relatifs aux nombres", Journal für die reine und angewandte Mathematik (en francés), 3 : 390–393
9. Bien, André ; Rosenlicht, Maxwell (1979), "§ VIII", Teoría de números para principiantes , Springer-Verlag , doi :10.1007/978-1-4612-9957-8, ISBN 978-0-387-90381-1, Zbl0405.10001 ​
10. Weil, André (2007) [1984], "§ III.VI", Teoría de números: una aproximación a través de la historia; de Hammurabi a Legendre , Birkhäuser , ISBN 978-0-8176-4565-6, Zbl1149.01013 ​
11. Euler, Leonhard (1761), "Theoremata circa residua ex divisione potestatum relicta" (PDF) , Novi Commentarii Academiae Scientiarum Petropolitanae (en latín), 7 : 49–82