Para discutir problemas de competencias para graduados de secundaria (Número de Oro, CIMA/Paenza, etcétera) y problemas que requieran conocimientos avanzados.
Yanes
Mensajes: 27 Registrado: Lun 05 Nov, 2018 8:59 pm
Medallas: 2
Nivel: Exolímpico
Mensaje sin leer
por Yanes » Mié 11 Dic, 2019 7:04 pm
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)$