Matematica Discreta Lezione dei giorni 19 e 26 aprile 2012 Operazioni compatibili con una relazione di equivalenza.

Matematica Discreta

Lezione dei giorni 19 e 26 aprile 2012

Operazioni compatibili con una relazione di equivalenza.

Consideriamo un insieme A in cui sia definita una relazione di equivalenza R: ricordiamo che se l’elemento xA è associato nella relazione R all’elemento yA scriviamo il simbolo xRy.

Inoltre per ipotesi R soddisfa le proprietà riflessiva, simmetrica e transitiva.

Sappiamo che, fissato xA, si può costruire la classe di equivalenza rappresentata da x, contenente tutti gli elementi di A che sono associati ad x nella relazione R:

[x] = { yA / xRy }

Ricordiamo inoltre che le distinte classi di equivalenza formano una partizione di A (cioè 2 classi diverse hanno intersezione vuota, e l’unione di tutte le classi è l’insieme A).

Si ha inoltre, per un risultato già dimostrato:

[x]=[y]  xRy .

Indicheremo con il simbolo A/R l’insieme delle classi di equivalenza della relazione R in A (è detto anche insieme quoziente dell’insieme A rispetto alla relazione di equivalenza R).

Supponiamo anche che nell’insieme A sia definita (oltre alla relazione di equivalenza R) anche un’operazione *.

Potremmo allora provare a definire nell’insieme A/R delle classi di equivalenza un’operazione fra classi (che indichiamo sempre con il simbolo *) servendoci dell’operazione * (che è definita nell’insieme A) nel modo seguente:

[a]*[b] = [a*b]

(quindi per calcolare il risultato dell’operazione sulle classi [a],[b] prima si calcola il risultato dell’operazione * sui rappresentanti a,b, ottenendo un elemento a*b in A, e poi si considera la classe rappresentata da tale elemento, e questa classe si considera come risultato dell’operazioni fra le 2 classi [a],[b]).

Ciò solleva però un problema: il concetto di operazione implica l’unicità del risultato (perché l’operazione è una funzione che associa ad ogni coppia di operandi uno e un solo risultato). Quindi per essere certi che la nostra operazione fra classi abbia risultato unico (fissate le 2 classi su cui si opera) dobbiamo essere sicuri che se [a]=[c] e se [b]=[d] (abbiamo lasciato invariate le 2 classi ma cambiato il rappresentante) allora si ha sempre [a*b]=[c*d] (il risultato deve essere invariato). Tale proprietà si può esprimere in modo equivalente nel modo seguente:

se aRc, e se bRd allora necessariamente (a*b)R(c*d)

(tale proprietà è detta compatibilità della relazione di equivalenza R con l’operazione *).

Riassumendo dunque: se in un insieme A sono definite sia una relazione di equivalenza R che un’operazione *, e se R è compatibile con * (cioè se da aRc, bRd segue sempre (a*b)R(c*d)) allora nell’insieme A/R delle classi di equivalenza si può definire un’operazione * fra classi (con risultato unico) ponendo [a]*[b] = [a*b].

Tale operazioni fra classi di equivalenza è detta operazione indotta dall’operazione * definita in A.

Operazioni fra classi congruenza.

Ricordiamo che, fissato un intero m>1 (modulo), abbiamo definito nell’insieme Z degli interi

relativi una relazione di equivalenza, detta congruenza modulo m: dati gli interi x,yZ, x

associato con y quando (x-y) è multiplo di m (cioè se esiste kZ tale che x-y=mk).

Ricordiamo anche che se x è associato con y si scrive xy (mod m) invece di xRy (e si legge x congruo y modulo m).

Si possono costruire dunque le classi di equivalenza di tale relazione, che sono dette classi di congruenza modulo m.

Abbiamo dimostrato anche che le classi di congruenza distinte modulo m sono le seguenti:

[0], [1], ……, [m-1]

e quindi sono in numero di m (cioè in numero uguale al modulo).

L’insieme quoziente di Z rispetto alla relazione di congruenza modulo m (cioè l’insieme delle classi di congruenza modulo m) sarà indicato con il simbolo Z

: quindi

Z

= { [0], [1], ……, [m-1] }

Esempi: l’insieme delle classi di congruenza distinte modulo 7 è il seguente:

Z

= { [0], [1], [2], [3], [4], [5], [6] }

