En el día de hoy hemos visto la función $\varphi $ de Euler. Esta función se define como
$$\varphi (n)=|\{m\in\mathbb{Z}^+|m<n, mcd(n,m)=1\}|.$$
Esta función cumple propiedades muy interesantes, como
- Si $p$ es primo, $\varphi (p)=p-1$
- Si $p$ es primo, $\varphi (p^\alpha)=p^{\alpha -1}(p-1)$
- Si $mcd(n,m)=1$ es $\varphi (nm)=\varphi (n)\varphi (m)$
Estos resultados nos sirven para exponer el Teorema de Euler:
Si $a,n\in\mathbb{Z}$ con $mcd(n,a)=1$, entonces $a^{\varphi (n)}\equiv 1(n)$
Este resultado ofrece además una forma de obtener el inverso de un número en $\mathbb{Z}_n$, siempre que este exista.
La descomposición de un numero entero en sus factores primos nos permite formular un resultado práctico para calcular la función $\varphi$
Si $n\in\mathbb{Z}$ es ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$, entonces $$\varphi (n)=n\sum_{i=1}^r\left(1-\frac{1}{p_i}\right)$$
$\quad $
| Ejercicio: Resolver $123321^{123}\equiv X(36)$ |