Función Phi (φ) de Euler

También llamada función totiente o función indicatriz de Euler

¿Cuántos números enteros de 1 al n no comparten ningún factor primo con n?

Ejemplo: 6

6 tiene los factores primos de 2 y 3

Comprobemos cada número entero del 1 al n:

1 no tiene factores 2 o 3
2 tiene el factor 2
3 tiene el factor 3
4 tiene el factor 2
5 no tiene factores 2 o 3
6 tiene los factores 2 y 3

Entonces solo hay 2 números enteros sin los factores 2 o 3.

Respuesta: 2

La idea de "no compartir ningún factor primo" a menudo se abrevia como "coprimo" o "relativamente primo".

Y así obtenemos la función totiente de Euler (símbolo φ)

φ(n) = cuántos números enteros de 1 al n son coprimos con n

¡Probemos con otro!

Ejemplo: 12

Comienza con los números enteros del 1 al 12:

1 2 3 4 5 6 7 8 9 10 11 12

12 tiene los factores primos 2 y 3 , por lo que podemos tachar cualquier múltiplo de 2 o 3:

1 2 3 4 5 6 7 8 9 10 11 12

Nos quedan 4 números enteros coprimos con 12:

Respuesta: 4

¡Tú turno!

Prueba con 15:

Empieza con:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

15 tiene los factores primos de 3 y 5, el resto depende de ti.

(Obtenemos 8 enteros coprimos con 15).

Todos estos son ejemplos de la función totiente de Euler, la cual se representa con el símbolo φ (la letra griega Phi)

φ(6) = 2
φ(12) = 4
φ(15) = 8

Es así de simple, simplemente tachando números de una lista.

Pero, por supuesto, puede llevar mucho tiempo, por lo que cualquier ahorro de tiempo sería útil. ¡Descubramos algunas formas de ahorrar tiempo!

Números primos

¿Qué pasa con los números primos?

Ejemplo: 5

5 es primo. Sólo tiene un factor primo: ¡él mismo!

Entonces todos los demás números de la lista son coprimos de 5:

1 2 3 4 5

Respuesta:

φ(5) = 4

Esto es generalmente cierto para todos los números primos:

φ(p) = p − 1
(donde p es un número primo)

Tenemos nuestro primer ahorro de tiempo.

El mismo número primo más de una vez

¿Qué pasa si volvemos a multiplicar por el mismo primo?

Ejemplo: 25

25 es 5 × 5:

1 2 3 4 5

6 7 8 9 10

1112131415

1617181920

2122232425

Obtenemos lo mismo 5 veces.

φ(25) = 5 × φ(5)
= 5 × 4
= 20

Y obtenemos:

un solo factor primo:(p − 1)

un mismo factor primo dos veces:p(p − 1)

un mismo factor primo tres veces:p²(p − 1)

un mismo factor primo "a"veces:p^a-1(p − 1)

Tenemos nuestro siguiente ahorro de tiempo:

φ(p^a) = p^a-1(p − 1)
(donde p es un número primo)

Ejemplo: 81

81 es 3⁴

φ(p^a) = p^a-1(p − 1)
φ(3⁴) = 3^4-1(3 − 1)
= 3³(2)
= 27 × 2
= 54

Dos primos diferentes

¿Qué pasa si tenemos dos números primos diferentes multiplicados entre sí?

Ejemplo: 14

14 es 2 por 7

Podemos eliminar todos los múltiplos de 2, hay 14/2 = 7 de esos:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

También podemos eliminar todos los múltiplos de 7, hay 14/7 = 2 de esos:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Hasta ahora hemos eliminado 7+2 = 9, pero ¡ups!, ¡contamos 14 dos veces!

Entonces, de hecho, solo eliminamos 8, dejando 14 − 8 = 6 que son coprimos:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

φ(14) = 6

¡Esto es generalmente cierto! Podemos calcular cuántos de cada factor primo eliminamos, ajustar los conteos dobles y luego calcular cuántos quedan.

Y podemos hacer una fórmula para ello:

Comenzamos con n=pq, eliminamos n/p números, luego n/q números y ajustamos el conteo:

Iniciamos con esto: n − ( np + nq − 1)

Quitamos paréntesis: n − np − nq + 1

Multiplicamos por pqn (=1): pq − q − p + 1

Y simplificamos: (p − 1)(q − 1)

El resultado es notablemente simple:

φ(pq) = (p − 1)(q − 1)
(donde p y q son primos distintos)

Hasta ahora hemos descubierto:

φ(p) = (p − 1)
φ(pq) = (p − 1)(q − 1)

De hecho, generalmente funciona:

φ(pqr) = (p − 1)(q − 1)(r − 1)
etc...

¡Pero todos los números primos deben ser distintos!

¿Qué pasa con una mezcla de números primos, algunos diferentes y otros iguales?

Ejemplo: 60

Los factores primos de 60 son 2, 2, 3 y 5.

2 aparece dos veces, así que dejemos de lado el 2 adicional por el momento.

φ(30) = (p − 1)(q − 1)(r − 1)

= (2 − 1)(3 − 1)(5 − 1)

= 1 × 2 × 4

= 8

Por último multiplicamos por el 2 que reservamos al principio:

φ(60) = 16

Entonces el algoritmo es:

Divide el número en sus factores primos.
Deja de lado cualquier factor duplicado.
Utiliza φ(pqr...) = (p − 1)(q − 1)(r − 1)... en los factores restantes.
Termina multiplicando por los factores que se reservaron.

