Matematica Discreta II
Lezione del giorno 24 ottobre 2007
Potenza di un elemento di un gruppo ad esponente intero relativo.
Siano A un gruppo (moltiplicativo) ed aA un elemento fissato.
Per ogni intero relativo kZ definiamo la potenza ak di a con esponente k nel modo seguente:
1A se k=0 ak = a∙a∙….∙a (k fattori) se k>0 a-1∙a-1∙….∙a-1 (-k fattori) se k<0 Esempio:
Nel gruppo moltiplicativo Z20* = { 1,3,7,9,11,13,17,19 } (identificando ogni classe di congruenza [x] con il rappresentante x), fissiamo a=3. Essendo 3∙7=21mod20=1, si ha 7=3-1.
Allora per esempio 33=3∙3∙3=27mod20=7, mentre 3-2=3-1∙3-1=7∙7=49mod20=9.
Se l’operazione del gruppo A è denotata additivamente, si preferisce parlare di multiplo ka di a con coefficiente k:
0A se k=0 ka = a+a+….+a (k addendi) se k>0 (-a)+(-a)+….+(-a) (-k addendi) se k<0
Per le potenze di un elemento di un gruppo valgono le stesse proprietà delle potenze numeriche:
se A è un gruppo (moltiplicativo) ed aA un elemento fissato, comunque presi gli interi relativi h,kZ si ha ah∙ak=ah+k , (ah)k=ahk (tali proprietà si dimostrano facilmente distinguendo i vari casi per i segni possibili degli interi h,k).
Esempio:
Nel gruppo additivo Z20 = { [0],[1],[2],[3],….,[19] } fissiamo a=[3]. Essendo [3]+[17]=[20]=[0], si ha –[3]=[17].
Allora per esempio:
8[3]=[3]+[3]+[3]+[3]+[3]+[3]+[3]+[3]=[24]=[4]
-2[3]=(-[3])+(-[3])=[17]+[17]=[34]=[14]
Siano A un gruppo (moltiplicativo) ed aA un elemento fissato.
Diremo che a è un elemento aperiodico se l’unico esponente intero relativo kZ tale che ak=1A è k=0; diremo invece che a è un elemento periodico se esiste qualche esponente intero relativo kZ, k0, tale che ak=1A .
Se a è un elemento periodico e se ah=1A con h<0 , allora anche a-h=(ah)-1=1A-1=1A : dunque se a è un elemento periodico esiste sempre qualche esponente intero k positivo tale che ak=1A, e il più piccolo intero k>0 tale che ak=1A sarà detto periodo dell’elemento periodico a.
Esempio:
Nel gruppo moltiplicativo Z20* = { 1,3,7,9,11,13,17,19 } (identificando ogni classe di congruenza [x] con il rappresentante x), fissiamo a=3. Essendo 31=3, 32=9, 33=27mod20=7, 34=81mod20=1, si ha che 3 è elemento periodico di periodo 4.
Nel gruppo moltiplicativo Q* dei numeri razionali non nulli l’elemento a=1/2 è aperiodico, perché non esiste un intero relativo k0 tale che (1/2)k=1/(2k)=1.
Teorema. Siano A un gruppo (moltiplicativo) ed aA un elemento fissato. Allora l’insieme di tutte le possibili potenze di a ad esponente intero relativo:
(a) = { x / x=ak con kZ } é un sottogruppo del gruppo A.
Dimostrazione:
Basta applicare il criterio per i sottogruppi: se x=ak, y=ah(a) si ha xy-1=ak-h(a).
Il sottogruppo (x) è detto sottogruppo ciclico generato da a.
Vedremo che la struttura di tale sottogruppo dipende dalla periodicità o aperiodicità dell’elemento a.
Teorema. Siano A un gruppo (moltiplicativo) ed aA un elemento fissato.
1) Se a è elemento aperiodico, al variare dell’esponente kZ le potenze ak sono tutte distinte
2) Se a è elemento periodico di periodo k, due potenze di a ad esponente intero relativo sono uguali se e solo se gli esponenti sono congrui modulo il periodo k:
ai=aj ij (mod k) Dimostrazione:
1) Sia a elemento aperiodico e per assurdo sia ai=aj con gli esponenti ij; allora moltiplicando ambo i membri per a-j si otterrebbe ai-j=1A con i-j0, contraddizione perché a è aperiodico.
2) : Se ai=aj supponiamo ij (se i=j la tesi è banale) e sia per esempio i>j; allora moltiplicando ambo i membri per a-j si ottiene ai-j=1A con i-j>0; se dividiamo i-j per il periodo k si ha i-j=kq+r con q,r≥0, r<k. Si ricava allora 1A= ai-j=akq+r=(ak)qar=(1A)qar=ar; ma allora r=0 (se fosse r>0 si avrebbe 1A=ar con 0<r<k, contro la definizione di periodo k). Dunque i-j=kq e si ha la tesi.
: Se ij (mod k), si ha i-j=kq con q intero, i=j+kq, ai=aj+kq=aj(ak)q=aj e si ha la tesi.
Conseguenze del Teorema :
1) Se a è elemento aperiodico del gruppo A, il sottogruppo ciclico (a) generato da a é infinito: in particolare un gruppo finito A non può contenere elementi aperiodici.
2) Se a è elemento periodico di periodo k del gruppo A, poiché le classi di congruenza distinte modulo k sono [0],[1],….,[k-1] e dunque ogni intero relativo h è congruo ad uno e uno solo dei numeri 0,1,…,k-1, si ha che le potenze distinte di a sono a0,a1,…,ak-1, dunque il sottogruppo ciclico (a) generato da a coincide con l’insieme {a0,a1,…,ak-1} e quindi tale sottogruppo ha cardinalità uguale al periodo k di a. In particolare, per il Teorema di Lagrange si ha: se a è elemento periodico del gruppo finito A, il periodo k di a è divisore della cardinalità del gruppo A.
Esempio:
Nel gruppo moltiplicativo Z20* = { 1,3,7,9,11,13,17,19 } (identificando ogni classe di congruenza [x] con il rappresentante x), abbiamo già verificato che l’elemento a=3 ha periodo 4 (come previsto è divisore della cardinalità 8 del gruppo). Il sottogruppo ciclico generato da 3 è dunque:
(3) = {30=1, 31=3, 32=9, 33=7 }.
Teorema.
Se A è un gruppo (moltiplicativo) finito di cardinalità n, per ogni elemento aA si ha an=1A . Dimostrazione:
Essendo A gruppo finito, un generico elemento aA è periodico: se k è il periodo di a, abbiamo dimostrato che k è divisore di n=A, dunque n=kq con q intero, da cui an=(ak)q=(1A)q=1A .
Teorema di Eulero-Fermat. Siano a,n numeri naturali con a,n coprimi, e sia (n) la funzione di Eulero di n.
Allora si ha: a(n) 1 (mod n)
Dimostrazione:
Consideriamo il gruppo moltiplicativo Zn* = {[x] / x,n coprimi}: è un gruppo di cardinalità (n), e per ipotesi contiene [a]. Per il Teorema precedente si ha [a](n)=[1], da cui:
[1]= [a](n)=[a][a]….[a]=[aa…..a]=[a(n)] e si ottiene la tesi a(n) 1 (mod n) .
Corollario (Piccolo Teorema di Fermat). Siano a,n numeri naturali, con n primo ed a non multiplo di n.
Allora si ha: an-1 1 (mod n) Dimostrazione:
Essendo n primo, si ha mcd(a,n)=1 opppure mcd(a,n)=n: ma non può essere mcd(a,n)=n perché n non è divisore di a, dunque a,n sono coprimi. Per il Teorema di Eulero-Fermat, essendo (n)=n-1, si ottiene la tesi an-1 1 (mod n) .
