La función  de Euler

1 Denición
Sea n 2 N. Se dene (n) como

(n) := #f1 6 q 6 n: (n; q) = 1g:

Esta función aritmética : N ! N se conoce como función  de Euler. En términos

precisos: (n) cuenta el número de naturales menores que n y primos relativos a n.
Ejemplos:
(10) = 4 pues q 2 f1; 3; 7; 9g cumple que (10; q) = 1,
(30) = 8 pues q 2 f1; 7; 11; 13; 17; 19; 23; 29g cumple con (30; q) = 1.
Para n 2 N ja, al conjunto f1 6 q 6 n: (n; q) = 1g se le conoce como un sistema
reducido de residuos módulo n (en contraste con f0; 1; :::; n ¡ 1g que se conoce como
un sistema completo de residuos módulo n).

2 Fórmulas para 
Una función aritmética f : N ! R se dice que es multiplicativa si f (1) = 1 y

f (mn) = f (m)f (n) (1)

para toda pareja de naturales m; n 2 N con (m; n) = 1.

Teorema 1. (Euler) La función  es multiplicativa.

Demostración. Notemos que (1) = 1. Sean ahora m; n 2 N con (m; n) = 1. Si

m = 1 o n = 1 vemos que (1) se cumple sin problemas. Supogamos que m > 1; n > 1.
Podemos distribuir los enteros de 1 a mn en un arreglo con n columnas y m las
en cada una como sigue:

1 m+1 2m + 1


(n ¡ 1)m + 1

2 m+2 2m + 2


(n ¡ 1)m + 2
3 m+3 2m + 3


(n ¡ 1)m + 3








(2)





r m+r 2m + r


(n ¡ 1)m + r














m 2m 3m


nm

1
Sea r un natural 6m tal que (r; m) > 1. Pongamos d = (r; m), luego dj(km + r) para
todo k 2 N, es decir d > 1 divide a cualquier elemento de la r-ésima la en (2), luego
ningún elemento de esta la es primo relativo a m, y así tampoco a mn.
Esto es, los elementos en el arreglo (2) que son primos relativos a mn provienen de
la r-ésima la únicamente si (r; m) = 1. Por denición hay (m) de dichos enteros
r, y entonces (m) de dichas las.
Sea 1 6 r 6 m con (r; m) = 1. La r-ésima la tiene por elementos

r; m + r; 2m + r; :::; (n ¡ 1)m + r: (3)

Vamos a mostrar que los n elementos en esta lista son un sistema completo de
residuos módulo n. Basta para ello ver que ningún par de elementos distintos son
congruentes. Si

km + r  lm + r (mod n) ; 0 6 k; l < n (4)

entonces km  lm (mod n) y puesto que (m; n) = 1 tenemos que k  l (mod n), pero
(4) indica que k; l están en un sistema completo de residuos módulo n, luego k = l.
Esto concluye la prueba que (3) es un sistema completo de residuos módulo n, de
donde sabemos que hay (n) elementos que son primos relativos a n, luego en la r-
ésima la hay (n) elementos que son primos relativos a n y por ende a mn.
Finalmente, hay (m) las en (2) que contienen naturales primos relativos a mn
y cada la contiene (n) elementos primos relativos a ellos, luego el arreglo (2)
contiene (m)(n) enteros positivos 6mn y primos relativos a mn, es decir (mn) =
(mn). 

Corolario 2. Para toda n 2 N se tiene que

Y 1

(n) = n 1¡ ;
pjn
p

donde el producto se extiende sobre todos los divisores primos de n.

Demostración. Sea n 2 N con factorización n = p1 1


pr r. En virtud del teorema

anterior

(n) = (p1 1


pr) = (p1 1)


(pr r): (5)

Esto nos remite a calcular (pk). Sabemos que (l; pk) = 1 si y sólo si p - l. Hay pk¡1
enteros entre 1 y pk que son divisibles por p, a saber,

p; 2p; 3p; :::; (pk ¡1)p:

