Propiedades relevantes de la función indicatriz de Euler

Recordemos que la función indicatriz de Euler de un número entero positivo $m$, distinto de cero, proporciona el número de números naturales menores o iguales que $m$ que son coprimos con $m$   (*), y se de demuestra que $\displaystyle \varphi(m):=m\,\prod_{p_i|m}\,\left(1-\dfrac{1}{p_i}\right)$; siendo $\{p_i\}$, el conjunto de números primos que dividen a $m$   (**). Entonces, a partir de ahí, es fácil demostrar las siguientes propiedades:

1. $\varphi(p)\overset{\text{(*)}}{=}p-1$ si $p$ es primo, habida cuenta de la definición de la función   $\diamond$.
2. $\varphi(m\,n)\overset{\text{(*)}}{=}\varphi(m)\,\varphi(n)$ si $(m,n)=1$, habida cuenta de la definición de la función; en particular, si $m$ y $n$ son números primos, se tiene que $\varphi(m\,n)\overset{\text{P1}}{=}(m-1)\,(n-1)$   $\diamond$.
3. $\varphi(p^k)=(p-1)\,p^{k-1}$ si $p$ es primo y $k\in \mathbb{N}$; en efecto, $\varphi(p^k)\overset{\text{(**)}}{=}p^k\,\left(1-\dfrac{1}{p}\right)=p^k\,\dfrac{(p-1)}{p}=(p-1)\,p^{k-1}$   $\diamond$.

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$

La función indicatriz de Euler, el teorema de Euler-Fermat y el pequeño teorema de Fermat

La función indicatriz de Euler

La función indicatriz de Euler es muy importante en teoría de números. La función indicatriz de Euler de un número entero positivo $m$, y se escribe $\varphi(m)$, proporciona el número de números enteros positivos, menores o iguales que $m$, que son coprimos con $m$. En el lenguaje matemático: $\varphi(m):=\text{cardinal}\left(\{n\in \mathbb{N}: (1\le n \le m) \wedge \text{m.c.d.}(m,n)=1\}\right)$. Se demuestra que dicha cantidad es igual a $\displaystyle \varphi(m):=m\,\prod_{p_i|m}\,\left(1-\dfrac{1}{p_i}\right)$; siendo $\{p_i\}$, el conjunto de números primos que dividen a $m$. Así, por ejemplo $\varphi(9)=9\cdot \left(1-\dfrac{1}{3}\right)=9\cdot \dfrac{2}{3}=6$; en efecto, el conjunto de números naturales que cumplen la condición requerida es $\{1,2,4,5,7,8\}$, y, claro está que $\text{cardinal}\left(\{1,2,4,5,7,8\}\right)=6$

El teorema de Euler-Fermat

La función indicatriz de Euler-Fermat aparece por ejemplo en el teorema de Euler-Fermat: Si $a,m \in \mathbb{N}$ son primos relativos, esto es, $\text{m.c.d.}(a,m)=1)$, entonces $a$ es congruente con $1$ módulo $m$: $a^{\varphi(m)} \equiv 1 (\text{mod}\, m)$, y es de gran importancia en el cálculo de congruencias.

El pequeño teorema de Fermat

El teorema de Euler-Fermat generaliza el pequeño teorema de Fermat. El pequeño teorema de Fermat dice así: dado un número $p$, primo, y un número entero $a$, siendo $a$ y $p$ coprimos, esto es $\text{m.c.d.}(a,p)=1$, entonces $a^{p-1}\equiv 1 (\text{mod}\, p)$, afirmación que es equivalente a $a^p ≡ a (\text{mod}\, p)$. Por ejemplo, si $p=3$ y $a=4$, se tiene que el residuo de la división euclídea de $a^p=4^{3-1}=16$ entre $3$ es $1$, como debe ser; esto es, el residuo de la división $4^3=64$ entre $3$ es igual a $4$.

-oOo-

Observación. Una consecuencia de este teorema es la siguiente: Como al dividir $a^{p-1}$ entre $p$ se obtiene resto igual a $1$, existe un $k\in \mathbb{Z}$ para el cual $a^{p-1}=k\, p +1$, multiplicando por $a$ en cada miembro de la igualdad, se tiene que $a^{p}= k \,p \,a + a$, luego $a^{p} - a$ es múltiplo de $p$ puesto que $k\,a$ és también un número entero.

Ejemplo. Sea $a=9$ y $p=2$ (primo), siendo $(9,2)=1$ y cumpliéndose así las condiciones suficientes del teorema. Comprabamos, en efecto, que $a^p=9^2=81 \mod 2 = 1$, coincidiendo con $a=9 \mod 2 =1$; y, además, $a^p-a \in (\overset{.}{p})$ pues $81-8=72 \in (\overset{.}{2})$.

$\diamond$