Matematica Discreta
Lezione del giorno 6 maggio 2009
Dato un gruppo A (rispetto all’operazione *) abbiamo definito il concetto di potenza di un elemento aA con esponente intero k0 nel modo seguente:
- se k>0 ak = a*a*……*a (con k operandi) - se k=0 a0 = e (elemento neutro di A).
Teorema. Se A è un gruppo finito di cardinalità n, fissato un elemento aA esiste sempre qualche intero k>0, kn tale che ak = e.
Dimostrazione:
Consideriamo le seguenti potenze di a:
a0, a1, ……….., an
Tali elementi di A non sono tutti distinti (se così fosse sarebbero n+1 elementi di A, in contraddizione con l’ipotesi che n è la cardinalità di A), dunque esistono almeno 2 interi t,s tali che ts, 0t,sn, at = as. Supponiamo per esempio t>s (se t<s si ragiona in modo analogo).
Se s=0 si ha la tesi, perché allora at = a0 = e, con t>0, tn, e basta scegliere k=t.
Sia dunque s>0.
Allora da at = as segue at = e*as, e poiché at = a*a*……*a (con t operandi), as = a*a*……*a (con s operandi), applicando s volte la legge di cancellazione a destra (valida nel gruppo A):
at-s = e con t-s>0, t-stn
Si ottiene anche in questo caso la tesi, scegliendo k=t-s.
Se A è un gruppo finito di cardinalità n, e se fissiamo un elemento aA, per il Teorema precedente esistono esponenti positivi k tali che ak = e, dunque (per l’Assioma del minimo) possiamo considerare il più piccolo intero positivo k tale che ak = e, detto periodo dell’elemento a.
Sempre per il Teorema precedente si ha che il periodo k di un elemento a è sempre della cardinalità n del gruppo A.
Notiamo anche che ovviamente il periodo dell’elemento neutro è sempre k=1 perché e1 = e.
Esempio. Consideriamo il gruppo delle classi di congruenza modulo 18 che sono simmetrizzabili rispetto all’operazione di prodotto di classi (sappiamo che sono le classi il cui rappresentante e 18 sono coprimi):
Z18* = {[1],[5],[7],[11],[13],[17]}
e calcoliamo per esempio il periodo dell’elemento a=[7], cioè il minimo intero positivo k tale che [7]k = [1] (perché [1] è in questo caso l’elemento neutro del gruppo).
Si ha:
[7]1 = [7];
[7]2 = [7][7] = [77] = [49] = [13] (perché 13 è il resto della divisione di 49 per 18);
[7]3 = [7]2[7] = [13][7] = [137] = [91] = [1] (perché 1 è il resto della divisione di 91 per 18) Dunque k=3 è il periodo dell’elemento a=[7] nel gruppo Z18*.
Facendo i calcoli per tutti gli elementi di Z18* si ottengono i seguenti risultati:
[1] ha periodo 1;
[17] ha periodo 2;
[7], [13] hanno periodo 3;
[5], [11] hanno periodo 6.
Si può notare in questo esempio che non solo il periodo di ogni elemento è della cardinalità 6 del gruppo, ma è anche divisore della cardinalità 6 del gruppo (dimostreremo in seguito che ciò non è casuale).
Teorema. Sia A un gruppo finito di cardinalità n, 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. Per ogni elemento aA si ha an = e (dunque, per il Teorema precedente, il periodo k di a è divisore della cardinalità n del gruppo).
Dimostrazione:
Siano a1,a2,…,an gli n elementi distinti di G. Fissato aA, si definisca la funzione f: A A ponendo f(x)=a*x per ogni xA.
La funzione f è iniettiva: 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 avrebbe b=c, contraddizione.
Essendo dominio e codominio finiti di eguale cardinalità, f è anche surgettiva, dunque le immagini degli elementi a1,a2,…,an di A:
a*a1,a*a2,…,a*an
sono tutti gli elementi di A.
Dunque (dal punto di vista insiemistica):
A = { aa1,aa2,…,aan } = {a1,a2,…,an }
(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:
an*(a1*a2*……*an) = e*(a1*a2*……*an)
e per la legge di cancellazione a destra si ha la tesi an = e.
Nota: Si può dimostrare, con altre tecniche, che la tesi del Teorema vale anche nel caso di un gruppo (finito) non commutativo.
Teorema di Eulero-Fermat. Siano a,n due numeri naturali, con n>1, e con 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:
Il gruppo commutativo finito A= Zn* (contenente le classi di congruenza modulo n simmetrizzabile rispetto al prodotto di classi) ha cardinalità (n) perché contiene le classi con rappresentante coprimo con n. In particolare, essendo a,n coprimi, 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).
Se n è un numero primo, per ogni naturale a non multiplo di n si ha an-11 (mod n).
Dimostrazione:
Essendo a non multiplo del primo n, 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 non essendo n divisore di a). Poiché
(n)=n-1 (perché n è primo) la tesi segue immediatamente dal Teorema di Eulero-Fermat.
