CTX - 05 - Funzione di Eulero

Andiamo adesso a dimostrare che la funzione di Eulero è una funzione moltiplicativa. Infatti, siamo \(n, m\) due naturali tali che \(MCD(n, m) = 1\) e consideriamo la seguente applicazione

\[f: \mathbb{Z}_{nm} \to \mathbb{Z}_n \times \mathbb{Z}_m\]

definita da

\[f(x) := (x \mod n, \,\,\,x \mod m) \quad \forall x \in \mathbb{Z}_{nm}\]

Notiamo che tale applicazione è ben definita, nel senso che ad ogni classe di \(\mathbb{Z}_{nm}\) viene associata una sola classe del codominio. Infatti, \(x \equiv y \mod nm\) se e solo se \(x - y = \alpha nm\). Ma quindi \(x \equiv y \mod n\) e \(x \equiv y \mod m\). Detto altrimenti, abbiamo dimostrato che, cambiando rappresentante della classe del dominio, non cambia la classe del codominio associata. Ovvero \(f\) associa ad ogni classe del dominio una classe del codominio, in modo indipendente dai rappresentati scelti.

Osserviamo ora che \(f\) è surriettiva. Infatti, sia \((a, b)\) un elemento di \(\mathbb{Z}_n \times \mathbb{Z}_m\). Vogliamo trovare un \(x \in \mathbb{Z}_{nm}\) tale che

\[\begin{cases} x \equiv a & (\mod n) \\ x \equiv b & (\mod m) \\ \end{cases}\]

Dato che \(MCD(n, m) = 1\) possiamo utilizzare il TCDR per trovare la soluzione \(x^*\). Tale soluzione è poi unica modulo \(nm\). Mettendo tutto insieme, concludiamo che \(x^*\) è l'unico elemento di \(\mathbb{Z}_{nm}\) tale che \(f(x^*) = (a, b)\). Da questo segue che \(f\) non solo è suriettiva, ma è anche iniettiva, e quindi è biiettiva.

Avendo concluso che \(f\) è biiettiva sappiamo che \(Z_{nm}\) e \(Z_n \times Z_m\) hanno lo stesso numero di elementi. Ma questo equivale a dire che

\[\varphi(nm) = \varphi(n)\varphi(m)\]

il che dimostra che la funzione di Eulero è una funzione moltiplicativa.

Concludiamo osservando che \(f\) è un omomorfismo tra gruppi, e, essendo biiettivo, è in realtà un isomorfismo tra gruppi.

Visto che \(\varphi\) è una funzione moltiplicativa, l'idea è quella di spezzare il calcolo di \(\varphi(n)\) in vari casi:

Andiamo adesso a dimostrare la seguente proprietà della funzione di eulero.

\[\sum_{d \,\,|\,\, n} \varphi(d) = n \,\,\,\, \forall n \in \mathbb{N}\]

Dimostrazione: Ricordiamo che dal lemma dimostrato prima, dato che \(\varphi\) è moltiplicativa, allora anche \(F(n) := \sum_{d | n} \varphi(d)\) è moltiplicatica.

Andiamo a vedere i vari casi, a seconda della fattorizzazione di \(n\):

• Caso \(n = p\) con \(p\) primo, allora banalmente \(F(p) = p\).

• Caso \(n = p^a\) con \(p\) primo, allora \(F(p^a) = \sum_{d | p^a} \varphi(d)\).

  Notiamo in questo caso che gli unici interi che dividono \(p^a\) sono a loro volta potenze di \(p\), ovvero sono numeri della forma \(p^b\) con \(0 \leq b \leq a\). Quindi

  \[\begin{split} F(p^a) = \sum_{d | p^a} \varphi(d) &= \sum_{b = 0}^a \varphi(p^b) \\ &= \varphi(1) + \sum_{b = 1}^a{p^b - p^{b-1}} \\ &= 1 + \Big[(p^a - p^{a-1}) + (p^{a-1} - p^{a-2}) + ... + (p - 1)\Big] \\ &= 1 + \Big[p^a - 1\Big] \\ &= p^a \\ \end{split}\]

• Caso \(n = p_1^{a_1}p_2^{a_2}....p_h^{a_h}\) con \(p_1,...,p_h\) primo.

  \[\begin{split} F(n) &= F(p_1^{a_1}p_2^{a_2}....p_h^{a_h}) \\ &= F(p_1^{a_1})F(p_2^{a_2})...F(p_h^{a_h}) \\ &= p_1^{a_1}p_2^{a_2}...p_h^{a_h} \\ &= n \end{split}\]

Procediamo per casi.

Andiamo adesso a dimostrare un interessante corollario.

Corollario: Siano \(a, m\) due numeri naturali tali che \(MCD(a, m) = 1\). Allora

\[n' \equiv n \mod{\varphi(n)} \implies a^{n'} \equiv a^n \mod n\]

Dimostrazione: Infatti, se \(n \equiv n' \mod{\varphi(n)}\), allora \(\exists \,\, q \in Z\) tale che \(n = n' + q\varphi(n)\). Ma allora otteniamo

\[\begin{split} a^n &\equiv a^{n' + q\varphi(n)} \mod n \\ &\equiv a^{n'}(a^{\varphi(n)})^q \mod n \\ &\equiv a^{n'}(1)^q \mod n \\ &\equiv a^{n'} \mod n \\ \end{split}\]

\[\tag*{$\blacksquare$}\]

Come avevamo menzionato per il piccolo teorema di Fermat, notiamo che il teorema di Eulero non ci calcola l'ordine degli elementi di un gruppo, ed è quindi un risultato piuttosto rozzo se visto negli interessi della teoria dei gruppi.