Teorema di Eulero

# Teorema di Eulero ###### tags: `md` ###### Definizione Un gruppo $G$ è un insieme non vuoto dotato di una operazione che ad ogni coppia di elementi $a, b \in G$ associa un elemento di $G$ indicato con $a \cdot b$ e ha le seguenti proprietà: * dati $a,b,c \in G$ vale $a \cdot (b \cdot c) = (a \cdot b) \cdot c$ (proprietà associativa); * esiste un elemento $e \in G$ tale che $a \cdot e = e \cdot a = a$ per ogni $a \in G$ (esistenza dell'elemento neutro / identità in $G$); * per ogni $a \in G$ esiste un elemento $a^{-1} \in G$ tale che $a \cdot a^{-1} = a^{-1} \cdot a = e$ (esistenza dell'inverso in $G$). Un gruppo di dice commutativo o abeliano se, per ogni $a, b \in G$ vale $a \cdot b = b \cdot a$. Un gruppo $G$ si dice finito se l'insieme $G$ ha cardinalità finita. ###### Teorema Dimostrare che, se $G$ è un gruppo, allora * C'è un solo elemento neutro $e$. * Per ogni $a \in G$ c'è un unico inverso di $a$. * Per ogni $a \in G$ vale $(a^{-1})^{-1} = a$. * Per ogni $a, b \in G$ vale $(ab)^{-1} = b^{-1}a^{-1}$. * Siano $a, b, c$ elementi di $G$. Allora l'equazione $axb = c$ ha un'unica soluzione $x = a^{-1}cb^{-1}$ in $G$. ###### Dimostrazione Supponiamo di avere due elementi neutri $e$ ed $e'$. Allora possiamo scrivere, che $e = ee' = e'$ dove per il primo $=$ abbiamo sfruttato la proprietà di elemento neutro di $e'$, e per il secondo la proprietà di elemento neutro di $e$. Siano $h$ e $k$ due inversi di $a$. Allora $$ h = he = h(ak) = (ha)k = ek = k $$ Osserviamo che $(g^{-1})^{-1}g^{-1} = g^{-1}(g^{-1})^{-1} = e$ per definizione di $(g^{-1})^{-1}$. Ma sappiamo anche che $gg^{-1} = g^{-1}g = e$ per definizione di $g^{-1}$. Dunque osserviamo che sia $g$ sia $(g^{-1})^{-1}$ sono inversi di $g^{-1}$. Per l'unicità dell'inverso stabilita nel punto 2 possiamo concludere che $g = (g^{-1})^{-1}$. Basta verificare che $b^{-1}a^{-1}$ è un inverso di $ab$. Lo faremo moltiplicando a sinistra $$ (b^{-1}a^{-1})(ab) = b^{-1}(a^{-1}(ab)) = b^{-1}((a^{-1}a)b) = b^{-1}(eb) = b^{-1}b = e $$ dove abbiamo usato in maniera sostanziale la proprietà associativa. Un elemento $\bar{x}$ soddisfa l'equazione $axb=c$ se e solo se vale $a\bar{x}b = c$. Questa uguaglianza è vera se e solo se è vera $\bar{x}b = a^{-1}c$, come si vede moltiplicando a sinistra entrambi i membri per $a^{-1}$. Moltiplicando a destra per $b^{-1}$ si vede che questa uguaglianza a sua volta è vera se e solo se è vera $\bar{x} = a^{-1}cb^{-1}$. Dunque le soluzioni dell'equazione $axb = c$ coincidono con le soluzioni dell'equazione $x = a^{-1}cb^{-1}$, che sono una sola, ossia $a^{-1}cb^{-1}$. ###### Definizione Un sottogruppo $H$ di un gruppo $G$ è un sottoinsieme di $G$ che soddisfa le tre seguenti proprietà: * $e \in H$ * $a, b \in H \Rightarrow ab \in H$ * $a \in H \Rightarrow a^{-1} \in H$ Per indicare che $H$ è un sottogruppo di $G$ si scrive $H < G$. ###### Osservazione Tra i sottogruppi di un gruppo $G$ ci sono sempre $G$ stesso e il sottogruppo banale $\{e\}$. ###### Definizione ###### Centro di un gruppo Dato un gruppo $G$ si chiama centro di $G$ il sottoinsieme formato dagli elementi che commutano con tutti gli elementi del gruppo: $$ Z(G) = \{g \in G \ | \ gh = hg \quad \forall h \in G \} $$ ###### Definizione Se, per qualche $a \in G$ vale $G = (a)$ allora si dice che $G$ è un gruppo ciclico. ###### Definizione Sia $G$ un gruppo, $H$ un sottogruppo di $G$. Chiameremo $H$-laterale destro, o laterale destro di $H$, o classe laterale destra di $H$, un sottoinsieme di $G$ del tipo: $$ gH = \{gh \ | \ h \in H \} $$ dove $g \in G$. L'insieme i cui elementi sono gli $H$-laterali destri si indica con $G/H$ e la sua cardinalità $|G/H|$ si chiama indice di $H$ in $G$. ###### Teorema ###### Teorema di Lagrange Se $G$ è un gruppo finito e $H$ è un sottogruppo di $G$, allora $|H|$ divide $|G|$. ###### Dimostrazione Visto che $G$ è finito, $G$ è l'unione disgiunta di un numero finito, diciamo $n_H$, di laterali destri di $H$. Se dimostriamo che ogni laterale ha cardinalità esattamente $|H|$ allora risulta $|G| = n_H |H|$ e dunque$|H|$ divide $|G|$. ###### Definizione Dato un elemento $x$ di un gruppo $G$, se esiste un minimo intero positivo $n$ tale che $x^n=e$ allora $n$ si indica con $o(x)$ e si chiama ordine di $x$. Se un tale $n$ non esiste allora si dice che $x$ ha ordine infinito e si scrive con $o(x) = +\infin$. ###### Corollario In un gruppo finito $G$, ogni elemento $x$ ha ordine finito e tale ordine $o(x)$ divide $|G|$. ###### Corollario Se $x$ è un elemento di un grupo finito $G$ vale $$ x^{|G|}=e $$ #### La funzione di Eulero e il Teorema di Eulero Il Teorema di Lagrange e il Corollario (ordine divide $G$) hanno un'immediata applicazione. Fissato un numero positivo $m$, consideriamo l'anello $\mathbb{Z}_m$. È immediato verificare che gli elementi invertibili di $\mathbb{Z}_m$ costituiscono un gruppo rispetto alla moltiplicazione. Tale gruppo viene indicato con la notazione $\mathbb{Z}_m^*$. ###### Definizione La funzione $\phi$ di Eulero è la funzione $\phi \ : \ \mathbb{N}^{>0} \rightarrow \mathbb{N}^{>0}$ definita ponendo $\phi(1) 0= 1$ e, per $n > 1$, $$ \phi(n) = \text{numero degli interi positivi minori di }n\text{ e primi con }n $$ Dunque la cardinalità di $\mathbb{Z}_m^*$ è uguale a $\phi(m)$. ###### Teorema Fissato un intero positivo $m$, se $a$ è un intero primo con $m$ vale: $$ a^{\phi(m)} \equiv 1 \ mod \ m $$ ###### Dimostrazione Visto che $a$ ed $m$ sono coprimi, sappiamo che $[a]$ appartiene a $\mathbb{Z}_m^*$. Per il Corollario (ultimo cap precedente) vale $$ [a]^{\phi(m)} = [1] $$ che equivale a $$ a^{\phi(m)} \equiv 1 \ mod \ m $$ ###### Osservazione Se $m=p$ è primo ritroviamo l'enunciato del piccolo teorema di Fermat, visto che $\phi(p) = p-1$. In questo caso vale anche che $\mathbb{Z}_p^*$ è un gruppo ciclico, ossia esiste un elemento in $\mathbb{Z}_p^*$ di ordine esattamente $p-1$. ###### Proposizione Se $b$ e $c$ sono due numeri primi tra loro $$ \phi(bc) = \phi(b)\phi(c) $$ ###### Dimostrazione Facciamo un'osservazione: dati tre numeri interi $s,t,m$ con $m > 0$, tali che $s \equiv t \quad (m)$, allora $s$ è coprimo con $m$ se e solo se $t$ è coprimo con $m$. Infatti $s \equiv t \quad (m)$ può essere tradotto nella relazione $s = mq + t$ per un certo intero $q$, e sappiamo che $MCD(s, m) = MCD(m, t)$. Ora se $u$ è un numero intero positivo corpimo con $bc$ e minore di $bc$, allora $u$ è coprimo con $b$ e coprimo con $c$, ed è dunque soluzione di un sistema di equazioni del tipo $$ \begin{cases} x \equiv k \quad (b) \\ x \equiv v \quad (c) \end{cases} $$ dove $k$ è un intero positivo coprimo con $b$ e $<b$ e $v$ è un intero positivo coprimo con $c$ e $<c$. Per il teorema cinese, ogni sistema di equazioni del tipo descritto ha una sola soluzione intera positiva e $< bc$, e tale soluzione è anche coprima con $bc$. I numeri interi positivi coprimi con $bc$ e minori di $bc$ sono tanti quanti i sistemi del tipo descritto, che sono $\phi(b)\phi(c)$ (il prodotto delle possibili scelte di $k$ e $v$). ###### Teorema Consideriamo un intero positivo $m$. Se $m=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ è la sua decomposizione in fattori primi, allora $$ \phi(m) = (p_1^{a_1} - p_1^{a_1 - 1})(p_2^{a_2} - p_2^{a_2-1})...(p_k^{a_k} - p_k^{a_k - 1}) $$ ###### Dimostrazione Dalla Proposizione precedente segue che per calcolare $\phi(m)$ basta fare il prodotto dei numeri $\phi(p_i^{a_i})$. Ci resta dunque da sapere quanto vale $\phi(p^n)$ con $p$ numero primo. Osserviamo che i numeri positivi minori di $p^n$ sono tutti primi con $p^n$ a meno che non siano multipli di $p$. Un semplice calcolo mostra che $p^n - p^{n-1}$. ###### Osservazione In particolare, se $p$ e $q$ sono due distinti numeri primi, $\phi(p^2)=p^2 - p, \ \phi(pq) = (p-1)(q-1)$. Quindi $\phi(10) = 4 \cdot 1 = 4, \ \phi(15) = 4 \cdot 2 = 8$.