Funzione $varphi$ di Eulero
salve ragazzi sono ormai ore che cerco di dimostrare che $varphi(n)=n\prod_{p|n_{p Primo}}(1-1/p)$ ma non ci sono riuscito...ho cercato un po' su internet ma la dimostrazione che ho trovato mette in mezzo il fatto che $varphi$ sia moltiplicativa ma dato che nel corso di studi non abbiamo affrontato questo argomento non mi sembra opportuno studiare questa dimostrazione...qualcuno ha da fornirmi una dimostrazione che non utilizzi questo? grazie
Risposte
"erdos1123":
salve ragazzi sono ormai ore che cerco di dimostrare che $varphi(n)=n\prod_{p|n_{p Primo}}(1-1/p)$ ma non ci sono riuscito...ho cercato un po' su internet ma la dimostrazione che ho trovato mette in mezzo il fatto che $varphi$ sia moltiplicativa ma dato che nel corso di studi non abbiamo affrontato questo argomento non mi sembra opportuno studiare questa dimostrazione...qualcuno ha da fornirmi una dimostrazione che non utilizzi questo? grazie
Che argomenti hai fatto finora?
allora...numeri complessi, gruppi, anelli, omomorfismi,numeri primi, polinomi, classi di congruenze ($ZZ_n$), permutazioni, prodotti diretti, teorema di Lagrange,Eulero e Fermat quindi i gruppi ciclici...e basta credo
Rimane la strada suggerita dall'Apostol... Il punto focale è dimostrare l'identità [tex]\displaystyle \varphi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d}[/tex]. A questo punto sviluppi [tex]\displaystyle n \prod_{p \mid n} \left(1 - \frac{1}{p} \right)[/tex] e fai vedere che è esattamente il membro destro della precedente uguaglianza. Naturalmente [tex]\mu(\cdot)[/tex] è la funzione di Moebius.
In effetti, questo è l'unico modo consistente che conosco per dimostrare l'identità che riporti. Nel senso che l'unica prova che conosco io per dimostrare la moltiplicatività della [tex]\varphi[/tex] passa appunto attraverso questa identità.
In effetti, questo è l'unico modo consistente che conosco per dimostrare l'identità che riporti. Nel senso che l'unica prova che conosco io per dimostrare la moltiplicatività della [tex]\varphi[/tex] passa appunto attraverso questa identità.
mm ok grazie quindi vedrò cosa riesco a fare utilizzando la funzione di Moebius vi ringrazio
Se hai fatto i gruppi allora saprai che se [tex]m,n[/tex] sono interi positivi coprimi allora [tex]C_n \times C_m \cong C_{nm}[/tex], dove [tex]C_k[/tex] indica il gruppo ciclico di ordine [tex]k[/tex] (cioè [tex]C_k \cong \mathbb{Z}/k\mathbb{Z}[/tex]), per ogni intero positivo [tex]k[/tex]. Saprai inoltre che i generatori di [tex]C_n \times C_m[/tex] sono della forma [tex](g,h)[/tex] dove [tex]g[/tex] è un generatore di [tex]C_n[/tex] e [tex]h[/tex] è un generatore di [tex]C_m[/tex]. Saprai anche che il numero di generatori di [tex]C_k[/tex] è [tex]\varphi(k)[/tex] (in ogni caso, tutte queste cose sono facili da dimostrare). Da questi fatti è ovviamente immediato dedurre che [tex]\varphi[/tex] è moltiplicativa.
grazie dei consigli ragazzi Martino io l'ho provato così:
dato che $m,n$sono coprimi allora $mathbbZ_(mn)\congmathbbZ_mXmathbbZ_n$ e quindi l'insieme degli invertibili di $mathbbZ_(mn)$ ha la stessa cardinalità degli invertibili di $mathbbZ_mXmathbbZZ_n$ e quindi $varphi(mn)=varphi(m)*varphi(n)$ e quindi ho considerato $varphi(n)$ con $ninmathbbZZ$ ora ho utilizzato il teorema fondamentale dell' aritmetica scrivendo n come prodotto di primi elevati a potenze e quindi $varphi(n)=varphi(p_1^(alpha_1)*p_2^(alpha_2)*...*p_n^(alpha_n))$ e quindi poichè sono a due a due coprimi risulta per la dimostrazione precedente $varphi(n)=prod_{i=1}^n varphi(p_i^(alpha_i))$ il problema è ora calcolare $varphi(p^n)$ con p primo...come la posso impostare...so che il risultato deve essere $p^n-p^(n-1)$ ma come lo dimostro?
dato che $m,n$sono coprimi allora $mathbbZ_(mn)\congmathbbZ_mXmathbbZ_n$ e quindi l'insieme degli invertibili di $mathbbZ_(mn)$ ha la stessa cardinalità degli invertibili di $mathbbZ_mXmathbbZZ_n$ e quindi $varphi(mn)=varphi(m)*varphi(n)$ e quindi ho considerato $varphi(n)$ con $ninmathbbZZ$ ora ho utilizzato il teorema fondamentale dell' aritmetica scrivendo n come prodotto di primi elevati a potenze e quindi $varphi(n)=varphi(p_1^(alpha_1)*p_2^(alpha_2)*...*p_n^(alpha_n))$ e quindi poichè sono a due a due coprimi risulta per la dimostrazione precedente $varphi(n)=prod_{i=1}^n varphi(p_i^(alpha_i))$ il problema è ora calcolare $varphi(p^n)$ con p primo...come la posso impostare...so che il risultato deve essere $p^n-p^(n-1)$ ma come lo dimostro?
ragazzi credo di esser riuscito a dimostrarlo anche se è formalizzato malissimo (e in questo vi chiedo una mano) allora io ho pensato così: devo calcolare gli elementi non coprimi con $p^n$ da $0$ a $p^n-1$ allora procedendo per induzione su n si ha che per n=1 $varphi(p)=p-1$ e ci siamo per $n-1$ si avrà:$varphi(p^(n-1))=p^(n-1)-p^(n-2)$ ora devo calcolare $varphi(p^n)$ allora abbiamo che i non coprimi sono $p^n$ meno: i non coprimi fino a $p^(n-1)$ che per ipotesi sono $p^(n-1)-p^(n-2)$
e i non coprimi tra $p^n e p^(n-1)$. ora calcolo questi ultimi so che i numeri compresi tra questi due sono $p^n-p^(n-1)$ e sono del tipo $p^(n-1)+1,p^(n-1)+2,...,p^(n-1)+p,....,p^(n-1)+2*p,....,p^(n-1)+p^2,...,p^(n-1)+p(n-1)=2*p^(n-1),....,p*p^(n-1)=p^n$ ora ho trovato che $p^(n-1)+p$non è coprimo con $p^n$ e quindi fino a $p^(n-1)-p^2$ i non coprimi sono p, fino a $p^(n-1)-p^3$ sono $p^2$ e procedendo così si avrà che fino a $p^n$ saranno $p^n-1$. Quindi avrò che i non coprimi con $p^n$ da $p^(n-1)$a$p^n$ saranno $p^n-p^(n-1)+p^(n-2)-p^(n-1)=p^n-2*p^(n-1)+p^(n-2)$ ora questi sommati a quelli dell'ipotesi induttiva (ovvero quelli relativi a $p^(n-1)$ saranno $p^n-2*p^(n-1)+p^(n-2)+p^(n-1)-p^(n-2)=p^n-p^(n-1)$. Vi chiedo scusa se non si capisce niente. Come idea è giusta??? se si mi aiutereste a formalizzare grazie 1000
e i non coprimi tra $p^n e p^(n-1)$. ora calcolo questi ultimi so che i numeri compresi tra questi due sono $p^n-p^(n-1)$ e sono del tipo $p^(n-1)+1,p^(n-1)+2,...,p^(n-1)+p,....,p^(n-1)+2*p,....,p^(n-1)+p^2,...,p^(n-1)+p(n-1)=2*p^(n-1),....,p*p^(n-1)=p^n$ ora ho trovato che $p^(n-1)+p$non è coprimo con $p^n$ e quindi fino a $p^(n-1)-p^2$ i non coprimi sono p, fino a $p^(n-1)-p^3$ sono $p^2$ e procedendo così si avrà che fino a $p^n$ saranno $p^n-1$. Quindi avrò che i non coprimi con $p^n$ da $p^(n-1)$a$p^n$ saranno $p^n-p^(n-1)+p^(n-2)-p^(n-1)=p^n-2*p^(n-1)+p^(n-2)$ ora questi sommati a quelli dell'ipotesi induttiva (ovvero quelli relativi a $p^(n-1)$ saranno $p^n-2*p^(n-1)+p^(n-2)+p^(n-1)-p^(n-2)=p^n-p^(n-1)$. Vi chiedo scusa se non si capisce niente. Come idea è giusta??? se si mi aiutereste a formalizzare grazie 1000
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo