En 1640 Pierre de Fermat escribió en una carta a un amigo.

Si pes primo y aes cualquier número entero no divisible por p, entonces aᵖ⁻¹ − 1es divisible por p.

A diferencia de la mayoría de las cosas que les digo a mis amigos, Fermat tenía razón. Sin embargo, Fermat nunca lo demostró. Dejó el trabajo a Leonhard Euler, conocido aquí como la persona más ocupada de toda la historia de las matemáticas. En 1736, Euler demostró que Fermat había tenido razón y continuó extendiendo también el reclamo.

El pequeño teorema de Fermat

Fermat tenía peces más grandes que freír, así que este era su pequeño teorema. Establece que para cualquier número primo py entero aque sea coprimo de p: aᵖ⁻¹ % p = 1.

¿Por qué tenía razón Fermat?

La lista de números a, 2a, 3a, ..., (p-1)ason todos coprimos con p, porque pes primo. Si usamos mod pcada uno de estos números, estamos garantizados para producir una lista de todos los números entre 1& p-1. Esto se debe a que habrá p - 1resultados distintos. Podemos probar que serán distintos.

> if `k` & `m` are two values between `1` & `p - 1`
> to prove they are NOT distinct we would want to find
ka ≡ ma (mod p)
> because of the cancellation rule
k ≡ m (mod p)
> because `k` & `m` were defined as being less than `p`
k = m

Así que hemos demostrado que dada la lista a, 2a, 3a, ..., (p-1)a (mod p), obtendríamos el conjunto completo de números 1 -> p - 1. Ordenar esos resultados nos daría el conjunto: 1, 2, ..., p-1.

Un ejemplo podría aclarar las cosas:

p = 7, a = 3
> a, 2a, 3a, ..., (p-1)a
1(3), 2(3), 3(3), 4(3), 5(3), 6(3)
3, 6, 9, 12, 15, 18
> all `mod p`
3, 6, 2, 5, 1, 4
> ordering the results
1, 2, 3, 4, 5, 6

> we know that
a, 2a, ..., (p-1)a ≡ 1, 2, ..., p-1 (mod p)
> multiplying all elements
a x 2a x ... x (p-1)a ≡ 1 x 2 x ... x (p-1) (mod p)
> simplifies
aᵖ⁻¹(p-1)! ≡ (p-1)! (mod p)
> cancel `(p-1)!`
> giving us
aᵖ⁻¹ ≡ 1 (mod p)

Teorema de Euler

Habiendo demostrado el Pequeño Teorema de Fermat, Euler decidió continuar. Pudo demostrar que para dos enteros coprimos cualesquiera, ninguno necesariamente coprimo: aᵠ⁽ⁿ⁾ ≡ 1 (mod n). se refiere a la Función Totient de Euler, que exploramos anteriormente . La función Totient de cualquier entero n, devuelve el número de ncoprimos menores que n.

A diferencia del pequeño teorema de Fermat, la extensión de Euler eliminó la necesidad de que el módulo fuera un número primo. Sin embargo, afortunadamente, ya hemos hecho la mayor parte del trabajo para probar esto.

Recuerda cómo, con el Pequeño Teorema de Fermat, todos alos múltiplos de 's (mod p), dieron los números 1 -> p-1. Esa lista de números, 1 -> p-1eran pcoprimos de , dado que pes primo. En este caso, el módulo nno es primo, pero la lista de ncoprimos de 's multiplicada por a, todos (mod n), aún produce ncoprimos de 's. Por ejemplo

> remembering that
(n) = Number of n's coprimes
n = 10
> n's coprimes
1, 3, 7, 9
a x 3a x 7a x 9a ≡ 1 x 3 x 7 x 9 (mod n)
> where n = 10, this gives us the number of "a" factors
aᵠ⁽¹⁰⁾
aᵠ⁽¹⁰⁾ x (1 x 3 x 7 x 9) ≡ (1 x 3 x 7 x 9) (mod n)
> cancel the coprime multiplication
aᵠ⁽¹⁰⁾ ≡ 1 (mod n)

El pequeño teorema de Fermat y el teorema de Euler son muy importantes para la teoría de números. Ayudan a resolver casos de la Función de Carmichael, que cubrimos en profundidad . También son interesantes de forma aislada, como ejemplo de uso de la función Totient de Euler.

Y todo comenzó con una carta a un amigo hace casi 400 años.

Más ?

Escribo el boletín más corto del mundo. Una cosa rápida que he aprendido o visto o leído en la semana, cada miércoles.

Quiero que sea el boletín informativo más accesible y directo que reciba.

Podría valer la pena intentarlo. Darse de baja también es fácil.

Se llama . ¡Te veo allí!