Dimostreremo ora che sia l’operazione di somma che quella di prodotto esistenti fra numeri interi relativi in Z sono compatibili con la relazione di congruenza modulo m.

Compatibilità della congruenza modulo m con la somma di numeri interi relativi:

se ac (mod m), e se bd (mod m) allora m è divisore delle differenze a-c, b-d, dunque a-c=mk, b-d=mh (con k,h interi)

da cui:

(a+b)-(c+d)=m(h+k)

ossia m è divisore della differenza (a+b)-(c+d) e si conclude che (a+b)(c+d) (mod m) Compatibilità della congruenza modulo m con il prodotto:

con le stesse notazioni, si ha:

(ab)-(cd)=a(b-d)+d(a-c)=m(ah+dk)

ossia m è divisore della differenza (ab)-(cd) e si conclude che (ab)(cd) (mod m).

Dalla compatibilità delle operazioni di somma e prodotto con la relazione di congruenza modulo m, segue che é possibile definire, nell’insieme Z

delle classi di congruenza modulo m, le operazioni di somma e prodotto fra classi di congruenza, operazioni indotte dalle operazioni di somma e prodotto fra numeri interi e definite nel modo seguente:

[a]+[b] = [a+b] [a][b] = [ab]

Esempio.

Consideriamo l’insieme Z

delle 7 classi di congruenza modulo 7:

Z

= { [0],[1],[2],[3],[4],[5],[6] } e le seguenti classi di congruenza modulo 7 [5], [6]Z

Possiamo allora calcolare la somma e il prodotto di queste 2 classi:

[5]+[6] = [5+6] = [11] = [4] (perché 114 (mod 7)) [5][6] = [56] = [30] = [2] (perché 302 (mod 7)) Esempio.

Consideriamo l’insieme Z

delle 4 classi di congruenza modulo 4:

Z

= {[0],[1],[2],[3]}

Se costruiamo la tavola operazionale della somma fra classi (rispetto all’ordine [0],[1],[2],[3])

otteniamo la seguente matrice 4x4:



 









 







] 2 [ ] 1 [ ] 0 [ ] 3 [

] 1 [ ] 0 [ ] 3 [ ] 2 [

] 0 [ ] 3 [ ] 2 [ ] 1 [

] 3 [ ] 2 [ ] 1 [ ] 0 [

(per calcolare per esempio [2]+[3] si calcola [2+3]=[5]=[1], notando che 51 (mod 4) etc…..) Se invece costruiamo la tavola operazionale del prodotto fra classi (rispetto sempre all’ordine [0], [1],[2],[3]) otteniamo la seguente matrice 4x4:



 









 







] 1 [ ] 2 [ ] 3 [ ] 0 [

] 2 [ ] 0 [ ] 2 [ ] 0 [

] 3 [ ] 2 [ ] 1 [ ] 0 [

] 0 [ ] 0 [ ] 0 [ ] 0 [

(per calcolare per esempio [2][3] si calcola [23]=[6]=[2], notando che 62 (mod 4) etc…..) Proprietà che si trasmettono da un’operazione all’operazione indotta.

Torniamo al caso generale di un insieme A in cui sono definite sia una relazione di equivalenza R che un’operazione * compatibile con R, in modo che nell’insieme quoziente A/R delle classi di equivalenza sia definita un’operazione indotta * fra le classi.

Notiamo che in tale caso molte proprietà dell’operazione * dell’insieme A si trasmettono all’analoga operazione * dell’insieme delle classi A/R:

1) se l’operazione * in A é associativa, l’operazione indotta * in A/R é anch’essa associativa. Infatti, date 3 classi [a],[b],[c] si ha (sfruttando la proprietà associativa valida in A):

[a]*([b]*[c]) = [a]*[b*c] = [a*(b*c)] = [(a*b)*c] = [a*b]*[c] = ([a]*[b])*[c]

2) se l’operazione * in A é commutativa, l’operazione indotta * in A/R é anch’essa commutativa.

Infatti, date 3 classi [a],[b],[c] si ha (sfruttando la proprietà commutativa valida in A):

[a]*[b] = [a*b] = [b*a] = [b]*[a]

