Teorema de Euler & Fermat de Aritmética modular

Para discutir problemas de competencias para graduados de secundaria (Número de Oro, CIMA/Paenza, etcétera) y problemas que requieran conocimientos avanzados.
Avatar de Usuario
Yanes

OFO - Medalla de Bronce-OFO 2020 COFFEE - Mención-COFFEE Carolina González
Mensajes: 23
Registrado: Lun 05 Nov, 2018 8:59 pm
Medallas: 2
Nivel: Exolímpico

Teorema de Euler & Fermat de Aritmética modular

Mensaje sin leer por Yanes » Lun 06 Ene, 2020 9:26 pm

Sea $\text{mcd}:{\mathbb{N}}^{2} \rightarrow \mathbb{N}$
$/\text{mcd}(m;n)=\max \{d\in \mathbb{N}~/~d\mid m,~d\mid n\}$

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

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

$\Rightarrow a^{\varphi (n)}\equiv 1\pmod n$

Demostración:
Spoiler: mostrar
Hay $\varphi(n)$ números menores o iguales a $n$ y coprimos con $n$

Sea $\alpha _i$ el $i$-ésimo número coprimo menor o igual a $n\Rightarrow 1\leq i\leq \varphi (n)$

Sea $\beta _i=a\alpha _i$
$\Rightarrow \text{mcd}(\beta _i;n)=1$

Sea $x_i~/~\beta _i\equiv x_i\pmod n$
Si $x_i$ es menor a $n \Rightarrow x_i$ es solución única
$\Rightarrow \beta _i-x_i$ es un múltiplo de $n$
$\Rightarrow \beta _i-x_i=nm_i$

Si $\text{mcd}(x_i;n)=k_i$
$\Rightarrow \exists ~ x_i',n'\in \mathbb{N}~/~x_i=x_i'k_i,~n=n'k_i$

$\Rightarrow \beta _i=nm_i+x_i=n'k_im_i+x_i'k_i=k_i(n'm_i+x_i')$
$\Rightarrow \beta _i$ es un múltiplo de $k_i$
Tambien $n$ es un múltiplo de $k_i$
$\Rightarrow \text{mcd}(\beta _i;n)$ es un múltiplo de $k_i$

Pero dijimos que $mcd(\beta _i;n)=1$
$\Rightarrow 1$ es múltiplo de $k_i$
$\Rightarrow k_i=1$

$\Rightarrow \text{mcd}(x_i;n) =1$
$\Rightarrow x_i=\alpha _j$

Si $i\neq j\Rightarrow \beta _i\equiv \alpha _j\pmod n$
$\beta _i+anu_i\equiv \alpha _j\pmod n/u_i\in \mathbb{N}$
Sea $\beta _i+anu_i=\beta _h$

Pero $\beta _i=a\alpha _i$
$\Rightarrow \beta _h=a\alpha _h$
$\beta _i+anu_i=a\alpha _h$
$a\alpha _i+anu_i=a\alpha _h$
$a(\alpha _i+nu_i)=a\alpha _h$
$\alpha _i+nu_i=\alpha _h$

Pero habíamos definido a $\alpha _i\leq n$
$\Rightarrow \alpha _h\leq n$
$\alpha _i+nu_i\leq n$
$\alpha _i\leq n-nu_i$
$\alpha _i\leq n(1-u_i)$

Pero $u_i\in \mathbb{N}$
$\Rightarrow 1\leq u_i$
$1-u_i\leq 0$
$n(1-u_i)\leq 0$

Por transitividad de las desigualdades
${\alpha}_i\leq 0$
Lo cual es un absurdo e indica que estrictamente $i=j$

$\Rightarrow$ A cada $\beta _i$ le corresponde un solo $\alpha _i$
$\beta _1\equiv \alpha _{j_1}\pmod n$
$\beta _2\equiv \alpha _{j_2}\pmod n$
...
$\beta _{\varphi (n)}\equiv \alpha _{j_{\varphi (n)}}\pmod n$

$\Rightarrow \prod \limits _{i=1}^{\varphi (n)}\beta _i\equiv \prod \limits _{i=1}^{\varphi (n)}\alpha _{j_i}\pmod n$

Los elementos del conjunto $\{j_1;j_2;\ldots ;j_{\varphi (n)}\}$ son los mismos que los elementos del conjunto $\{1;2;\ldots ;\varphi (n)\}$ en algún orden

$\Rightarrow \prod \limits _{i=1}^{\varphi (n)}\beta _i\equiv \prod \limits _{i=1}^{\varphi (n)}\alpha _i\pmod n$

$\prod \limits _{i=1}^{\varphi (n)}a\alpha _i\equiv \prod \limits _{i=1}^{\varphi (n)}\alpha _i\pmod n$

$\prod \limits _{i=1}^{\varphi (n)}a\prod \limits _{i=1}^{\varphi (n)}\alpha _i\equiv \prod \limits _{i=1}^{\varphi (n)}\alpha _i\pmod n$

Si $\text{mcd}(\alpha _i;n)=1\Rightarrow \text{mcd}\left (\prod \limits _{i=1}^{\varphi (n)}\alpha _i~;~n\right )=1$

$\Rightarrow \prod \limits _{i=1}^{\varphi (n)}a\equiv 1\pmod n$

$\Rightarrow a^{\varphi (n)}\equiv 1\pmod n$

Responder