Función $\phi$ de Euler y teorema de Euler

De los $p^k$ enteros en $\{1, 2, \ldots, p^k\}$, los que no son coprimos con $p^k$ son exactamente los múltiplos de $p$: hay $p^{k-1}$ de ellos ($p, 2p, \ldots, p^{k-1} \cdot p$). Por tanto:

$\varphi(p^k) \;=\; p^k - p^{k-1}. \qquad \blacksquare$

Organizamos los enteros $\{1, 2, \ldots, mn\}$ en una tabla de $m$ columnas y $n$ filas:

$\begin{pmatrix} 1 & 2 & \cdots & m \\ m+1 & m+2 & \cdots & 2m \\ \vdots & & & \vdots \\ (n-1)m+1 & (n-1)m+2 & \cdots & nm \end{pmatrix}$

La columna $j$ (con $1 \leq j \leq m$) contiene los enteros $j, j+m, j+2m, \ldots, j+(n-1)m$.

Paso 1. $\gcd(j + im, mn) = 1$ si y solo si $\gcd(j, m) = 1$ (condición sobre la columna) y $\gcd(j + im, n) = 1$ (condición sobre la fila dentro de la columna).

Justificación: $mn = m \cdot n$ con $\gcd(m,n) = 1$, así $\gcd(x, mn) = 1 \iff \gcd(x, m) = 1$ y $\gcd(x, n) = 1$.

Paso 2. La columna $j$ contribuye coprimos solo si $\gcd(j, m) = 1$: hay $\varphi(m)$ tales columnas.

Paso 3. En cada columna $j$ con $\gcd(j, m) = 1$, la subcondición $\gcd(j + im, n) = 1$ depende de $i$. Como $\gcd(m, n) = 1$, los residuos $j + im \pmod n$ para $i = 0, 1, \ldots, n-1$ son una permutación completa de $\{0, 1, \ldots, n-1\}$ (porque $m$ es invertible módulo $n$). Por tanto exactamente $\varphi(n)$ valores de $i$ satisfacen $\gcd(j + im, n) = 1$.

Conclusión. El número de enteros en $\{1, \ldots, mn\}$ coprimos con $mn$ es $\varphi(m) \cdot \varphi(n)$. $\blacksquare$

Por multiplicatividad aplicada iterativamente:

$\varphi(n) \;=\; \prod_{i=1}^r \varphi(p_i^{e_i}) \;=\; \prod_{i=1}^r p_i^{e_i - 1}(p_i - 1) \;=\; \left(\prod_{i=1}^r p_i^{e_i}\right) \cdot \prod_{i=1}^r \frac{p_i - 1}{p_i} \;=\; n \prod_{p \mid n} \!\left(1 - \frac{1}{p}\right). \qquad \blacksquare$

Particionamos $\{1, 2, \ldots, n\}$ según el valor de $\gcd(k, n)$. Para cada divisor $d$ de $n$:

$\#\{k \in \{1,\ldots,n\} : \gcd(k,n) = d\} \;=\; \#\{j \in \{1,\ldots,n/d\} : \gcd(j, n/d) = 1\} \;=\; \varphi(n/d).$

(Razonamiento: $\gcd(k, n) = d$ si y solo si $k = dj$ con $\gcd(j, n/d) = 1$ y $1 \leq j \leq n/d$.)

Sumando sobre todos los divisores $d$ de $n$:

$n \;=\; \sum_{d \mid n} \varphi(n/d) \;=\; \sum_{e \mid n} \varphi(e), \qquad \blacksquare$

cambiando variable $e = n/d$.

Consideramos el sistema reducido de residuos $\{r_1, r_2, \ldots, r_{\varphi(n)}\}$ módulo $n$: los $\varphi(n)$ enteros en $\{1, \ldots, n\}$ coprimos con $n$.

Como $\gcd(a, n) = 1$, la función $x \mapsto ax \pmod n$ es una biyección del sistema reducido en sí mismo: cada $ar_i$ es coprimo con $n$ (pues $\gcd(ar_i, n) = \gcd(a,n)\gcd(r_i, n) = 1$) y todos son distintos (si $ar_i \equiv ar_j$, la cancelación da $r_i \equiv r_j$).

Por tanto $\{ar_1, ar_2, \ldots, ar_{\varphi(n)}\}$ es una permutación de $\{r_1, \ldots, r_{\varphi(n)}\}$ módulo $n$. Multiplicando:

$\prod_{i=1}^{\varphi(n)} (ar_i) \;\equiv\; \prod_{i=1}^{\varphi(n)} r_i \pmod n.$

Esto da $a^{\varphi(n)} \cdot (r_1 r_2 \cdots r_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n$. Como cada $r_i$ es coprimo con $n$, también su producto lo es. Cancelando: $a^{\varphi(n)} \equiv 1 \pmod n$. $\blacksquare$