Función Totient de Euler — Teoría de números

Jan 13 2023

Euler, una de las personas más ocupadas en la historia de las Matemáticas, demostró por primera vez esta función en 1763. Trató de usar pi (π) para denotar la función, pero resultó que pi estaba ocupado.

Euler, una de las personas más ocupadas en la historia de las Matemáticas, demostró por primera vez esta función en 1763. Trató de usar pi ( π) para denotar la función, pero resultó que pi estaba ocupado. En 1801, Gauss sugirió que usáramos phi ( ) en su lugar. Fue nombrada 'Función Totient' en 1879, por James Joseph Sylvester.

Cuando le digo a la gente que me gustan las matemáticas...

Con el nombre y la notación definidos, veamos qué hace. Un par coprimo es donde el máximo común divisor que comparten dos números es 1. No tienen factores comunes mayores; son relativamente primos.

La función Totient nos dice cuántos coprimos tiene un número más pequeño que él mismo. Los coprimos más pequeños del 9 son 1, 2, 4, 5, 7 y 8. (9) = 6. Pero, ¿cómo hace eso?

Encontrando al Tociente

para números primos

Para números primos, el valor de Totient es 1menor que él mismo. Todo número menor que un número primo es primo relativo a él. Esta es la definición de un número primo. Entonces, para cualquier número primo p, (p) = p -1. Eso fue bastante simple.

Para poderes primarios

Para un número primo pelevado a una potencia k, los únicos números menores pᵏque NO son sus coprimos son otros múltiplos de p. Esto se debe a que pes el único factor en pᵏ.

Todo pᵏfactor de se puede representar: p, 2p, 3p, ..., pᵏ⁻¹p.

pᵏ⁻¹es necesariamente el mayor múltiplo de pmayor o igual que pᵏporque pᵏ⁻¹p = p.

Por tanto sabemos que pᵏtiene pᵏ⁻¹números menores que él que no son coprimos. Hay pᵏnúmeros enteros menores que pᵏ. Si pᵏ⁻¹no son coprimos, entonces pᵏ - pᵏ⁻¹los enteros son coprimos con pᵏ.

Para potencias primas, la fórmula para contar coprimos menores que es: (pᵏ) = pᵏ - pᵏ⁻¹.

para todo lo demás

Para aquellos números que no son ni primos ni potencias primas, usamos la fórmula del producto de Euler. Funciona de la siguiente manera.

Resolviendo para n, que tiene jfactores primos, la fórmula del producto toma la forma:

n x (1 — 1/p₁) x (1 — 1/p₂) x ... x (1 — 1/pⱼ).

n = 42
> which has 3 prime factors
j = 3
ϕ(42) = ϕ(7 x 2 x 3) = 42 x (1 — 1/7) x (1 — 1/2) x (1 — 1/3) = 12.
ϕ(42) = 12

Uno de los factores primos de 42 es 3. Sabemos que 1 de cada 3 números es múltiplo de 3, y los otros 2 de 3 no lo son. Así que multiplicamos 42 por 2/3para darnos la cuenta de números menores que 42 que no comparten el factor 3.

Repetir este proceso para todos los números primos de 42 se ve así: 6/7 x 1/2 x 2/3 = 6/21. Esto nos da la proporción de todos los números menores de 42 que no comparten ninguno de sus factores primos. Para obtener el conteo, podemos hacer la proporción multiplicada por el total: 6/21 x 42 = 12.

También podemos usar esto como una prueba corroborativa para los poderes primarios. Encontramos que para cualquier potencia prima pᵏ, el valor total es (pᵏ) = pᵏ - pᵏ⁻¹.

pᵏ — pᵏ⁻¹
pᵏ — (pᵏ x p⁻¹)
pᵏ — (pᵏ x 1/p)
pᵏ(1 — 1/p)

Uso de la función Totient

Está equipado para encontrar su valor en cualquier caso, pero ¿por qué querría hacerlo? El Totient de Euler se apoya mucho cuando se trabaja con la función de Carmichael, como vimos en nuestra explicación en una publicación anterior . En consecuencia, es muy importante la criptografía digital.