Problema sulla funzione di eulero dei divisori di n

[Leonardo891]

Ciao a tutti
Mi piacerebbe sapere se ho risolto correttamente questo problema.
Metto la soluzione in spoiler così chi vuole può provare a risolverlo da solo.

Sia $n \in NN: n>=1 $. Allora si ha $ n = \sum_{d|n} \phi (d) $ dove $ \phi $ è la funzione di Eulero e dove con $ d| n $ intendo "d divide n".

Se n=1, allora $ \sum_{d|1} \phi (d)= \phi(1) = 1 $
Assumo ora $n = p^r $ con p primo ed $ r>=1 $.
I divisori di d sono tutti gli interi $ p^i $, con $i=0,...,r$, quindi

$\sum_{d|n} \phi (d) = \sum_{i=0}^r \phi (p^i)= \phi(1) + \sum_{i=1} \phi(p^i) = 1 + \sum_{i=1}^r p^{i-1} (p-1) = $
$=1 + (p-1) \sum_{i=0}^{r-1} p^i = 1+ (p-1) \frac{1-p^r}{1-p}= 1 + p^r -1 =^r =n $

Ora procedo per induzione sul numero $ s>=2 $ di primi distinti che compaiono nella fattorizzazione di n.
Sia $ n = p_1^{r_1} p_2^{r_2} ...p_s^{r_s} $
Pongo $ N := p_1^{r_1} $ e $ M:= p_2^{r_2} ...p_s^{r_s} $
Sia ora $d | n $ con $ d>1 $
Poiché $ n=N M $ si hanno le possibilità
4) $ (d | N ) ^^^ ( d | M ) $
1) $ (d | N ) ^^^ \neg ( d | M ) $
2) $ \neg (d | N ) ^^^ ( d | M ) $
3) $ \neg (d | N ) ^^^ \neg ( d | M ) $
Si vede subito che la 4) non è possibile perché MCD(N,M)=1
Pongo allora
$ DIV_1 = {(d | N ) ^^^ \neg ( d | M )} uuu {1} $
$ DIV_2 = {\neg (d | N ) ^^^ ( d | M ) } uuu {1} $
$ DIV_3 = { \neg (d | N ) ^^^ \neg ( d | M )} $
Poi $ AA i= 1,..., r_1 $ pongo
$ DIV_{3,i} = { p_1^{i} \alpha , \alpha \in DIV_2-\{1}} $
Quindi si ha $ DIV_3 = uuu_{i=1}^{r_1} DIV_{3,i} $
Allora, assumendo la tesi dimostrata per N e M grazie all'ipotesi di induzione forte, ho
$ \sum_{d|n} \phi (d)= \sum_{d \in DIV_1} \phi(d) + \sum_{d \in DIV_2} \phi(d) + ( \sum_{d \in DIV_3} \phi(d) ) -1 =N + M + ( \sum_{i=1}^{r_1} \sum_{d \in DIV_{3,i}} \phi(d) ) -1 = $
$ = N + M + ( \sum_{i=1}^{r_1} \sum_{d \in DIV_{2}-{1}} \phi(p_1^{r_1}) \phi(d) ) -1 = N + M + ( \sum_{i=1}^{r_1}\phi(p_1^{r_1}))( \sum_{d \in DIV_{2}-{1}} \phi(d) ) -1 = $
$ = N + M -1 + ((\sum_{d \in DIV_1} \phi(d))-1)(( \sum_{d \in DIV_{2}} \phi(d) )-1 ) = N + M -1 + (N-1)(M-1) = NM = n$
C.d.d.

Ciao e grazie,
Leonardo

P.S. So che la domanda ha poco senso perché è tutto relativo, ma secondo voi qual è il livello di difficoltà di questo problema?
Il mio prof di algebra assengnandolo ha detto che era molto difficile ed, in effetti, mi ha fatto sudare parecchio!

[Studente Anonimo]

Ora è un po' tardi, mi limito ad un'osservazione.

"Leonardo89":secondo voi qual è il livello di difficoltà di questo problema?