2
Entonces, el conjunto f1; 2; :::; pk g contiene exactamente pk ¡ pk¡1 enteros que son
primos relativos a pk, es decir (pk) = pk ¡ pk¡1 = pk(1 ¡ 1/ p). Si sustituimos esta
fórmula en (5) obtenemos

(n) = [p1 1(1 ¡ 1/ p 2 r
1)][p2 (1 ¡ 1/ p2)]


[pr (1 ¡ 1/ pr )]
   
1 2 1 1 1
= [p1 p2


pr] 1 ¡ 1¡


1 ¡
p1 p2 pr
Y 1

= n 1¡ ;
pjn
p

que es lo que se deseaba probar. 

Ejemplo 1: Sea n = 105 = 3
5
7, luego

   
1 1 1
(105) = 105 1 ¡ 1¡ 1¡
3 5 7
   
2 4 6
= 105
3 5 7
= (2)(4)(6) = 48:

Ejemplo 2: Sea n = 151875000 = 233557, luego

   
1 1 1
(151875000) = 151875000 1 ¡ 1¡ 1¡
2 3 5
   
1 2 4
= 233557
2 3 5
= 2 3 5 = 40500000:
5 4 6

Veamos otras propiedades de (n):

Teorema 3. La función  de Euler cumple con las siguientes propiedades:

(a) (mn) = (m) (n) fd/ (d)g, donde d := (m; n).

(b) Si ajb entonces (a)j(b).

(c) (n) es par para n > 3. Si n tiene r factores primos impares, entonces 2r j(n).

Demostración. Para probar (a) escribimos

 
(n) Y 1
= 1¡ :
n pjn
p

3
Enseguida notemos que cada divisor primo de mn es divisor primo de m o de n, y
aquellos primos que dividan a ambos números dividen también a d = (m; n). Por lo
tanto

(mn) Y  1

= 1¡
mn pjmn
p
Q  
1 Q

1

pjm
1¡ p pjn
1¡ p
= Q  
1
pj(m;n)
1¡ p
(m) (n)
m

n
= (d)
;
d

de donde se concluye (a).

Para probar (b) supongamos que ajb, es decir b = ac con 1 6 c 6 b. Si c = b, entonces
a = 1, y (b) se cumple sin dicultad. Enseguida supongamos que c < b. Del inciso
anterior tenemos

d (c)
(b) = (ac) = (a) (c) = d(a) ; (6)
(d) (d)

donde d = (a; c). El resultado ahora se sigue por inducción. Para b = 1 se cumple.
Supongamos que (b) se cumple para todos los enteros <b. Entonces se cumple para
c y asi (d)j(c) pues djc, luego el lado derecho de (6) es un múltiplo de (a), lo
que signica que (a)j(b).
Para probar (c), si n = 2 ;  > 2, entonces (n) = 2¡1 es par. Si n tiene al menos
un factor primo impar escribimos

Y p¡1 n Y Y
(n) = n =Q (p ¡ 1) = c(n) (p ¡ 1);
pjn
p pjn
p pjn pjn

Q
donde c(n) es un entero. El producto pjn (p ¡ 1) es par, luego (n) es par. Más
aún, cada primo impar p contribuye con un factor 2 a este producto, luego 2r j(n)
si n tiene r factores primos impares. 

3 Una identidad de Gauss

Teorema 4. (Gauss) Tenemos que
X
(d) = n; (7)
djn

donde la suma se extiende sobre todos los divisores positivos de n.

4
Demostración. En clase se vio que si una función f era multiplicativa, entonces
también lo es F denda como
X
F (n) = f (d):
djn

Puesto que  es multiplicativa, deducimos de esto que el lado izquierdo de (7)

describe una función multiplicativa, luego para probar (7) basta vericar la igualdad
en potencias de primos. Sea p primo y  2 N, si n = p tenemos que
X X
(d) = (d)
djn djp

X
= (pr)
r=0

X
= 1+ (pr)
r=1

X
= 1+ (pr ¡ pr ¡1)
r=1
= 1 + (p ¡ 1) = p = n

como se quería probar. 

Pablo González
Octubre 01, 2017