Phi de Euler de una potencia de un numero primo

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

Phi de Euler de una potencia de un numero primo

Mensaje sin leer por Yanes » Mar 07 Ene, 2020 4:42 pm

Sea $\mathbb{P}=\{p\in \mathbb{N}-\{ 1 \}~/~\nexists ~d\in \mathbb{N}-\{p;1\}~/~d\mid p\}$ (conjunto de los números primos)

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

Si $n\in \mathbb{N},~p\in \mathbb{P} \Rightarrow \varphi \left (p^n\right )=p^n-p^{n-1}$

Demostración:
Spoiler: mostrar
Sean:
$X=\{x\in \mathbb{N}\cap [1;p^n]~/~\text{mcd}(x;p^n)=1\}$
$Y=\{y\in \mathbb{N}\cap [1;p^n]~/~\text{mcd}(y;p^n)\neq 1\}$

Es evidente que:
$\# X+\# Y=p^n$

El menor elemento de $Y$ es $\min \{y\in \mathbb{N}\cap [1;p^n]~/~\text{mcd}(y;p^n)\neq 1\}=p$

...y $p$ al ser primo, los demás elementos de $Y$ son múltiplos de $p$, es decir, $kp~/~k\in \mathbb{N}$

El mayor elemento de $Y$ es $\max \{y\in \mathbb{N}\cap [1;p^n]~/~\text{mcd}(y;p^n) \neq 1\}=p^n$

$\Rightarrow p\leq kp\leq p^n$
$1\leq k\leq p^{n-1}$

$\Rightarrow \# Y=(\text{cantidad de valores que puede tomar }k)$
$\Rightarrow \# Y=p^{n-1}$

Reemplazando:

$\# X+\# Y=p^n$
$\varphi \left (p^n\right )+p^{n-1}=p^n$
$\varphi \left (p^n\right )=p^n-p^{n-1}$

Responder