¡Una mejor versión!

Hay una fórmula más clara que hace todo eso:

φ(n) = n (p₁ − 1p₁)(p₂ − 1p₂) ... (p_z − 1p_z)

Comienza con n, luego lo multiplica de forma especial para reducirlo como hicimos con anteriormente.

Ejemplo: 60 (otra vez)

Los distintos factores primos de 60 son 2, 3 y 5.

φ(60) = 60 × ( 2−12 )( 3−13 )( 5−15 )

φ(60) = 60 × ( 12 )( 23 )( 45 )

= 16

¿Qué hicimos? Empezamos con 60, luego:

eliminamos todos los factores de 2, que es lo mismo que multiplicar por 1/2
eliminamos todos los factores de 3, que es lo mismo que multiplicar por 2/3
eliminamos cada factor de 5, que es lo mismo que multiplicar por 4/5

¡Y como los aplicamos uno tras otro, no hay riesgo de contar doblemente!

Si estás haciendo el cálculo manualmente, intenta reemplazar n con todos sus factores, esto facilita la cancelación:

Ejemplo: 60 (una vez más)

φ(60) = 2×2×3×5 × (12)(23)(45)

= 2×2×3×5 × (12)(23)(45)

= 16

Toma en cuenta que la fórmula a menudo se escribe en esta forma (la cual es exactamente equivalente):

φ(n) = n (1 − 1p₁)(1 − 1p₂) ... (1 − 1p_z)

Cualquiera de esas fórmulas nos permite encontrar φ(n) para cualquier número entero superior a 1, porque los números enteros superiores a 1 son primos o producto de primos. Lee sobre el teorema fundamental de la aritmética.

Otra fórmula

Hay otra fórmula general:

φ(n) = p₁^k₁−1(p₁ − 1)p₂^k₂−1(p₂ − 1) ... p_z^k_z−1(p_z − 1)

Donde p₁, p₂, etc . son primos distintos y los exponentes k₁, k₂, etc. son sus exponentes.

En esta fórmula se puede visualizar de forma clara cómo se puede calcular la función para números que tienen factores primos únicos o repetidos. Hagamos nuestro ejemplo anterior nuevamente para ver:

Ejemplo: 60 (una vez más)

Los factores primos de 60 son 2, 2, 3 y 5, y usando exponentes obtenemos:

60 = 2² × 3 × 5

La fórmula para tres primos distintos:

φ(n) = p₁^k₁−1(p₁ − 1)p₂^k₂−1(p₂ − 1)p₃^k₃−1(p₃ − 1)

Sustituimos p₁=2, k₁=2, p₂=3, k₂=1, p₃=5, k₃=1:

φ(60) = 2²⁻¹(2 − 1)3¹⁻¹(3 − 1)5¹⁻¹(5 − 1)

= 2¹(1)3⁰(2)5⁰(4)

= 2 × 2 × 4

= 16

¿Ves cómo el 2 tenía un exponente de 1 (2¹=2) por lo que los 2 adicionales duplican el resultado, pero los otros primos tenían un exponente de 0 (3⁰=1 y 5⁰=1) y se ignoran?

Propiedad multiplicativa

Esto también es cierto:

φ(pq) = φ(p)φ(q)
(donde p y q son coprimos, así que no comparten ningún factor)

Para mostrar por qué esto funciona, veamos un ejemplo:

Ejemplo: 6×7 = 42

Colocamos los números en una tabla de 6×7:

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

Elimina todos los números que no sean coprimos con 6, es decir, aquellos con factores de 2 o 3:

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

Nos quedan exactamente φ(6) = 2 columnas.

Siguiente: elimina todos los números que no sean coprimos a 7, es decir, cualquiera que tenga un factor de 7:

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

Cada columna termina con exactamente φ(7) = 6 entradas.

Entonces una tabla de 6×7 termina como φ(6)=2 por φ(7)=6.

Y nuestra respuesta es que φ(6×7) = φ(6)×φ(7) = 2×6 = 12.

Prueba esto tú mismo con 3×5, o tal vez 5×7, solo asegúrate de que los dos factores sean coprimos (sin factores compartidos).

Usos

La función totiente de Euler es muy útil en teoría de números y tiene un papel central en la criptografía RSA .

Resumen

La función totiente de Euler φ indica cuántos números enteros del 1 al n son coprimos a n
Coprimo significa "no compartir ningún factor"
Para un número primo: φ(p) = p − 1
Para las potencias de un número primo: φ(p^a) = p^a-1(p − 1)
Fórmulas generales (p_r son números primos):

φ(n) = n (p₁ − 1p₁)(p₂ − 1p₂) ... (p_z − 1p_z)

φ(n) = n (1 − 1p₁)(1 − 1p₂) ... (1 − 1p_z)

φ(n) = p₁^k₁−1(p₁ − 1)p₂^k₂−1(p₂ − 1) ... p_z^k_z−1(p_z − 1)

Propiedad multiplicativa (p y q son coprimos):

φ(pq) = φ(p)φ(q)

¡Refuerza tu aprendizaje resolviendo los siguientes retos sobre este tema! (Nota: están en inglés).

25373, 25374, 25375, 25376, 25377, 25378, 25379, 25380, 25381, 25382

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
31	32	33	34	35	36
37	38	39	40	41	42