3) se esiste l’elemento neutro eA rispetto all’operazione *, allora esiste anche l’elemento neutro nell’insieme delle classi A/R rispetto all’operazione indotta * ; inoltre tale elemento neutro é la classe [e]. Infatti per ogni classe [a] si ha:

[a]*[e] = [a*e] = [a] ; [e]*[a] = [e*a] = [a]

4) se un elemento aA é simmetrizzabile rispetto all’operazione * con simmetrico a’A, allora la classe [a] é simmetrizzabile nell’insieme delle classi A/R rispetto all’operazione indotta * ed il suo simmetrico é la classe [a’]. Infatti si ha :

[a]*[a’] = [a*a’] = [e] = elemento neutro di A/R; [a’]*[a] = [a’*a] = [e] = elemento neutro di A/R In particolare:

- se A é monoide rispetto all’operazione *, anche A/R é monoide rispetto all’operazione indotta * - se A é gruppo rispetto all’operazione *, anche A/R é gruppo rispetto all’operazione indotta * Inoltre se A è monoide (rispettivamente gruppo) commutativo anche A/R lo é.

Applichiamo le considerazioni precedenti all’insieme Z

delle classi di congruenza modulo m, in cui abbiamo definito le operazioni di somma e prodotto di classi, indotte dalle operazioni di somma e prodotto fra interi.

Vediamo quali proprietà hanno tali operazioni.

Essendo Z un gruppo commutativo rispetto all’operazione di somma (con elemento neutro 0 e con

simmetrico di un elemento a uguale all’opposto –a) per le osservazioni precedenti si ottiene che

l’insieme Z

delle classi di congruenza modulo m é un gruppo commutativo rispetto all’operazione di somma fra classi (l’elemento neutro sarà [0] e il simmetrico di una classe [a]

sarà la classe [-a]).

Invece essendo Z solo un monoide commutativo rispetto all’operazione di prodotto (con elemento neutro 1) per le osservazioni precedenti si ottiene che l’insieme Z

delle classi di congruenza modulo m é un monoide commutativo rispetto all’operazione di prodotto fra classi (l’elemento neutro sarà [1]).

Per quanto riguarda l’operazione di somma fra classi in Z

, possiamo notare che per calcolare il simmetrico (sempre rispetto alla somma) di una classe [a] scelta fra le classi {[0], [1],..., [m-1]}, vi é una regola pratica molto semplice:

- se [a] = [0], il suo simmetrico é [0] (l’elemento neutro ha come simmetrico sé stesso)

- se [a]  [0] (quindi se a=1,2...,m-1) allora il simmetrico di [a] é la classe [m-a] (infatti sommando [a] con [m-a] si ottiene [a]+[m-a] = [a+m-a] = [m] = [0] = elemento neutro, perché r=0 é il resto della divisione di m per m).

Per esempio in Z

il simmetrico di [48] é [100-48] = [52].

Abbiamo detto che rispetto all’operazione di prodotto di classi, l’insieme Z

é un monoide commutativo (con elemento neutro [1]), perché tale è Z rispetto al prodotto.

Tale monoide Z

non è un gruppo: possiamo infatti notare che [0] non é certamente simmetrizzabile rispetto al prodotto fra classi, in quanto non può esistere il simmetrico di [0], perché il prodotto di [0] per qualunque classe dà come risultato sempre [0] (quindi non si ottiene mai [1] che é l’elemento neutro).

Se esaminiamo per esempio la tavola operazionale del prodotto in Z

(vista in precedenza) si verifica che gli unici elementi simmetrizzabili sono [1] e [3].

Resta da risolvere un problema generale: nel monoide Z

(rispetto all’operazione di prodotto fra classi) quali sono gli elementi simmetrizzabili e come si calcola il loro simmetrico (cioé il loro inverso) ?

Ricordiamo anche che l’insieme degli elementi simmetrizzabili del monoide Z

é un gruppo (indicato con Z

*) rispetto alla stessa operazione di prodotto fra classi (ed é ovviamente commutativo anch’esso).

Abbiamo già notato che [0] non é certamente simmetrizzabile rispetto al prodotto fra classi, dunque gli elementi simmetrizzabili nel monoide Z

sono da cercare fra le classi diverse da [0], cioé fra le classi [1],..., [m-1].

Il prossimo risultato che dimostreremo caratterizza fra queste classi quali sono simmetrizzabili.

Teorema. Una classe [a] del monoide Z

