Función φ de Euler


Hoy: Otra curiosa función matemática, en este caso la función \varphi de Euler. Veamos primero su definición matemática formal:

\varphi(m) = | \left\lbrace n\in \mathbb{N} | \text{mcd}(m,n) = 1 \wedge n \leqslant m \right\rbrace |

Lo que está dentro de las llaves indica un conjunto formado por todos los números menores que m y que son coprimos con m, es decir, que el máximo común divisor de todos los números de ese conjunto con m es 1. Que el conjunto esté entre barras verticales | indica que hablamos del cardinal del conjunto, es decir, del número de elementos del conjunto.

En resumen, la función nos devuelve el número de números menores que m que son coprimos con m. Hay algunas deducciones muy directas y sencillas a partir de esto. Por ejemplo, \varphi(p) = p-1 \text{ si }p\text{ es primo}.

Es evidente. Si p es primo, eso significa que los únicos números que lo dividen son él mismo y 1, así que ninguno más tendrá con él un divisor común distinto de 1, y por lo tanto todos los números anteriores serán coprimos e irán al conjunto devuelto, el número de elementos es por tanto todos los anteriores a él: p-1.

Podemos pintar fácilmente una gráfica que dibuje los valores de la función, pero soy vago y copio la imágen de por ahí (Google Imágenes). Sin embargo, programarlo debería ser muy simple. Sólo hay que hacer una función que devuelva verdadero a falso si dos números son coprimos. Os dejo un código en matlab que lo hace, aunque usa demasiadas funciones internas, así que me gusta poco. También es de por ahí, uno se siente vago en época de exámenes:


function t = totient(n)

[r c]=size(n);
n=reshape(n,1,r*c);
t=zeros(1,r*c);
f=zeros(1,10);

for k=1:r*c;
nk=n(k);
f=unique(factor(nk));
t(k)=nk*prod(1-1./f);
end
t=reshape(t,r,c);
p=find(n==1);
t(p)=1;
t=round(t);
return

%a demo of this program is
n=(1:50).';
t=totient(n);
[n t]

Vemos una distribución bastante lineal para algunos valores, aunque es bastante más simple demostrarla que para otras funciones como los resultados de los máximos valores de los números siguiendo la conjetura de Collatz, que vimos en un artículo anterior a este.

Por ejemplo, la linea de más pendiente, la que corresponde a los valores más altos, es fácil de sacar.

Es bastante evidente que esta linea corresponde a los números primos, ya que para estos \varphi(p) = p-1, alcanzando los valores más altos. Para cualquiera dos números primos consecutivos, tenemos que la pendiente de la recta que los une es:

\frac{p_{i+1} - 1 - (p_{i}-1)}{p_{i+1}-p_i} = 1 .

Ya que la diferencia de alturas es \Delta h = p_{i+1} - 1 - (p_{i}-1), ya que son los dos valores de la función para ambos primos, y la diferencia del eje x es \Delta x = p_{i+1}-p_i. Vemos que la pendiente es 1, constante para cualesquiera dos primos consecutivos que cojamos, y por lo tanto lo será entre cualesquiera dos primos que cojamos, y esa recta pasará por encima de todos los valores. Si hacemos que pase por cualquiera de los valores, por ejemplo (2,1), obtenemos la altura de la recta (-1), y la recta es: y = x-1.

Uno de los usos de esta función es el cifrado RSA, que usa una congruencia módulo \varphi(n).

Hasta aquí por hoy, un saludo.

Anuncios
Esta entrada fue publicada en Matemáticas y etiquetada , , , , , , . 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