da ficus2002 » 20/03/2006, 23:57
Se $n$ è una potenza di $2$, allora $phi(n)|n$, infatti
$n/(phi(n))=prod_{p|n}p/(p-1)=2/1 =2$
quindi $n=2phi(n)$.
Se i fattori primi di $n$ sono solo $2$ e $3$, allora $phi(n)|n$, infatti
$n/(phi(n))=prod_{p|n}p/(p-1)=2/1 3/2 =3$
quindi $n=3phi(n)$.
Viceversa, se $p_1,p_2,...,p_k$ sono i primi della fattorizzazione di $n$ e se $h$ è l'intero tale che $n=h phi(n)$, allora
$h (p_1-1)(p_2-1)...(p_k-1)=p_1p_2...p_k$
Poichè ci può essere al più un numero primo pari, ce ne sono almeno $k-1$ dispari. Quindi $2^{k-1}$ divide il primo membro dell'uguaglianza precedente. Poichè i primi al secondo membro sono tutti distinti, il secondo membro può essere diviso al massimo per $2$. Quindi $k-1=0$ o $k-1=1$ ossia $k=1$ o $k=2$.
Il caso $k=1$:
$h(p_1-1)=p_1$
è valido solo per $p_1=2$
Il caso $k=2$:
$h(p_1-1)(p_2-1)=p_1 p_2$
poichè $2$ divide sicuramente il primo membro, almeno uno tra $p_1$ e $p_2$ è $2$. Supponiamo $p_1=2$. Quindi
$h(p_2-1)=2 p_2$
con $p_2>2$. Poichè $p_2-1$ è primo con $p_2$, necessariamente $p_2-1|2$ da cui $p_2-1=2$ ossia $p_2=3$.