Matematica Discreta
Lezione del giorno 29 aprile 2010
Se A è un gruppo finito di cardinalità n con elemento neutro eA, abbiamo definito periodo di un elemento aA il minimo intero positivo kn tale che ak=e.
Ovviamente possono esistere altri esponenti h (oltre il periodo k) tali che ah=e, ma essi dipendono dal periodo k, come afferma il prossimo risultato:
Teorema. Sia A un gruppo finito con elemento neutro eA, e sia aA un elemento di periodo k.
Per ogni intero h0 si ha:
ah = e h è multiplo del periodo k Dimostrazione:
(): Se h=0 è ovvio che h è multiplo di k. Sia dunque h>0, e dividiamo h per k mediante l’algoritmo della divisione per i numeri naturali: esistono interi q,r0 tali che h=kq+r con r<k.
Se per assurdo h non fosse multiplo di k, sarebbe r0, dunque r>0, ed inoltre:
e = ah = akq+r =(ak)q*ar = eq*ar = e*ar = ar con 0<r<k contraddizione perché k è il minimo intero positivo tale che ak = e.
(): Per ipotesi esiste un intero t0 tale che h=kt, da cui ah = akt = (ak)t = et = e.
Teorema (Lagrange). Sia A un gruppo commutativo finito di cardinalità n, con elemento neutro eA.
Allora per ogni elemento aA si ha:
1) an = e
2) il periodo k di a è divisore della cardinalità n del gruppo.
Dimostrazione:
1) Fissato aA, si definisca la funzione f: A A ponendo f(x)=a*x per ogni xA.
La funzione f è iniettiva: infatti se per assurdo esistessero b,cA, bc, tali che f(b)=f(c) si avrebbe a*b=a*c, e per la legge di cancellazione a sinistra si otterrebbe b=c, contraddizione.
Essendo dominio e codominio finiti di eguale cardinalità, f è anche surgettiva (dunque biunivoca).
Se a1,a2,…,an sono gli n elementi distinti di G, le immagini degli elementi a1,a2,…,an di A:
f(a1)=a*a1, f(a2)=a*a2,…, f(an)=a*an
sono tutti gli elementi di A (per la surgettività di f).
Dunque (dal punto di vista insiemistico):
A = { a*a1, a*a2,…, a*an } = {a1,a2,…,an }
(sono elenchi degli stessi elementi anche se non necessariamente nello stesso ordine).
Per la proprietà commutativa si ha:
(a*a1)*(a*a2)*……*(a*an) = a1*a2*……*an = e*a1*a2*……*an
Di nuovo per la proprietà commutativa (applicata al primo membro):
(an)*(a1*a2*……*an) = e*(a1*a2*……*an)
e per la legge di cancellazione a destra si ha la tesi an = e.
2) Per la 1) si ha an=e: per il Teorema precedente ciò implica che il periodo k di a è divisore dell’esponente n.
Nota: Si può dimostrare, con altre tecniche, che la tesi del Teorema vale anche nel caso di un gruppo (finito) non commutativo. Quindi in tutti i gruppi finiti elevando qualunque elemento alla cardinalità del gruppo si ottiene sempre l’elemento neutro ed il periodo di ogni elemento è divisore della cardinalità del gruppo.
Vedremo ora una importante conseguenza di questi risultati sull’aritmetica dei numeri naturali.
Teorema di Eulero-Fermat. Siano a,n due numeri naturali, con n>1, e supponiamo a,n coprimi (quindi mcd(a,n)=1). Allora, se (n) è la funzione di Eulero di n, si ha:
a(n)1 (mod n).
Dimostrazione:
Sappiamo che il gruppo commutativo finito A = Zn* (contenente le classi di congruenza modulo n simmetrizzabili rispetto al prodotto di classi) ha cardinalità (n) perché contiene le classi [a] con il rappresentante a coprimo con n.
In particolare, essendo a,n coprimi per ipotesi, si ha [a]A.
Per il Teorema precedente, ogni elemento di un gruppo finito commutativo elevato alla cardinalità del gruppo dà come risultato l’elemento neutro: nel nostro caso si ha
[1]=[a](n)=[a][a]….[a]=[aa….a]=[a(n)], da cui la tesi a(n)1 (mod n).
Corollario (Piccolo Teorema di Fermat).
Siano a,n due numeri naturali, e supponiamo che n sia un numero primo ed n non sia divisore di a.
Allora si ha:
an-11 (mod n).
Dimostrazione:
Notiamo che i numeri a,n sono coprimi (perché le uniche possibilità per il mcd(a,n) sono 1, n, e la possibilità mcd(a,n)=n è da escludere essendo n non divisore di a per ipotesi).
Poiché (n)=n-1 (perché n è primo) la tesi segue immediatamente dal Teorema di Eulero-Fermat.
