OliForum Matematico

Probabilmente è un fatto stranoto, ma lo posto lo stesso perché l'ho trovato carino...
Dimostrare che per ogni $n>0$ vale $\sum\limits_{d|n}\varphi(d)=n$

definisci
$ \varphi(n) $

Credo che intenda dire la funzione φ di Eulero. A questo punto sarebbe carino chiedere anche una formula per la somma di tutti i divisori di un numero.

$\sum\limits_{d|n}$

Significa che si devono prendere solo i d che dividono n?

Se d è primo, allora per ogni h>1 risulta $ \varphi(d^{h})=d^{h}-d^{h-1} $ se non sbaglio.

exodd ha scritto:definisci
$ \varphi(n) $

Perché? Può voler dire qualcos'altro?

Drago96 ha scritto:

$\sum\limits_{d|n}$

Significa che si devono prendere solo i d che dividono n?

Esatto

LeZ ha scritto:Se d è primo, allora per ogni h>1 risulta $ \varphi(d^{h})=d^{h}-d^{h-1} $ se non sbaglio.

Fin qui ok, ti rimangono i divisori composti!
P.S.: per il simbolo $\ge$ puoi usare \ge o \geq: è un po' più elegante...

Sì, scusa, è che lo vedo sempre scritto in un altro modo
Comunque è abbastanza facile, quindi sotto gente

Per i divisori composti, basta che applico questa regola ad ogni primo che lo compone
Comunque grazie per l'aiuto nel LateX devo ancora specializzarmi

LeZ ha scritto:Per i divisori composti, basta che applico questa regola ad ogni primo che lo compone
Comunque grazie per l'aiuto nel LateX devo ancora specializzarmi

Sì, ma.. Lo dovresti dimostrare

Gli unici numeri che non sono primi con $ d^{h} $ sono i multipli di d, possiamo quindi scriverli nella forma $ d\dot k $ con $ 1\le k \le d^{h-1} $, e quindi in totale sono $ d^{h-1} $

Bene, ora prova a dimostrare che $\varphi$ è moltiplicativa, ovvero che se $a$ e $b$ sono coprimi allora $\varphi (ab) = \varphi (a)\varphi (b)$...

Hint per una delle possibili dimostrazioni:

Beh intanto l'MCD $ (a,b)=1 $. Sia il prodotto $ k =a\dot b $ esistono quindi alcuni numeri $ 0\le h <k $ nella forma $ (h \mod a, h\mod b) $, avendo MCD $ (h,ab)=1 $ se e solo se MCD $ (h\mod a,a)=1 $ e MCD$ (h\mod b,b)= $1; da cui il totale $ \varphi (ab) $ degli $ h\mod ab $ è quindi $ \varphi (a)\varphi (b) $. La funzione di Eulero è moltiplicativa.