Congruenze

Definizione[modifica | modifica wikitesto]

Dato un insieme si possono generare tante relazioni di equivalenza. Prendiamo un insieme con un'operazione binaria e sia una relazione di equivalenza definita su .


Definizione (112)

Si dice che è una congruenza rispetto all'operazione , o anche che è compatibile con , se , e supponiamo e , questo implica necessariamente che .

 



Queste relazioni consentono di indurre sull'insieme quoziente un'operazione che ha quasi tutte le proprietà dell'operazione .



Osservazione (113)

Se è una congruenza rispetto a , si induce un'operazione binaria chiamata sull'insieme quoziente ponendo per ogni coppia l'uguaglianza .

 


è un'operazione ben definita , perché è una congruenza e quindi preso un elemento qualsiasi in e uno in , il loro prodotto è associato a quello di altri due elementi presi rispettivamente in e , cioè e appartengono alla stessa classe di equivalenza, che chiamo .


Osservazione (114)

Si può esprimere in termini della proiezione canonica. Si chiama la proiezione canonica da a . Allora si può anche scrivere:

(la proiezione canonica conserva il prodotto). in queste condizioni è un morfismo.

 


Osservazione (115)

L'operazione indotta sul quoziente eredita alcune proprietà di . Le proprietà di esreditate da sono:

  1. le proprietà di tipo equazionale (commutativa o associativa);
  2. Se ammette unità sinistra o unità destra o unità bilatera , allora le immagini mediante la proiezione canonica che contengono funzionano da unità rispetto all'operazione indotta e si denotano con .
  3. Infine, se e ammette unità , e ammette inverso sinistro e inverso destro o inverso bilatero , ispetto a , allora l'immagine ammette rispettivamente inverso sinistro , inverso destro e inverso bilatero rispetto all'unità .
 


Proposizione (116)

[Proprietà di annullamento del prodotto] Il prodotto di due interi è diverso da .

 



Prese due matrici elementari, due matrici non nulle possono avere prodotto .


Se questa proprietà vale per , può non valere per l'operazione indotta.

Relazione di congruenza in Z[modifica | modifica wikitesto]

Definizione (117)

Sia un fissato intero . Due interi e si dicono congrui modulo se la differenza è divisibile per , cioè se , ovvero esiste tale che sia è esprimibile come . Allora questa relazione su si dice congruenza modulo e se e sono congrui mod n fra loro, scriviamo (uguale con tre lineette).

 


Osservazione (118)

Per , se e solo se e la relazione sarebbe l'identità.

 
Esempio (119)

Se , per ogni , ottengo la relazione universale, tutti gli interi sono nella stessa classe.

 
Esempio (120)

Presi i numeri relativi, si otengono le stesse classi di equivalenza che avevo ottenuto con i numeri positivi. Per questo si sceglie .

 
Esempio (121)

La relazione di equivalenza modulo consiste delle classi dei pari e dei dispari.

 


Esempio (122)

Per , allora le classi sono .

 



Si possono definire una somma e un prodotto di classi, tali che , e .


Se considero ad esempio , perché , si verifica che la proprietà dell'annullamento del prodotto non si eredita nel quoziente.

Congruenza modulo n come relazione di equivalenza[modifica | modifica wikitesto]

Nell'insieme degli interi relativi, fissato un intero positivo maggiore di si può dare la definizione di congruenza modulo : è congruo a modulo () se , cioè esiste un intero tale che .


Proposizione (123)

La relazione di congruenza è di equivalenza su e l'insieme quoziente è costituito da esattamente classi, che sono indicate con . Ogni intero è contenuto in una di queste classi.

 
Dimostrazione

Dimostro che la relazione è di equivalenza:

  1. Per ogni , se pongo (riflessiva).
  2. se , allora quindi , (simmetrica);
  3. se e , allora esiste per cui , ed esiste tale che . Sommando termine a termine ottengo , ovvero (transitiva)


Sia un intero e mostriamo che la classe che lo contiene è una di quelle indicate. Usiamo l'algoritmo della divisione.


Se , divido per e ottengo un quoziente e un resto, cioè scrivo , con . , quindi la differenza è divisibile per e , cioè la classe che contiene è quella che contiene il resto. Siccome il resto può andare da a , l'insieme delle classi di equivalenza consiste di classi.


Dimostriamo che le classi sono a due a due distinte. Supponiamo per assurdo che siano due interi fra e , e quindi supponiamo che . Allora dev'essere un multiplo di , ma , la differenza è strettamente compresa tra e . è un multiplo di se e solo se . Quindi se e solo se coincidono, quindi l'insieme quoziente consiste esattamente di classi.

 
Definizione (124)

L'insieme quoziente rispetto alla relazione di congruenza modulo si denota con e prende il nome di insieme delle classi di resti modulo .

 
Esempio (125)

Se , l'insieme quoziente di consiste di due classi , dove è la classe dei numeri pari e è quella dei numeri dispari.

 
Esempio (126)

Se ho tre oggetti: costituita dai multipli di , , .

 

Compatibilità tra congruenza e operazioni[modifica | modifica wikitesto]

Per ogni fissato modulo , la relazione di congruenza modulo è compatibile sia rispetto all'operazione di somma ordinaria, che rispetto a quella di prodotto fra interi.


Supponiamo che e . Se la relazione è compatibile rispetto alla somma, allora . Infatti, se esiste un intero tale che . Invece significa che esiste un intero tale che . Se sommo le uguaglianze termine a termine, , cioè perché i due numeri differiscono di un intero multiplo di .


Considerando la compatibilità rispetto al prodotto, . quindi e differiscono per un multiplo di .


Pertanto la somma e il prodotto tra gli interi inducono sull'insieme quoziente due operazioni ben definite, che chiameremo somma e prodotto, tali che:

Le operazioni sono ben definite perché non dipendono dalla scelta dei rappresentanti della classe di equivalenza.


Dati due interi e un'incognita , ci si chiede quando l'equazione ha soluzioni intere.


Le congruenze lineari servono anche per risolvere le equazioni diofantee, della forma , di cui si vuole capire quando le coppie sono soluzioni intere.

Tavole di composizione[modifica | modifica wikitesto]

Siccome l'insieme quoziente per ogni fissato è finito, allora si possono scrivere le tavole di composizione di queste operazioni.


Queste tavole sono matrici e permettono di evidenziare alcune proprietà. La commutatività si vede dal fatto che la tavola è simmetrica. Non si riesce a vedere l'associatività.

Esempio (127)

Esempio di tavola della somma: scrivo sulla prima riga e sulla prima colonna le classi di equivalenza in ordine, poi nelle celle faccio le operazioni tra le classi di equivalenza (ad esempio , perché mi sto riferendo alle classi di equivalenza e ). Nella cella escluse la prima riga e la prima colonna, ad esempio c'è l'operazione . Ad esempio, se .

Tavola del prodotto:

Dal fatto che nella tavola della somma la prima riga e la prima colonna rimangono invariate si capisce che l'operazione ha un elemento neutro.

 


Dal fatto che nella tavola del prodotto c'è una riga e una colonna di 0 si capisce che l'operazione ha un elemento annullatore.


Il prodotto di due classi di equivalenza diverse da 0 può essere 0.

 PrecedenteSuccessivo