, con il rappresentante a scelto fra 1,...,m-1, é simmetrizzabile rispetto al prodotto fra classi  il rappresentante a della classe é coprimo con il modulo m (ossia mcd(a,m)=1).

Dimostrazione:

(): Se [a] é simmetrizzabile, esiste il suo simmetrico [b] tale che [a][b]=[ab]=[1], dunque si ha la congruenza:

ab1 (mod m)

ossia m è un divisore della differenza (ab-1) dunque esiste un intero k tale che (ab-1)=mk, ossia:

1=ab-(mk)=ab+m(-k)

Si ottiene che 1 é combinazione lineare di a,m con coefficienti interi relativi b,-m, e ricordando che

il mcd(a,m) é la minima combinazione lineare positiva di a,m (si ricava dalla dimostrazione del

Teorema di esistenza del massimo comune divisore) si deduce che 1=mcd(a,m) e si ha la tesi.

(): Se 1=mcd(a,m), allora, per una proprietà del massimo comune divisore, 1 é combinazione lineare di a,m a con opportuni coefficienti interi relativi x,y

1=ax+my

Da ciò si ha ax-1=m(-y), dunque m é divisore della differenza (ax-1), ossia si ha la congruenza:

ax1 (mod m)

dunque in Z

sono uguali le classi [ax]=[1]

da cui [a][x]=[1]=elemento neutro, e si conclude che [a] é simmetrizzabile (con simmetrico [x]) cioé la tesi.

Il Teorema precedente risolve non solo il problema di caratterizzare quali sono gli elementi simmetrizzabili del monoide Z

rispetto al prodotto di classi, ma per ognuno di essi illustra un algoritmo per calcolare l’inverso (cioè il simmetrico):

1) data una classe [a][0] in Z

si calcola (con l’algoritmo Euclideo) il mcd(a,m) 2) se mcd(a.m)>1 allora si conclude che [a] non é simmetrizzabile

3) se mcd(a,m)=1, allora [a] è simmetrizzabile, ed il suo simmetrico è [x] dove x è il coefficiente di a nella rappresentazione di 1 come combinazione lineare di a,m a coefficienti interi relativi:

1 = ax+my  [a]

=[x]

Per il calcolo del coefficiente x (e quindi dell’inverso di [a]) si può usare egualmente l’algoritmo Euclideo delle divisioni successive (la versione “estesa” che permette di calcolare anche i coefficienti x,y).

Sappiamo che, dato un qualunque monoide A (rispetto ad una operazione *), il suo sottoinsieme A*, contenente gli elementi simmetrizzabili, è un gruppo rispetto alla stessa operazione.

In particolare, dato il monoide Z

={[0], [1], …., [m-1]} delle classi di congruenza modulo m (rispetto all’operazione di prodotto di classi), abbiamo dimostrato che gli elementi simmetrizzabili sono le classi con rappresentante a compreso fra 1,2,…..,m-1, tali che a,m siano coprimi.

Dunque il sottoinsieme degli elementi simmetrizzabile di Z

: Z

* = {[a] Z

/ a=1,2,….,m-1; a,m coprimi}

è un gruppo, rispetto all’operazione di prodotto di classi: ovviamente la sua cardinalità coincide con la funzione di Eulero (m) del modulo m:

 Z

* = (m) Esempio.

Dato il monoide Z

delle classi di congruenza modulo 9 rispetto all’operazione di prodotto di classi:

Z

= {[0],[1],[2],[3],[4],[5],[6],[7],[8]} (di cardinalità 9)

il gruppo degli elementi simmetrizzabili contiene le classi con rappresentante compreso fra 1 e 8 e coprimo con 9 ossia:

Z

*= {[1],[2],[4],[5],[7]} (di cardinalità (9)=6) Leggi di cancellazione in un gruppo

Sia A un gruppo rispetto all’operazione *.

Affermiamo che:

dati comunque gli elementi a,b,cA tali che a*c=b*c allora si ha necessariamente a=b

(è la cosiddetta legge di cancellazione a destra, perché il secondo operando c viene “cancellato a destra” in ambo i membri dell’eguaglianza).

Dimostriamo tale legge di cancellazione: se eA è l’elemento neutro di A, e se c’A è il simmetrico di c in A, si ha (utilizzando la proprietà associativa insieme con l’ipotesi a*c=b*c ):

