Passa al tema normale
Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

forse è semplice ma mi sfugge...

20/03/2006, 21:15

è vero che $\phi$(6n) divide 6n per ogni intero n? dove $\phi$ è la solita funzione di Euler.

Ciao, ubermensch

20/03/2006, 21:26

no, per esempio $phi(6 cdot 5)=8$.

20/03/2006, 21:31

esatto!! lo stavo per scrivere io! mi accorgo che ho scritto una c****ata sempre dopo che l'ho scritta... vabbè..

ciao

20/03/2006, 21:50

A proposito, ma li sappiamo caratterizzare tutti gli h tali che $\phi$(h) divide h?

20/03/2006, 22:21

si, $phi(n)$ divide $n$ se e solo se $n$ è della forma $2^{alpha}$ o $2^{alpha} \cdot 3^{beta}$ (con $alpha, beta>0$), e si ha rispettivamente $n=2phi(n)$ e $n=3phi(n)$.
Ultima modifica di ficus2002 il 21/03/2006, 00:27, modificato 1 volta in totale.

20/03/2006, 23:34

o santissimo iddio!! ma sei sicuro? please, a proof!

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$.

21/03/2006, 23:27

grazie mille!

ciao, ubermensch
Rispondi al messaggio