Moltiplicatività di $phi(n)$
Ragazzi qualcuno conosce una dimostrazione del fatto che la funzione di Eulero $phi(n)$ sia moltiplicativa?
Risposte
La moltiplicatività della funzione di eulero può essere provata tenendo conto della relazione
${phi(n)}/n=\prod_{p|n}(1-1/p)$,
infatti, per $m,n$ coprimi, è
${phi(mn)}/n=\prod_{p|mn}(1-1/p)=\prod_{p|m}(1-1/p)\prod_{p|n}(1-1/p)={phi(m)}/m{phi(n)}/n$.
${phi(n)}/n=\prod_{p|n}(1-1/p)$,
infatti, per $m,n$ coprimi, è
${phi(mn)}/n=\prod_{p|mn}(1-1/p)=\prod_{p|m}(1-1/p)\prod_{p|n}(1-1/p)={phi(m)}/m{phi(n)}/n$.
Grazie! Però io so che a quella relazione si arriva sfruttando la moltiplicatività della funzione.
Dato un numero primo $p^k$, il numero dei coprimi minori di $p^k$ è $p^k-p^(k-1)=p^k-p^k/p=p^k(1-1/p)$; ora, poichè $phi(n)$ è moltiplicativa se $n=p_(1)^(alpha_(1))*p_(2)^(alpha_(2))*...*p_(k)^(alpha_(k))$ si vede benissimo che $phi(n)=nprod_(p|n)(1-1/p)$.
Quindi in sostanza abbiamo dato per scontata la moltiplicatività della funzione per arrivare a quella relazione e poi utilizziamo quest'ultima per vedere che $phi(n)$ è moltiplicativa.
Dato un numero primo $p^k$, il numero dei coprimi minori di $p^k$ è $p^k-p^(k-1)=p^k-p^k/p=p^k(1-1/p)$; ora, poichè $phi(n)$ è moltiplicativa se $n=p_(1)^(alpha_(1))*p_(2)^(alpha_(2))*...*p_(k)^(alpha_(k))$ si vede benissimo che $phi(n)=nprod_(p|n)(1-1/p)$.
Quindi in sostanza abbiamo dato per scontata la moltiplicatività della funzione per arrivare a quella relazione e poi utilizziamo quest'ultima per vedere che $phi(n)$ è moltiplicativa.
Puoi, provare la validità della relazione
$phi(n)=n\prod_{p|n}(1-1/p)$
utilizzando la funzione di Moebius. In particolare si osserva che
$phi(n)=n\prod_{p|n}(1-1/p)=\sum_{d|n}mu(d)/d$
e che
$\sum_{d|n}mu(d)/d=\phi(n)$.
Comunque, ho trovato un'altra dimostrazione della proprietà di moltiplicatività della funzione di eulero:
Dati $m,n$ corpimi, sia ${r_1, r_2, \ldots, r_j}$ (con $j=phi(m)$) un sistema ridotto di residui modulo $m$ e sia ${s_1, s_2, \ldots, s_k}$ (con $k=phi(n)$) un sistema ridotto di residui modulo $n$.
Sia $x$ un elemento di un sistema ridotto di residui modulo $mn$. Poichè $(x,mn)=1$ e $(m,n)=1$ è anche $(x,m)=(x,n)=1$, quindi per la definizione di sistema ridotto, esistono $r_i, s_h$ tali che
$x\equiv r_i (mod m)$
$x\equiv s_i (mod n)$
Quindi $x$ determina univocamente una coppia $(r_i,s_h)$. Viceversa, per il teorema cinese del resto la coppia $(r_i,s_j)$ determina un solo $x$ modulo $mn$. Vi è quindi una corrispondeza biunivoca tra il sistema ridotto di residui modulo $mn$ e le coppie $(r_i,s_j)$.
Con il linguaggio dell'algebra, ciò equivale a provare che $ZZ_{mn}$ e $ZZ_m oplus ZZ_n$ sono isomorfi.
$phi(n)=n\prod_{p|n}(1-1/p)$
utilizzando la funzione di Moebius. In particolare si osserva che
$phi(n)=n\prod_{p|n}(1-1/p)=\sum_{d|n}mu(d)/d$
e che
$\sum_{d|n}mu(d)/d=\phi(n)$.
Comunque, ho trovato un'altra dimostrazione della proprietà di moltiplicatività della funzione di eulero:
Dati $m,n$ corpimi, sia ${r_1, r_2, \ldots, r_j}$ (con $j=phi(m)$) un sistema ridotto di residui modulo $m$ e sia ${s_1, s_2, \ldots, s_k}$ (con $k=phi(n)$) un sistema ridotto di residui modulo $n$.
Sia $x$ un elemento di un sistema ridotto di residui modulo $mn$. Poichè $(x,mn)=1$ e $(m,n)=1$ è anche $(x,m)=(x,n)=1$, quindi per la definizione di sistema ridotto, esistono $r_i, s_h$ tali che
$x\equiv r_i (mod m)$
$x\equiv s_i (mod n)$
Quindi $x$ determina univocamente una coppia $(r_i,s_h)$. Viceversa, per il teorema cinese del resto la coppia $(r_i,s_j)$ determina un solo $x$ modulo $mn$. Vi è quindi una corrispondeza biunivoca tra il sistema ridotto di residui modulo $mn$ e le coppie $(r_i,s_j)$.
Con il linguaggio dell'algebra, ciò equivale a provare che $ZZ_{mn}$ e $ZZ_m oplus ZZ_n$ sono isomorfi.
Avevo quasi dimenticato questo topic...
Era quello che cercavo...grazie!
"ficus2002":
Comunque, ho trovato un'altra dimostrazione della proprietà di moltiplicatività della funzione di eulero:
Dati $m,n$ corpimi, sia ${r_1, r_2, \ldots, r_j}$ (con $j=phi(m)$) un sistema ridotto di residui modulo $m$ e sia ${s_1, s_2, \ldots, s_k}$ (con $k=phi(n)$) un sistema ridotto di residui modulo $n$.
Sia $x$ un elemento di un sistema ridotto di residui modulo $mn$. Poichè $(x,mn)=1$ e $(m,n)=1$ è anche $(x,m)=(x,n)=1$, quindi per la definizione di sistema ridotto, esistono $r_i, s_h$ tali che
$x\equiv r_i (mod m)$
$x\equiv s_i (mod n)$
Quindi $x$ determina univocamente una coppia $(r_i,s_h)$. Viceversa, per il teorema cinese del resto la coppia $(r_i,s_j)$ determina un solo $x$ modulo $mn$. Vi è quindi una corrispondeza biunivoca tra il sistema ridotto di residui modulo $mn$ e le coppie $(r_i,s_j)$.
Con il linguaggio dell'algebra, ciò equivale a provare che $ZZ_{mn}$ e $ZZ_m oplus ZZ_n$ sono isomorfi.
Era quello che cercavo...grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo