4.4: Función Phi o Totient de Euler

Última actualización
Guardar como PDF

Page ID: 111575

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Recuérdese la función phi de la Definición 4.9.

Lema 4.15 (Gauss)

Para\(n \in \mathbb{N} : n = \sum_{d|n} \varphi (d)\).

Prueba

Definir\(S(d,n)\) como el conjunto de enteros\(m\) entre\(1\) y\(n\) tal que\(\gcd (m, n) = d\):

\[S(d, n) = \{m \in \mathbb{N} | m \le n \mbox{ and } \gcd (m,n) = d\} \nonumber\]

Esto equivale a

\[S(d, n) = \{m \in \mathbb{N} | m \le n \mbox{ and } \gcd (md, dn) = 1\} \nonumber\]

De la definición de la función phi de Euler, vemos que la cardinalidad\(|S(d,n)|\) de\(S(d, n)\) viene dada por\(\varphi(\frac{n}{d})\). Así obtenemos:

\[n = \sum_{d|n} |S(d,n)| = \sum_{d|n} \varphi(\frac{d}{n}) \nonumber\]

Como\(d\) recorre todos los divisores de\(n\) en la última suma, también lo hace\(\frac{n}{d}\). Por lo tanto la última suma es igual a\(\sum_{d|n} \varphi(d)\), lo que prueba el lema.

Teorema 4.16

\(\prod_{i=1}^{r} p_{i}^{l_{i}}\)Déjese ser la factorización de poder primordial de\(n\). Entonces

\[\varphi (n) = \prod_{i=1}^{r} (1-\frac{1}{p_{i}}) \nonumber\]

Prueba

Aplicar inversión de Mobius a Lemma 4.15:

\[\varphi (n) = \sum_{d|n} \mu (d) \frac{n}{d} = n \sum_{d|n} \frac{\mu (d)}{d} \nonumber\]

Las funciones\(\mu\) y\(d \rightarrow \frac{1}{d}\) son multiplicativas. Es fácil ver que el producto de dos funciones multiplicativas también es multiplicativo. Por lo tanto también\(\varphi\) es multiplicativo (Proposición 4.3). Así

\[\varphi (\prod_{i=1}^{r} p_{i}^{l_{i}} = \prod_{i=1}^{r} \varphi (p_{i}^{l_{i}}) \nonumber\]

Por lo que es suficiente evaluar la función\(\varphi\) sobre los poderes primos. Al señalar que los divisores de la potencia prima\(p^l\) son\(\{1, p, \cdots p^l\}\), obtenemos de la Ecuación

\[\varphi (p^l) = p^{l} \sum_{j=0}^{l} \frac{\mu (p^j)}{p^j} = p^{l} (1-\frac{1}{p}) \nonumber\]

Sustituyendo esto en la Ecuación 4.4 completa la prueba.

De esta prueba obtenemos el siguiente corolario.

Corolario 4.17

La función phi de Euler es multiplicativa.