Introducing Euler’s phi function

Esta entrada, con un título muy a lo Keynote de Apple, vamos a dedicarla a una de las funciones más importantes de la teoría de números: la función \varphi de Euler.

Esta función cuenta el número de números primos con otro dado, esto es, cuántos números tienen máximo común divisor igual a uno con otro número fijo. Matemáticamente, la función \varphi puede expresarse de la siguiente manera

\displaystyle \varphi(n) =\sum_{k\leq n,\,\gcd(k,n)=1} 1

Por ejemplo, si n=8 entonces \varphi(8) = 1+1+1+1 = 4. Hay un uno por cada número que es primo con 8, en este caso 1,3,5 y 7. Una primera propiedad de esta función es la siguiente. Si n=p es un número primo, entonces

\displaystyle \varphi(p) = p-1

Esto es claro: todos los números anteriores a p son primos con él.

Aparte de la anterior, tenemos las siguientes importantes propiedades

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

\displaystyle \varphi(ab) = \varphi(a)\varphi(b),  cuando \gcd(a,b)=1

La primera de ellas es una extensión de la primera propiedad que hemos dado. La segunda se conoce como propiedad multiplicativa de la función \varphi.

Consecuencia del teorema fundamental de la aritmética, y las dos últimas propiedades expresadas, tenemos una fórmula de representación de \varphi para todo número natural

\displaystyle \varphi(n) = n \left(1 - \frac{1}{p_1}\right)\cdots \left(1 - \frac{1}{p_k}\right)

donde los p_1,\ldots,p_k son los primos que factorizan n. Un ejemplo de uso de la anterior fórmula sería el siguiente: pongamos que n=3150. Vemos que es un número par, la suma de sus dígitos es múltiplo de 3, es múltiplo de 5…total, sabemos que se factoriza como

\displaystyle 3150 = 2\cdot 3^2 \cdot 5^2 \cdot 7

Aplicando la fórmula anterior vemos que 3150 tiene por debajo a

\displaystyle \varphi(3150) = 3150\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right) = 720

números que son primos con él.

…y esto,  ¿tiene alguna aplicación?

 La más inmediata, y menos conocida por el público en general, tal vez sea la generalización del Pequeño Teorema de Fermat, el Teorema de Euler. El primero de ellos afirma que, si a y p son dos números primos entre sí, con p primo, entonces

\displaystyle a^{p-1}\equiv 1\mod p

Como ejemplo, si p=13 y a=5 entonces

\displaystyle 5^{12}\equiv 25^6\equiv 12^6 \equiv (-1)^6 \equiv 1\mod 13

El Teorema de Euler generaliza el resultado anterior. Éste establece que para a y n primos entre sí se tiene

\displaystyle a^{\varphi(n)}\equiv 1\mod n

……y esto,  ¿tiene alguna aplicación?

¡Por supuesto! La función \varphi, junto con el Teorema de Euler, forman el núcleo del algoritmo de encriptación de clave pública RSA, usado por todos y cada uno de nosotros cada día. Por ejemplo, al identificarnos en nuestra red social favorita.

De este algoritmo hablaremos en una entrada posterior.

Anuncios
Esta entrada fue publicada en Uncategorized. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s