Matematica Discreta II Lezione del giorno 22 ottobre 2007 Congruenza modulo un sottogruppo

(1)

Matematica Discreta II

Lezione del giorno 22 ottobre 2007 Congruenza modulo un sottogruppo

Consideriamo nel gruppo Z degli interi relativi (rispetto all’operazione di somma) un intero fissato m e il sottoinsieme (m) contenente tutti i multipli di m:

(m) = { x / x=mk, con kZ }

Tale sottoinsieme è un sottogruppo del gruppo Z, come si verifica facilmente utilizzando il criterio per i sottogruppi (nella notazione additiva esso diventa: dati comunque x,y(m) si ha x+(-y) (m)).

La ben nota relazione di congruenza modulo m, definita nell’insieme Z ponendo:

x,yZ xy (mod m) se x-y è multiplo di m si può allora tradurre nel modo seguente:

x,yZ xy (mod m) se x-y(m)

Tutto questo si può generalizzare al caso di un gruppo qualunque: fissato un gruppo (moltiplicativo) A e un suo sottogruppo B, definiamo nell’insieme A la seguente relazione (detta congruenza modulo il sottogruppo B):

x,yA xy (mod B) se xy^-1B (se il gruppo A é additivo la condizione diventa x+(-y)B).

Verifichiamo che tale relazione è di equivalenza:

- proprietà riflessiva: per ogni xA si ha xx (mod B) perché xx^-1=1AB (essendo B sottogruppo) - proprietà simmetrica: per ogni x,yA se xy (mod B) (cioè se xy^-1B) si ha (essendo B sottogruppo) (xy^-1)^-1=(y^-1)^-1x^-1=yx^-1B, dunque yx (mod B)

- proprietà transitiva: per ogni x,y,zA se xy (mod B) (cioè se xy^-1B) e se yz (mod B) (cioè se yz^-1B) si ha (essendo B sottogruppo) (xy^-1)(yz^-1)=xz^-1B, dunque xz (mod B).

Fissato xA si può allora costruire la classe di equivalenza rappresentata da x in A in questa relazione di congruenza modulo B:

[x] = { yA / yx (mod B) } = { yA / yx^-1B } = { yA / yx^-1=bB } = { yA / y=bx, bB } Dunque gli elementi della classe [x] sono tutti i prodotti di un elemento bB per il rappresentante x.

Sia A gruppo finito, e B sottogruppo di cardinalità m. Se elenchiamo gli m elementi distinti di B:

B = { b1, b2, ………., bm }

gli elementi della classe rappresentata da un generico elemento xA nella relazione di congruenza modulo B sono:

{ b1x, b2x, ………., bmx }

e tali elementi sono distinti (se per assurdo fosse bix=bjx con ij, per la legge di cancellazione valida nel gruppo A si avrebbe bi=bj , contraddizione). Dunque la cardinalità di ogni classe di congruenza modulo B coincide con la cardinalità m di B.

Da ciò segue il:

Teorema di Lagrange. Siano A un gruppo finito di cardinalità n, e sia B un sottogruppo di A di cardinalità m. Allora m è un divisore di n.

(2)

Dimostrazione:

Dalla teoria generale delle relazioni di equivalenza, segue che le classi di congruenza modulo m costituiscono una partizione del gruppo A (cioè due classi distinte hanno intersezione vuota e l’unione di tutte le classi distinte coincide con A).

Dunque la cardinalità n di A coincide con la somma delle cardinalità delle distinte classi di congruenza modulo B. Ma si è osservato che ogni classe ha la stessa cardinalità m del sottogruppo B, dunque, se k è il numero di classi distinte, n coincide con la somma di k addendi tutti uguali ad m, ossia n=mk, e si ha la tesi.

Questo teorema limita la possibilità della cardinalità di un sottogruppo di un gruppo finito ai soli valori divisori della cardinalità del gruppo: per esempio se il gruppo A ha cardinalità 20, un sottogruppo B di A può avere solo cardinalità 1,2,4,5,10,20 (anche se non è detto che esista necessariamente qualche sottogruppo B per ognuno di tali valori).