Congruencias · Definición

Función φ de Euler

teoría de números elementalcongruencias

Antes de empezar necesitas conocer

Aparece al estudiar los residuos invertibles módulo n y es pieza central del teorema de Euler. Su cálculo se apoya en la factorización de n en primos.

Definición

La función \(\varphi\) de Euler asigna a cada entero positivo \(n\) la cantidad de enteros entre 1 y \(n\) que son coprimos con \(n\).

\[\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)\]

Si \(\gcd(m,n)=1\), entonces \(\varphi(mn)=\varphi(m)\varphi(n)\), y para un primo \(p\) se cumple \(\varphi(p^k)=p^{k-1}(p-1)\). Estas reglas, junto con \(\varphi(1)=1\), permiten calcular la función a partir de la factorización de n. La propiedad multiplicativa es la más útil en la práctica.

Para \(n=36=2^2\cdot 3^2\) se aplica la fórmula por primos: \(\varphi(36)=36\cdot\frac{1}{2}\cdot\frac{2}{3}=12\). Otra vía es contar: de los 36 enteros se excluyen los pares y los múltiplos de 3, y quedan 12 coprimos con 36.

Un error frecuente es escribir \(\varphi(n)=n-1\) para todo \(n\), fórmula que solo vale cuando \(n\) es primo. Para \(n=9\), la respuesta correcta es 6 y no 8, porque también hay que excluir el 3 y el 6, que no son coprimos con 9.

Para pensar

¿Por qué φ(n)=n-1 solo vale cuando n es primo?

Porque solo si n es primo todos los enteros de 1 a n-1 son coprimos con n; si n es compuesto, un divisor primo de n excluye algunos.

Ejercicios 10

Después de esto

Teorema de Euler

Referencias

David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 7
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2