Función phi de Euler

En la teoría de números la función phi de Euler ( phi: pronunciar fi) es una función aritmética multiplicativa que nos entrega la cantidad de primos relativos ( o coprimos) y menores que el número en cuestión.

Casos ilustrativos

f(1) = 1, f(2) = 1, donde 'f' reemplaza a la letra griega phi.

f(3) = 2, los primos relativos son 1 y 2; f(4) = 2, primos relativos 1 y 3

f(5) = 4, los coprimos son 1,2,3 y 4; f(6) = 2, sólo son coprimos 1 y 5

f(7)= 6, los coprimos son 1,2,3,4,5,6

Proposición- coprimos

Asumamos que (b, p) = 1. Entonces si r1,...,rp es un sistema completo de restos módulo p, así lo es b.r1, b.r2,...b.rp

Ejemplo

(8,3) = 1, entonces el sistema de restos es 0,1,2.

Teorema

Asumamos que (b, p) = MCD(b,p) = 1, entonces la función fi de Euler preserva el producto,en este sentido f(b.p) = f(b) f(p)

Proposición- potencia de primos

Suponemos que p sea primo positivo y m número natural. Entonces f(p^m) = (p-1). p^m-1

Ejemplo

Para 16 = 2⁴ su función fi de Euler es (2-1).2_4-3 = 8, justamente 1,3,5,7,9,11,13,15.

Proposición - factores primos

Sean h1, h2,...ht los factores primos de l. Se deduce

f(l) = l. (1- 1:h1)...(1-1:ht)

ejemplo

De 90 = 2.3². 5 esulta f(90)= 2.6.4 = 48 o bien f(90) = 90. 1/2 . 2(2/3). 3/4 = 48

Fuente

Enzo R. Gentile aritmética elemental, edición de OEA