funzione $varphi$ di Eulero

[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

[vict85]

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?

[erdos1123]

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

[maurer]

Rimane la strada suggerita dall'Apostol... Il punto focale è dimostrare l'identità \( \displaystyle \displaystyle \varphi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d} \) . A questo punto sviluppi \( \displaystyle \displaystyle n \prod_{p \mid n} \left(1 - \frac{1}{p} \right) \) e fai vedere che è esattamente il membro destro della precedente uguaglianza. Naturalmente \( \displaystyle \mu(\cdot) \) è 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 \( \displaystyle \varphi \) passa appunto attraverso questa identità.

[erdos1123]

mm ok grazie quindi vedrò cosa riesco a fare utilizzando la funzione di Moebius vi ringrazio

[Martino]

Se hai fatto i gruppi allora saprai che se \( \displaystyle m,n \) sono interi positivi coprimi allora \( \displaystyle C_n \times C_m \cong C_{nm} \) , dove \( \displaystyle C_k \) indica il gruppo ciclico di ordine \( \displaystyle k \) (cioè \( \displaystyle C_k \cong \mathbb{Z}/k\mathbb{Z} \) ), per ogni intero positivo \( \displaystyle k \) . Saprai inoltre che i generatori di \( \displaystyle C_n \times C_m \) sono della forma \( \displaystyle (g,h) \) dove \( \displaystyle g \) è un generatore di \( \displaystyle C_n \) e \( \displaystyle h \) è un generatore di \( \displaystyle C_m \) . Saprai anche che il numero di generatori di \( \displaystyle C_k \) è \( \displaystyle \varphi(k) \) (in ogni caso, tutte queste cose sono facili da dimostrare). Da questi fatti è ovviamente immediato dedurre che \( \displaystyle \varphi \) è moltiplicativa.

[erdos1123]

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?

[erdos1123]

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