El teorema de Euler-Fermat tiene un papel relevante en matemática discreta (teoría de números)

Preliminar:

Recordemos, para empezar, que dos números enteros positivos $a,b$ son coprimos si el máximo común divisor de dichos números es $1$, y lo notamos de la froma $\text{mcd}(a,b)=1$ (de manera más compacta: $(a,b)=1$); así, por ejemplo, $12$ y $35$ son coprimos, pues $(12,35)=1$. Por otra parte, la función $\varphi$ de Euler (o función indicatriz de Euler) de un número natural, $n$, que escribimos de la forma $\varphi(n)$ proporciona el número de números naturales menores o iguales que $n$ que son coprimos con $n$, esto es, $\varphi(n)=|\{m \in \mathbb{N}: m\le n\,\wedge\,(m,n)=1\}|$, donde $|.|$ designa el cardinal del conjunto (entre llaves). Así, por ejemplo, $\varphi(24)=8$ ya que $|\{1,5,7,11,13,17,19,23\}|=8$.

A efectos prácticos, y para evitar tener que escribir la lista de todos los divisores del número en cuestión que son coprimos con dicho número para contarlos uno a uno, es muy útil la siguiente fórmula para calcular el valor de la función indicatriz de Euler para dicho número: $\displaystyle \varphi(n):=n\,\prod_{p_i|n}\,\left(1-\dfrac{1}{p_i}\right)$; siendo $\{p_i\}$, el conjunto de números primos que dividen a $n$.

Otro ejemplo de cálculo de la función indicatriz de Euler: $\varphi(75)$

Teniendo en cuenta que los divisores primos de $75$ son $3$ y $5$, puesto que $75=3\cdot 5^2\cdot 3$, se tiene que, de acuerdo con la definición, $\varphi(75)=75\cdot \left(1-\dfrac{1}{3}\right)\,\left( 1- \dfrac{1}{5}\right)=75\cdot \dfrac{2}{3}\cdot \dfrac{4}{5}=40$

Teorema (de Euler-Fermat):

Vamos a recordar ahora lo que se afirma en dicho teorema, si bien no reproduciré aquí la demostración: $a^{\varphi(n)}$ es congruente con $1$ módulo $n\in \mathbb{N}$, para todo número $a \in \mathbb{Z} \setminus \{0\}$ tal que éste y $n$ sean coprimos, esto es, en esas condiciones, el resto de la división euclídea de $a^{\varphi(n)}$ entre $n$ es igual a $1$; y, exprasado de una manera más compacta, $a^{\varphi(n)} \equiv 1 \,(\text{mod}\; n)\,\forall a \in \mathbb{Z} \setminus \{0\}: (a,n)=1$.

Ejemplo:

Consideremos, por ejemplo, $a=:6$ y $n=:5$, entonces, como se cumple que $(6,5)=1$, por el teorema se tiene que $6^{\varphi(5)}=6^4=1296 \equiv 1 (\text{mod}\,5)$, lo cual es fácilmente comprobable: al dividir $1296$ entre $5$ se obtiene cociente igual a $259$ y, como debe ser, resto igual a $1$.

-oOo-

Comentario:

Otro resultado muy importante en el cálculo con congruencias (clases de resto) es el pequeño teorema de Fermat, que dice así: dado un número entero positivo $a$ y un número primo $p$, tales que $(a,p)=1$ ($a$ y $p$ son coprimos), entonces $a^{p-1} \equiv 1 \,(\text{mod}\;p)$   (1). Dicho sea de paso que, sin necesidad de que $a$ y $p$ sean coprimos, se llega también a la siguiente afirmación $a^p \equiv a\,(\text{mod}\,p)$; en efecto, $a^{p-1} \equiv 1 \,(\text{mod}\;p) \therefore a\cdot a^{p-1}=a^p \equiv a\cdot 1 \,(\text{mod}\;p) = a\,(\text{mod}\;p)$   (2).

Ejemplos

1. Veamos un ejemplo para el resultado (1): consideremos $a=:5$ y $p=:3$ ($5,3)=1$), entonces $5^{3-1}=5^2=25 \equiv \,(\text{mod}\; 3)$
2. Veamos un ejemplo para el resultado (2): sea $a=:7$ y $p=:3$ (ahora, $(6,3) = 1$), entonces $7^{3}=343 = 1 \equiv \,(\text{mod}\; 3)$; en efecto, el resto de la división euclídea de $343$ entre $3$ es igual a $1$. Formulado el resultado del pequeño teorema de Fermat como (2), y aunque $(a,p)\, \not| 1$, se puede comprobar que se verifica (tal como se demuestra arriba): consideremos, por ejemplo, $a=:6$ y $p=:3$ — observemos que, en este caso, $(6,3) \neq 1$ —, entonces $6^{3}=216 = 0 \equiv \,(\text{mod}\; 3) = 6 \equiv \,(\text{mod}\; 3)$; en efecto, el resto de la división euclídea de $216$ entre $3$ es $0$, como también es $0$ el resto de la división de $6$ entre $3$.

$\diamond$