a=a*e=a*(c*c’)=(a*c)*c’=(b*c)*c’=b*(c*c’)=b*e=b dunque a=b (tesi).

Con ragionamento analogo si ottiene la cosiddetta legge di cancellazione a sinistra valida in ogni gruppo A:

dati comunque gli elementi a,b,cA tali che c*a=c*b allora si ha necessariamente a=b.

Notare che se A non è gruppo, tali leggi di cancellazione possono anche non valere.

Per esempio nel monoide Z

delle classi di congruenza modulo 4 rispetto al prodotto di classi si ha:

[2][3]=[6]=[2]=[2][1]

eppure non è vero che [3]=[1] (quindi non si può “cancellare” l’operando [2] nei due membri dell’eguaglianza: questo perché Z

non è un gruppo rispetto al prodotto di classi).

Potenza di un elemento di un gruppo ad esponente intero non negativo.

Siano A un gruppo rispetto all’operazione * ed aA un elemento fissato.

Vogliamo definire il concetto di potenza di base a ed esponente intero non negativo, in modo analogo a quanto si fa per le ordinarie potenze numeriche.

Per ogni numero naturale kN definiamo la potenza a

di a con esponente k nel modo seguente:

a

= a*a*….*a (dove il numero degli operandi coincide con l’esponente k) Dunque:

a

=a, a

=a*a, a

=a*a*a etc…

(notare che la validità della proprietà associativa ci permette di non specificare come si associano gli operandi: per esempio a

=(a*a)*a = a*(a*a)).

Estendiamo poi convenzionalmente la definizione di potenza anche al caso di un esponente nullo, definendo: a

= e (elemento neutro di A).

Esempio:

Consideriamo il gruppo delle classi di congruenza modulo 20 rispetto all’operazione di somma di classi:

Z

= { [0],[1],[2],[3],….,[19] } e fissiamo a=[3].

Allora per esempio:

[3]

=[3]+[3]+[3]=[3+3+3]=[9]

[3]

=[3]+[3]+[3]+[3]+[3]+[3]+[3]+[3]=[3+3+3+3+3+3+3+3]=[24]=[4]

(perché 4 è il resto della divisione di 24 per 20) [3]

=[0] (perché [0] è l’elemento neutro).

Consideriamo invece il gruppo delle classi di congruenza modulo 20 che sono simmetrizzabili rispetto all’operazione di prodotto di classi (sappiamo che sono le classi [a] con a=1,2,…..,19 e tali che mcd(a,20)=1):

Z

* = {[1],[3],[7],[9],[11],[13],[17],[19]}

e fissiamo di nuovo a=[3].

Allora per esempio:

[3]

=[3][3][3]=[333]=[27]=[7]

(perché 7 è il resto della divisione di 27 per 20).

[3]

=[1] (perché [1] è l’elemento neutro).

Per le potenze di un elemento a di un gruppo A valgono le ben note analoghe proprietà delle potenze numeriche, che ora illustreremo.

Comunque presi gli interi non negativi h,k si ha:

1) (a

)*(a

)=a

2) (a

)

=a

Dimostriamo per esempio la 1), distinguendo 3 casi e in ognuno di essi dimostrando la tesi:

caso 1: h=0; allora (indicato con eA il neutro di A) (a

)*(a

)=(a

)*(a

)=e*(a

)=a

=a

=a

;

caso 2: k=0 (dimostrazione simile)

caso 3: h,k>0; allora (a

)*(a

)=(a*a*…*a)*(a*a*…*a) (dove nella prima parentesi vi sono h operandi, nella seconda k operandi), dunque (a

)*(a

)=a*a*…*a (con un totale di h+k operandi) e si conclude che (a

)*(a

)=a

anche in questo caso.

La dimostrazione della 2) segue uno schema simile.

Teorema. Se A è un gruppo finito di cardinalità n con elemento neutro eA, fissato un elemento aA esiste sempre qualche intero k>0, k≤n tale che a

= e.

Dimostrazione:

Consideriamo le seguenti potenze di a:

a

, a

, ……….., a

Tali elementi di A non sono tutti distinti (se così fosse sarebbero n+1 elementi distinti di A, in contraddizione con l’ipotesi che n è la cardinalità di A), dunque esistono almeno 2 interi t,s tali che ts, 0t,sn, a

