La función Phi de Euler: otra genialidad del maestro

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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

3 Comentarios

  1. La verdad es que siempre he sentido cariño por este teorema de Euler.

    Bien comentas que es fácil probarlo por inducción, pero yo creo que este es uno de los casos en los que el álgebra sorprende ofreciendo una solución turbadoramente sencilla. Tan sólo atendiendo al teorema de Lagrange (http://www.worldlingo.com/ma/enwiki/es/Lagrange%27s_theorem_%28group_theory%29) al grupo multiplicativo Z_n, de tamaño \varphi(n).

    Por otro lado, siempre es interesante recordar que este resultado tan simple es la base del algoritmo RSA (http://en.wikipedia.org/wiki/RSA), tan importante para mantener nuestras comunicaciones secretas.

    Un saludo, y a seguir con este magnífico blog

    Publica una respuesta
  2. El valor de la suma para todos los divisores d de n: \displaystyle \sum_{d|n}  \phi(d) = n
    también es curioso y muy fácil de demostrar.

    Por ejemplo \phi(1) + \phi(2) + \phi(3) + \phi(4) + \phi(6) + \phi(12) = 12

    Publica una respuesta

Trackbacks/Pingbacks

  1. La función Phi de Euler: otra genialidad del maestro Fermat - [...] La función Phi de Euler: otra genialidad del maestro Fermat gaussianos.com/la-funcion-phi-de-euler-otra-genialidad-del-m...  por tomaydaca hace 2 segundos [...]
  2. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Introducción Pierre de Fermat Tras la muerte de Pierre de Fermat, muchas de sus…
  3. Tweets that mention La función Phi de Euler: otra genialidad del maestro | Gaussianos -- Topsy.com - [...] This post was mentioned on Twitter by gaussianos, redes sociales web. redes sociales web said: #hispaciencia La función Phi…
  4. ¿Que tiene que ver el número e con los números primos? | Gaussianos - [...] esta expresión es el logaritmo neperiano, denota el -ésimo número primo y es la función de…
  5. Un problema sobre la función phi de Euler | Gaussianos - [...] 1 en La función Phi de Euler: otra genialidad del maestro [...]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *