Funcion φ De Euler

Definición: Para $n>1$ denotamos por $\phi(n)$ al número de enteros positivos menores que $n$, sin excluir a $n$, que son relativamente primos que $n$. Esta función es llamada la función $\phi$ de Euler.

Así $\phi(30) = 8$ pues de entre los enteros positivosque no esceden a $30$ y que son primos con $30$ tenemos al 1, 7 11,113,17,19,23,29.

Notemos que $\phi(1)=1$ pues $(1,1)=1$. Si $n>1$ entonces $(n,n)= n\ne 1$ y por lo tanto $\phi(n) \le n-1$.

Si $n$ es un número primo, entonces cada entro menor que $n$ es primo relativo con con $n$, así que $\phi(n) = n-1$. Por otro lado si $n>1$ y $\phi(n) = n-1$ entonces $n$ tiene que ser primo pues de lo contrario $n$ tiene un divisor $d$ tal que $1<d<n$ y entonces $\phi(n) \le n-2$. Esto demuesta la siguiente:

Proposición: $n>1$ es primo sí y sólo sí, $\phi(n) = n-1$.

Teorema: Si $p$ es primo y $k>0$, entonces $\phi(p^k)= p^k-p^{k-1} = p^k(1-\frac 1p)$.

Lo que queremos ahora es dar una fórmula para calcular $\phi(n)$ basada en la factorización en números primos. Lo que nos falta entonces es demostrar que $\phi$ es una función multiplicativa.

Lema: Dados enteros $a,b,c$ tenemos que $(a,bc)=1$ si y sólo si $(a,b)=1$ y $(a,c)=1$.

Teorema: La función $\phi$ es multiplicativa.

Demostración: Tenemos que demostrar que $\phi(nm)=\phi(n)\phi(m)$ siempre que $(n,m)=1$. Si alguno de los dos $m \lor n =1$ entonces como $\phi(1)=1$ el resultado es claro. Asumamos pues que $n,m>1$. Podemos acomodar a todos los enteros positivos menores o iguales a $mn$ en filas de la forma:

(1)
\begin{align} 1, 2, \cdots, r, \cdots, m\\ m+1, m+2, \cdots m+r, \cdots, 2m\\ \vdots\\ (n-1)m+1, (n-1)m =2, \cdots, (n-1)m+r, \cdots, nm\\ \end{align}

y como $\phi(nn)$ es el número de enteros en el arreglo anterior que son primos relativos con $mn$, por el lema vamos que esto es equivalente a encontrar a los números que son primos relativos tanto con $n$ como con $n$.

Notemos que $(km+r,m)=(r,m)$ por lo que en cada renglon hay exactamente $\phi(m)$ enteros que son prmos relativos con $m$ y de hecho si en una comumna hay un entero primo relativo con $m$, todos los elementos de la columna son primos relativos con $m$, es decir hay exactamente $\phi(m)$ columnas formadas por enteros primos relativos con $m$. Ahora si suponemos que la columna $r$ está formada por enteros primos relativos con $m$ afirmamos que en esta columna hay exactamente $\phi(n)$ enteros primos relativos con $n$ pues todos estos enteros son distintos y $n$ no divide a la diferencia entre cualequiera dos de ellos, esto es, el residuo de cada uno de estos números al ser dividido entre $n$ es distinto (notar que $(m,n)=1$ y por lo tanto los residuos de esta columna son los enteros $0,1,2,3,\ldots, n-1$ en distinto orden. Por lo tanto en la tabla habrá exactamente $\phi(n)\phi(m)$ números que son primos relativos tanto a $n$ como a $m$ y por lo tanot $\phi(nm)=\phi(n)\phi(m)$ es decir $\phi$ es multiplicativa.

Teorema: Si $n>1$ tiene factorización en primos dada por $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, entonces:

(2)
\begin{align} \phi(n)= n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_r}). \end{align}

Ejemplo: Calcular $\phi(360)$.

Teorema: Para $n>2$ se tiene que $\phi(n)$ es un número par.

Demostración: 1) El caso $n=2^k$ con $k>1$ se sigue con facilidad.
2) Si $n$ no es una potencia de 2, entonces lo divide un primo impar $p$ y entonces $n=p^\alpha m$ com $(p^\alpha,m)=1$ por lo que $\phi(n)=\phi(p^\alpha)\phi(m)$ y como $\phi(p^\alpha)= p^{\alpha-1}(p-1)$ y $(p-1)$ es par, el resultado se sigue.

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License