Función Totiente de Euler

Teoría

La función totiente de Euler $\varphi(n)$ te dice cuántos enteros del 1 al $n$ son coprimos con $n$. También la puedes ver como el tamaño del grupo multiplicativo de los enteros módulo $n$.

Esta función es súper importante en la teoría de números y aparece en:

• El teorema de Euler: $a^{\varphi(n)} \equiv 1 \pmod{n}$ cuando $\gcd(a,n) = 1$
• Criptografía RSA
• Problemas de conteo que tienen que ver con coprimalidad
• Teoría de grupos (el orden de $(\mathbb{Z}/n\mathbb{Z})^*$)

Nota que algunas propiedades clave hacen que $\varphi$ sea fácil de calcular: es multiplicativa (para números coprimos) y tiene una fórmula simple para las potencias de primos.

Fórmulas Clave

Definición: $$\varphi(n) = |{k : 1 \leq k \leq n, \gcd(k, n) = 1}|$$

Para un primo $p$: $$\varphi(p) = p - 1$$

Para una potencia de primo: $$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$$

Multiplicatividad:

Si $\gcd(m, n) = 1$: $$\varphi(mn) = \varphi(m) \varphi(n)$$

Fórmula de producto: $$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

Suma de totientes: $$\sum_{d \mid n} \varphi(d) = n$$

Formas alternativas: $$\varphi(n) = n \cdot \frac{p_1 - 1}{p_1} \cdot \frac{p_2 - 1}{p_2} \cdots \frac{p_k - 1}{p_k}$$

donde $p_1, \ldots, p_k$ son los factores primos distintos de $n$.

Demostración

Demostración de $\varphi(p) = p - 1$:

Los enteros del 1 al $p$ son ${1, 2, \ldots, p}$.

Como $p$ es primo, puedes ver que $\gcd(k, p) = 1$ para todo $k \in {1, 2, \ldots, p-1}$.

El único caso que no cumple es $\gcd(p, p) = p \neq 1$.

Por lo tanto, $\varphi(p) = p - 1$. $\square$

Demostración de $\varphi(p^k) = p^{k-1}(p-1)$:

De entre ${1, 2, \ldots, p^k}$, fíjate en los que NO son coprimos con $p^k$.

$\gcd(m, p^k) > 1$ si y solo si $p \mid m$.

Los múltiplos de $p$ en ${1, \ldots, p^k}$ son ${p, 2p, \ldots, p^{k-1} \cdot p}$, que son $p^{k-1}$ elementos.

Entonces: $$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$$ $\square$

Demostración de la multiplicatividad:

Supón que $\gcd(m, n) = 1$. Lo que hay que mostrar es que $\varphi(mn) = \varphi(m)\varphi(n)$.

Considera el conjunto ${0, 1, \ldots, mn-1}$ acomodado en un arreglo de $m \times n$: $$\begin{matrix} 0 & 1 & \cdots & n-1 \ n & n+1 & \cdots & 2n-1 \ \vdots & & & \vdots \ (m-1)n & & \cdots & mn-1 \end{matrix}$$

La fila $i$ contiene a ${in, in+1, \ldots, in+(n-1)}$.

Afirmación: En cada fila, exactamente $\varphi(n)$ entradas son coprimas con $n$.

Esto pasa porque ${in, in+1, \ldots, in+n-1} \equiv {0, 1, \ldots, n-1} \pmod{n}$.

Afirmación: En cada columna, exactamente $\varphi(m)$ entradas son coprimas con $m$.

La columna $j$ contiene a ${j, n+j, 2n+j, \ldots, (m-1)n+j}$.

Como $\gcd(n, m) = 1$, estos números son congruentes a ${0, 1, \ldots, m-1} \pmod{m}$ en algún orden.

Combinando todo: $\gcd(k, mn) = 1$ si y solo si $\gcd(k, m) = 1$ Y $\gcd(k, n) = 1$.

Por el Teorema Chino del Residuo (CRT), esto pasa para exactamente $\varphi(m) \cdot \varphi(n)$ valores. $\square$

Demostración de $\sum_{d \mid n} \varphi(d) = n$:

Para cada $k \in {1, \ldots, n}$, toma $d = \gcd(k, n)$.

Entonces $k/d$ es coprimo con $n/d$, y $1 \leq k/d \leq n/d$.

Esto te da una biyección: los números del 1 al $n$ corresponden a parejas $(d, j)$ donde $d \mid n$ y $1 \leq j \leq n/d$ con $\gcd(j, n/d) = 1$.

Para cada divisor $d$, hay $\varphi(n/d)$ de esos valores de $j$.

Así que $n = \sum_{d \mid n} \varphi(n/d) = \sum_{d \mid n} \varphi(d)$ si cambias el índice de la suma. $\square$