Introducción

Pierre de Fermat
Tras la muerte de Pierre de Fermat, muchas de sus conjeturas quedaron sin resolver. Como ya sabemos, Fermat no era muy dado a publicar las demostraciones de sus resultados, por lo que debían ser demostrados por otros para confirmar su validez o falsedad. El caso más famoso, por lo que se tardó en confirmar y por la gran cantidad de matemáticos que se dedicaron a ello, es el denominado último teorema de Fermat, demostrado finalmente por Andrew Wiles en 1995, pero ni mucho menos fue el único.

La afirmación de Fermat sobre la primalidad de todos los números enteros positivos F_n=2^{2^n}+1, llamados números de Fermat, fue otra de sus más famosas conjeturas, refutada finalmente por Euler en 1732 al encontrar la factorización de F_5:

F_5=2^{2^5}+1=4294967297=641 \cdot 6700417

De hecho no se ha vuelto a encontrar ningún número de Fermat que sea primo.

Y el llamado pequeño teorema de Fermat constituye otro caso del mismo tipo que los anteriores. Dicho teorema afirma lo siguiente:

Si p es un número primo y a es un número natural que no es divisible por p, entonces a^{p-1} \equiv 1 \pmod{p}

Euler demostró este resultado y dio además la demostración de una generalización del mismo. En esta historia la conocida como función \varphi de Euler ejerce un papel de suma importancia.

La función \varphi de Euler

Leonhard Euler
Recordemos para comenzar el siguiente concepto:

Dos números enteros a,b son primos relativos si mcd(a,b)=1.

Por ejemplo, 3 y 16 son primos relativos, pero 7 y 28 no.

Bien, con esta información ya estamos preparados para conocer a la protagonista de este artículo:

Función \varphi de Euler

Dado n \in \mathbb{N}, se define \varphi (n) como la cantidad de números naturales menores o iguales que n que son primos relativos con el propio n.

Por ejemplo, \varphi (15)=8, ya que hay 8 números naturales menores que 15 que son primos relativos con 15: \{ 1,2,4,7,8,11,13,14 \}.

Dado que siempre debemos contar al número 1, se tiene que \varphi (1)=1. Y, por otra parte, si p es un número primo, entonces \varphi (p)=p-1, ya que al ser primo todos los naturales menores que él son primos relativos con él.

Vale, para los números primos es sencillo. ¿Y qué ocurre con el resto? Porque claro, en el caso de que necesitemos calcular el valor de \varphi(n) para n muy grande tendríamos que ir probando uno por uno con todos los números menores que el propio n para ver cuántos hay primos relativos con n, y eso parece un trabajo tremendo. Bien, no está todo perdido, esta función tiene unas características muy interesantes que nos van a permitir realizar ese cálculo.

Según el Teorema Fundamental de la Aritmética, todo número natural puede factorizarse de forma única como producto de potencias de sus factores primos, es decir:

Si n \in \mathbb{N}, entonces existen p_1, \ldots , p_k números primos y \alpha_1, \ldots , \alpha_k números naturales tal que:

n=p_1^{\alpha_1} \cdot \ldots \cdot p_k^{\alpha_k}

Entonces, lo primero que nos interesaría saber es cómo calcular el valor de \varphi para un número del tipo p^k, con p primo. Bien, pues ese valor es conocido y tiene la siguiente expresión, que es muy sencilla de probar por inducción sobre k:

\varphi (p^k)=(p-1) p^{k-1}

Ahora sólo nos falta algo que nos diga cómo calcular el valor de \varphi para un producto. Y para esto también tenemos una propiedad:

\varphi (n \cdot m)=\varphi (n) \cdot \varphi (m)

Aplicando estas dos propiedades a la vez a cualquier número natural del que conozcamos su factorización en números primos es muy sencillo cuánto vale \varphi de ese número, al ser esta factorización un producto de primos elevados a ciertas potencias.

De hecho hasta tenemos una expresión elegante para esto. Es la denominada producto de Euler:

Si la factorización de n en números primos es

n=p_1^{\alpha_1} \cdot \ldots \cdot p_k^{\alpha_k}

entonces

\varphi (n)=n \left (1-\cfrac{1}{p_1} \right ) \cdot \left (1-\cfrac{1}{p_2} \right ) \cdot \ldots \cdot \left (1-\cfrac{1}{p_k} \right )

Usando el ejemplo anterior, como 15=3 \cdot 5, tenemos que

\varphi (15) = 15 \left ( 1-\cfrac{1}{3} \right ) \cdot \left (1-\cfrac{1}{5} \right )=15 \cdot \cfrac{2}{3} \cdot \cfrac{4}{5}=8

El teorema de Euler: generalizando el pequeño teorema de Fermat

Como hemos comentado antes, el enunciado del denominado pequeño teorema de Fermat es el siguiente:

Si p es un número primo y a es un número natural que no es divisible por p, entonces a^{p-1} \equiv 1 \pmod{p}

Esto es, si p es un número primo y a es un número natural tal que $mcd(a,p)=1$, entonces a^{p-1} deja resto 1 al dividirlo por p.

Euler fue el primero en demostrar este hecho (que puede hacerse fácilmente por inducción sobre a), pero como hemos dicho no se quedó ahí. El gran Leonhard nos dejó para la posteridad una auténtica perla en forma de generalización de este teorema, conocida como teorema de Euler, que en esta ocasión va a servir para finalizar este artículo:

Dados a, n \in \mathbb{N} tales que mcd(a,n)=1, se tiene que

a^{\varphi (n)} \equiv 1 \pmod{n}

Fuentes:

  • Historia de la matemática, de Carl B. Boyer.
  • Función \varphi de Euler en la Wikipedia española.
Print Friendly, PDF & Email
5 3 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