Funzione $\phi$ di Eulero

[ladepie]

http://yfrog.com/0p17463915j
come si deduce che i numeri non primi con $p^r$ sono $p^{r-1}$?

[Lord K]

Se ci pensi gli unici che possono avere $mcd(p^r,n)$ sono tutti quelli del tipo $p^s$... quanti sono?

[ladepie]

per me sono $s+1$
ovvero i numeri del tipo $p^k$ con $k$ che va da $0$ a $s$...

[Lord K]

Devi togliere lo zero... anche perchè in quel caso $mcd()$ è uguale a uno

[misanino]

"ladepie":http://yfrog.com/0p17463915j
come si deduce che i numeri non primi con $p^r$ sono $p^{r-1}$?

A dire la verita' tu devi mostrare che i numeri minori o uguali di $p^r$ che non sono primi con $p$ sono $p^{r-1}$
(ma e' la stessa cosa di cercare i numeri minori o uguali di $p^r$ che non sono primi con $p^r$).
Ora dato un numero $n$ esso e' non primo con $p$ solo se contiene il fattore $p$ (dato che $p$ e' primo).
Percio' $n$ deve essere della forma $n=m\cdot p$.
Inoltre $n\leq p^r$ e quindi $(m\cdot p)\leq p^r$ e quindi (dividendo per $p$) si ha $m\leq p^{r-1}$.
Percio' i numeri $n$ non primi con $p$ e piu' piccoli o uguali di $p^r$ sono i numeri del tipo $n=m\cdot p$ dove $m$ va da 1 a $p^{r-1}$ e quindi sono $p^{r-1}$ numeri