Dimostrazione funzione di Eulero $\phi(n)$
La funzione di Eulero restituisce il numero di interi minori e coprimi con [tex]n[/tex] , ed esprime la cardinalità degli elementi invertivili di [tex]Z_n[/tex].
Sia [tex]p[/tex] un numero primo e siano [tex]a,b \in Z[/tex] coprimi, cioè [tex](a,b)=1[/tex]; allora si ha:
1) [tex]\phi(p^r) = p^r^-^1(p-1)[/tex]
2) [tex]\phi(ab) = \phi(a) * \phi(b)[/tex]
Dimostrazione di 1):
Siccome [tex]p[/tex] è un numero primo allora gli interi che non sono primi con [tex]p[/tex] sono i [tex]p^r^-^1[/tex], cioè i multipli di [tex]p[/tex]:
[tex]p,2p,3p, ... , p^r^-^1p = p^r[/tex]
quindi basta sottrarre [tex]p^r^-^1[/tex] a [tex]p^r[/tex] e si ottiene [tex]\phi(p^r) = p^r - p^r^-^1 = p^r^-^1(p-1)[/tex]
Dimostrazione di 2):
Sia [tex]ab \in Z[/tex] e sia [tex]S[/tex] un sistema completo di residui modulo [tex]ab[/tex]. Ogni elemento [tex]s \in S[/tex] può essere espresso come:
[tex]s = qb + r[/tex] con [tex]0 \leq r < b[/tex] e [tex]0 \leq q < a[/tex]
si vengono così a formare delle coppie di interi [tex](qb+r,b)[/tex] che sono coprimi se e solo se [tex](b,r)=1[/tex]
Per definizione di [tex]\phi(b)[/tex] sappiamo che esistono [tex]r \in Z[/tex] tali che [tex](b,r)=1[/tex], che sono esattamente i resti delle divisioni di [tex]s[/tex] per [tex]b[/tex],
e per ognuno di essi possiamo formare un insieme D, un sistema completo di residui modulo [tex]b[/tex] così definito:
[tex]D=\{ r, r+b, r+2b, r+ 3b, ..., r+ (a-1)b \}[/tex]
Tra gli elementi [tex]d \in D[/tex] ve ne sono alcuni coprimi con [tex]a[/tex] e quindi anche con [tex]ab[/tex]. Segue che si possono identificare [tex]\phi(a) * \phi(b)[/tex] interi
minori e coprimi con [tex]ab[/tex]:
[tex]J=\{ d \in D | (d,ab)=1 \}[/tex]
da cui [tex]\phi(ab) = \phi(a) \phi(b)[/tex]
Che ne dite, può andare??
Sia [tex]p[/tex] un numero primo e siano [tex]a,b \in Z[/tex] coprimi, cioè [tex](a,b)=1[/tex]; allora si ha:
1) [tex]\phi(p^r) = p^r^-^1(p-1)[/tex]
2) [tex]\phi(ab) = \phi(a) * \phi(b)[/tex]
Dimostrazione di 1):
Siccome [tex]p[/tex] è un numero primo allora gli interi che non sono primi con [tex]p[/tex] sono i [tex]p^r^-^1[/tex], cioè i multipli di [tex]p[/tex]:
[tex]p,2p,3p, ... , p^r^-^1p = p^r[/tex]
quindi basta sottrarre [tex]p^r^-^1[/tex] a [tex]p^r[/tex] e si ottiene [tex]\phi(p^r) = p^r - p^r^-^1 = p^r^-^1(p-1)[/tex]
Dimostrazione di 2):
Sia [tex]ab \in Z[/tex] e sia [tex]S[/tex] un sistema completo di residui modulo [tex]ab[/tex]. Ogni elemento [tex]s \in S[/tex] può essere espresso come:
[tex]s = qb + r[/tex] con [tex]0 \leq r < b[/tex] e [tex]0 \leq q < a[/tex]
si vengono così a formare delle coppie di interi [tex](qb+r,b)[/tex] che sono coprimi se e solo se [tex](b,r)=1[/tex]
Per definizione di [tex]\phi(b)[/tex] sappiamo che esistono [tex]r \in Z[/tex] tali che [tex](b,r)=1[/tex], che sono esattamente i resti delle divisioni di [tex]s[/tex] per [tex]b[/tex],
e per ognuno di essi possiamo formare un insieme D, un sistema completo di residui modulo [tex]b[/tex] così definito:
[tex]D=\{ r, r+b, r+2b, r+ 3b, ..., r+ (a-1)b \}[/tex]
Tra gli elementi [tex]d \in D[/tex] ve ne sono alcuni coprimi con [tex]a[/tex] e quindi anche con [tex]ab[/tex]. Segue che si possono identificare [tex]\phi(a) * \phi(b)[/tex] interi
minori e coprimi con [tex]ab[/tex]:
[tex]J=\{ d \in D | (d,ab)=1 \}[/tex]
da cui [tex]\phi(ab) = \phi(a) \phi(b)[/tex]
Che ne dite, può andare??
Risposte
Up!
Vorrei solo sapere se ho scritto delle fesserie....
Vorrei solo sapere se ho scritto delle fesserie....
Il primo è ok.
Per il secondo, mi pare che ti complichi la vita. Guarda come agisce Martino qui. A quel punto, ricorda che il numero di generatori di [tex]\mathbb Z_n[/tex] è [tex]\varphi(n)[/tex], quello di [tex]\mathbb Z_m[/tex] è [tex]\varphi(m)[/tex], osserva che i generatori di [tex]\mathbb Z_n \times \mathbb Z_m[/tex] sono della forma [tex](a,b)[/tex] dove [tex]a[/tex] genera [tex]\mathbb Z_n[/tex] e [tex]b[/tex] genera [tex]\mathbb Z_m[/tex] per concludere che [tex]\mathbb Z_n \times \mathbb Z_m[/tex] ha [tex]\varphi(n) \varphi(m)[/tex] generatori. D'altra parte, come dimostra Martino in quel post, [tex]\mathbb Z_n \times \mathbb Z_m \simeq \mathbb Z_{nm}[/tex] e quindi [tex]\varphi(nm) = \varphi(n) \varphi(m)[/tex].
Per il secondo, mi pare che ti complichi la vita. Guarda come agisce Martino qui. A quel punto, ricorda che il numero di generatori di [tex]\mathbb Z_n[/tex] è [tex]\varphi(n)[/tex], quello di [tex]\mathbb Z_m[/tex] è [tex]\varphi(m)[/tex], osserva che i generatori di [tex]\mathbb Z_n \times \mathbb Z_m[/tex] sono della forma [tex](a,b)[/tex] dove [tex]a[/tex] genera [tex]\mathbb Z_n[/tex] e [tex]b[/tex] genera [tex]\mathbb Z_m[/tex] per concludere che [tex]\mathbb Z_n \times \mathbb Z_m[/tex] ha [tex]\varphi(n) \varphi(m)[/tex] generatori. D'altra parte, come dimostra Martino in quel post, [tex]\mathbb Z_n \times \mathbb Z_m \simeq \mathbb Z_{nm}[/tex] e quindi [tex]\varphi(nm) = \varphi(n) \varphi(m)[/tex].
Intanto grazie per la risposta 
Ora vedo la risposta di Martino e poi cerco di capire cosa sono i gruppi ciclici, non avendoli ancora studiati.
Ora vedo la risposta di Martino e poi cerco di capire cosa sono i gruppi ciclici, non avendoli ancora studiati.
No no, allora lascia stare. Pensavo che avessi già fatto i gruppi, tutto qua. E' che quella è la dimostrazione più rapida che conosco.
Ne avevamo parlato anche qui. La prova a cui pensavo fa uso solo di strumenti elementari (niente di più dell'induzione se non ricordo male).
Ne avevamo parlato anche qui. La prova a cui pensavo fa uso solo di strumenti elementari (niente di più dell'induzione se non ricordo male).
Relativamente ai gruppi ho solo un'infarinatura (concetto di base), e quella discussione devo dire di averla letta, ma al momento non mi sembra di avere gli strumenti per capirla.
Comunque se la mia dimostrazione, anche se complicata, è corretta allora la tengo buona, poi non appena se saprò un pò di più vedo di ristudiarla
Comunque se la mia dimostrazione, anche se complicata, è corretta allora la tengo buona, poi non appena se saprò un pò di più vedo di ristudiarla
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo