Funcion Phi de Euler φ(mn) = φ(m) φ(n) / mcd(m:n) = 1

[Yanes]

Sean $m,n\in \mathbb{N}~/~\text{mcd}(m;n)=1$

Sea $\varphi :\mathbb{N}\rightarrow \mathbb{N}$

$/~\varphi (n)=\#\{x_i\in \mathbb{N}\cap [1;n]~/~\text{mcd}(x_i;n)=1\}$

$\Rightarrow \varphi (mn)=\varphi (m)\varphi (n)$

Demostración:

Spoiler: mostrar

Sean:

$\Phi _m=\{x_i\in \mathbb{N}\cap [1;m]~/~\text{mcd}(x_i;m)=1\}$

$\Phi_ n=\{y_i\in \mathbb{N}\cap [1;n]~/~\text{mcd}(y_i;n)=1\}$

$\Phi _{mn}=\{z_i\in \mathbb{N}\cap [1;mn]~/~\text{mcd}(z_i;mn)=1\}$

Sean $\alpha _m\leq m$, $\alpha _n\leq n$, $\alpha _{mn}\leq mn$, tal que:

$\alpha _{mn}\equiv \alpha _m\pmod m$
$\alpha _{mn}\equiv \alpha _n\pmod n$

Si $\alpha _m\in \Phi _m\Rightarrow \text{mcd}(\alpha _m;m)=1\Rightarrow \text{mcd}(\alpha _{mn};m)=1$

Si $\alpha _n\in \Phi _n\Rightarrow \text{mcd}(\alpha _n;n)=1\Rightarrow \text{mcd}(\alpha _{mn};n)=1$

$\Rightarrow \text{mcd}(\alpha _{mn};mn)=1$

Añadimos la condición: $\text{mcd}(m;n)=1$

$\Rightarrow \exists ~ \beta _1,\beta _2\in \mathbb{N}$ tal que:

$n\beta _1\equiv 1\pmod m$
$m\beta _2\equiv 1\pmod n$

Según el Teorema Chino del Resto:

$n\beta _1\alpha _m+m\beta _1\alpha _n\equiv \alpha _{mn}\pmod{mn}$

Pero $\alpha _{mn}\leq mn$

Entonces $\forall \alpha _m\in \Phi _m,\alpha _n\in\Phi _n\Rightarrow \exists !~\alpha _{mn}\in \Phi _{mn}$

Sea $f:\Phi _m\times \Phi _n\rightarrow \Phi _{mn}$

$/~f(\alpha _m;\alpha _n)=\alpha _{mn}$

Por lo que vimos, se deduce que $f$ es biyectiva

Entonces el cardinal de la imagen es igual al del dominio:

$\#\{\Phi _{mn}\}=\#\{\Phi _m\times \Phi _n\}$

$\#\{\Phi _{mn}\}=\#\{\Phi _m\}\#\{\Phi _n\}$

$\varphi (mn)=\varphi (m)\varphi (n)$