= a

. Supponiamo per esempio t>s (se t<s si ragiona in modo analogo).

Se s=0 si ha la tesi, perché allora a

= a

= e, con t>0, tn, e il valore di k cercato è k=t.

Supponiamo dunque s>0.

Allora da a

= a

segue a

= e*a

, e poiché a

= a*a*……*a (con t operandi), a

= a*a*……*a (con s operandi), applicando s volte la legge di cancellazione a destra (valida nel gruppo A):

a

= e con t-s>0, t-stn

Si ottiene anche in questo caso la tesi, scegliendo k=t-s.

Se A è un gruppo finito di cardinalità n con elemento neutro eA, e se fissiamo un elemento aA, per il Teorema precedente esistono esponenti positivi kn tali che a

=e, dunque (per l’Assioma del minimo) possiamo considerare il più piccolo intero positivo kn tale che a

= e, detto periodo dell’elemento a.

Notiamo anche che ovviamente il periodo dell’elemento neutro è sempre =1 perché e

= e.

Esempio. Consideriamo il gruppo delle classi di congruenza modulo 18 che sono simmetrizzabili rispetto all’operazione di prodotto di classi ([a] con a=1,2,…..,17 e tali che mcd(a,18)=1):

Z

* = {[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]

= [1] (perché [1] è in questo caso l’elemento neutro del gruppo).

Si ha:

[7]

= [7];

[7]

= [7][7] = [77] = [49] = [13] (perché 13 è il resto della divisione di 49 per 18);

[7]

= [7]

[7]

= [13][7] = [137] = [91] = [1] (perché 1 è il resto della divisione di 91 per 18) Dunque k=3 è il periodo dell’elemento a=[7] nel gruppo Z

*.

Facendo i calcoli per tutti gli elementi di Z

* 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).

Se A è un gruppo finito di cardinalità n con elemento neutro eA, abbiamo dunque definito periodo di un elemento aA il minimo intero positivo kn tale che a

=e.

Ovviamente possono esistere altri esponenti h (oltre il periodo k) tali che a

=e, ma essi dipendono

dal periodo k, come afferma il prossimo risultato:

Teorema. Sia A un gruppo finito con elemento neutro eA, e sia aA un elemento di periodo k.

Per ogni intero h0 si ha:

a

= 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,r0 tali che h=kq+r con r<k.

Se per assurdo h non fosse multiplo di k, sarebbe r0, dunque r>0, ed inoltre:

e = a

= a

=(a

)

*a

= e

*a

= e*a

= a

con 0<r<k contraddizione perché k è il minimo intero positivo tale che a

= e.

(): Per ipotesi esiste un intero t0 tale che h=kt, da cui a

= a

= (a

)

= e

= e.

Teorema (Lagrange). Sia A un gruppo commutativo finito di cardinalità n, con elemento neutro eA.

Allora per ogni elemento aA si ha:

1) a

= e

2) il periodo k di a è divisore della cardinalità n del gruppo.

Dimostrazione:

1) Fissato aA, si definisca la funzione f: A  A ponendo f(x)=a*x per ogni xA.

La funzione f è iniettiva: infatti se per assurdo esistessero b,cA, bc, 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 a

,a

,…,a

sono gli n elementi distinti di G, le immagini degli elementi a

,a

,…,a

di A:

f(a

)=a*a

, f(a

)=a*a

,…, f(a

)=a*a

sono tutti gli elementi di A (per la surgettività di f).

Dunque (dal punto di vista insiemistico):

A = { a*a

, a*a

,…, a*a

} = {a

,a

,…,a

}

(sono elenchi degli stessi elementi anche se non necessariamente nello stesso ordine).

Per la proprietà commutativa si ha:

(a*a

)*(a*a

)*……*(a*a

) = a

*a

*……*a

= e*a

*a

*……*a

Di nuovo per la proprietà commutativa (applicata al primo membro):

(a

)*(a

*a

*……*a

) = e*(a

*a

*……*a

)

e per la legge di cancellazione a destra si ha la tesi a

= e.

2) Per la 1) si ha a

=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

1 (mod n).

Dimostrazione:

Sappiamo che il gruppo commutativo finito A = Z

* (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]

=[a][a]….[a]=[aa….a]=[a

], da cui la tesi a

1 (mod n).