Di sicuro affrontarlo di petto porta a molti calcoli, ma se lo vedi dal punto di vista della teoria dei gruppi la dimostrazione è squisitamente elementare! (sic)

Considera $C_n$, il gruppo ciclico di ordine $n$, e chiama $g$ un generatore. E' ben noto che $C_n$ ha $phi(n)$ generatori (le potenze di $g$ con esponente coprimo con $n$).

Più in generale, se $d$ divide $n$ allora $C_n$ contiene esattamente $phi(d)$ elementi di ordine $d$ (sono i generatori del sottogruppo generato da $g^{n/d}$).

Chiama $O(d)$ l'insieme degli elementi di $C_n$ di ordine $d$. E' chiaro che (*) $sum_{d|n}|O(d)|=|C_n|$, no? E' ovvio, la famiglia degli $O(d)$ forma una partizione di $C_n$ (ogni elemento ha un ordine).

Ma ricorda che $|O(d)|=phi(d)$ e $|C_n|=n$. Quindi (*) cosa diventa?

[Leonardo891]

Prima di tutto ti ringranzio della risposta.

"Martino":Di sicuro affrontarlo di petto porta a molti calcoli, ma se lo vedi dal punto di vista della teoria dei gruppi la dimostrazione è squisitamente elementare! (sic)

Veramente interessante, peccato che quando il prof l'ho proposto ancora non studiavamo la teoria dei gruppi ed anche io ancora non ci arrivo a studiarla.
Tranquillo, quindi, che appena la studierò (tra pochissimo ) riaffronterò il problema da quest'altro punto di vista.
Mi piacerebbe comunque sapere se non ho scritto troppe scemenze.

[Leonardo891]

Grazie 1000 Martino, dopo aver studiato un po' di teoria dei gruppi comprendo la tua risposta e la tua dimostrazione è veramente semplice e pulita. Ho trovato perfino un'altra dimostrazione quasi identica alla tua nel capitolo sui gruppi ciclici del mio libro di algebra.
Ora però mi chiedo: cosa si aspettava il prof? Che mi inventassi la teoria dei gruppi ciclici?
Oppure voleva semplicemente che ci rendessimo conto di quanto erano complicati i conti e che, applicando la teoria dei gruppi, si poteva avere una dimostrazione molto più lineare?

[Studente Anonimo]

"Leonardo89":Oppure voleva semplicemente che ci rendessimo conto di quanto erano complicati i conti e che, applicando la teoria dei gruppi, si poteva avere una dimostrazione molto più lineare?

Questo credo.

[vict85]

"Leonardo89":Grazie 1000 Martino, dopo aver studiato un po' di teoria dei gruppi comprendo la tua risposta e la tua dimostrazione è veramente semplice e pulita. Ho trovato perfino un'altra dimostrazione quasi identica alla tua nel capitolo sui gruppi ciclici del mio libro di algebra.
Ora però mi chiedo: cosa si aspettava il prof? Che mi inventassi la teoria dei gruppi ciclici?
Oppure voleva semplicemente che ci rendessimo conto di quanto erano complicati i conti e che, applicando la teoria dei gruppi, si poteva avere una dimostrazione molto più lineare?

Quella di Martino è una dimostrazione molto standard...

[Studente Anonimo]

Comunque si può affrontare il problema anche senza la teoria dei gruppi.

L'idea è partizionare ${1,...,n}$ nei sottoinsiemi ${t in {1,...,n}:\ (t,n)=d}$ dove $d$ varia tra i divisori di $n$ e $(a,b)$ indica il MCD tra $a$ e $b$. Si ottiene:

$n = |{1,...,n}| = | \bigcup_{d|n} {t in {1,...,n}:\ (t,n)=d}| = sum_{d|n} |{t in {1,...,n}:\ (t,n)=d}| =$
$= sum_{d|n} |{t in {1,...,n}:\ d|t,\ (t/d,n/d)=1}| = sum_{d|n} |{s in {1,...,n/d}:\ (s,n/d)=1}| = sum_{d|n} phi(n/d) = sum_{d|n} phi(d)$.

[Leonardo891]

Bella!
Che testone che sono che non ho pensato alla cardinalità!