Le congruenze sono un linguaggio alternativo per trattare la divisibilità fra interi:

 

Definizione. Siano a e b due interi e m un intero strettamente positivo, detto modulo.

Si dice che a e b sono congruenti modulo m, in simboli

a º b  (mod m)

se m divide a-b .

 

In altre parole, possiamo dire che a è congruo a b modulo m se a e b differiscono per un multiplo di m, cioè

a º b  (mod m)  Û m|(a-b)  Û  esiste un kÎ Z tale che a-b = km Û

a = b +km,  con kÎZ.

In particolare, affermare che m divide a è equivalente a dire che a è congruo a 0 modulo m (basta porre  b=0 nelle equivalenze sopra).

Possiamo così riformulare il lemma di divisione studiato nella divisibilità fra interi per il caso delle congruenze:

 

Lemma di divisione. Dati due interi a,b con a positivo, esiste ed è unico un intero r con 0 £ r < a e tale che

b º r  (mod a)

ove r si dice  resto di a modulo m (è l’equivalente di dire b=q×a+r).

 

Poiché la relazione di congruenza è una relazione di equivalenza, gode delle seguenti proprietà:

 

1)      proprietà riflessiva:        a º a  (mod m)  per ogni aÎZ;

2)      proprietà simmetrica:     se a º b  (mod m), allora b º a  (mod m);

3)      proprietà transitiva:        se a º b  (mod m) e c º b  (mod m), allora a º c  (mod m).

 

Infatti è facile dimostrare che:

1)      a-a=0 è sempre divisibile per ogni intero m diverso da zero;

2)      se m|(a-b), allora m|(b-a) per le proprietà della divisibilità fra interi;

3)      se m|(a-b) e m|(c-b), allora esistono due interi k.t tali che a-b = km  e c-b = tm, quindi se consideriamo c-a = c-b-a+b = tm+km = (t+k)m abbiamo che m|(c-a).

 

Di seguito riporteremo altre facili proprietà della relazione di congruenza:

 

Proprietà i) Dati a,b interi, allora a º b  (mod m) se e solo se a e b hanno lo stesso resto modulo m.

Dimostrazione

Proprietà ii)       Se a º b  (mod m), per ogni intero k, avremo

ak º bk  (mod m)  e  a+k º b+k  (mod m). 

 

In altre parole, moltiplicando o sommando ad entrambi i membri un numero intero, il risultato non cambia.

Dimostrazione

Osservazione.   In generale però non è sempre vera l’implicazione opposta, cioè

se ak º bk  (mod m), allora non è detto che a º b  (mod m);

questo viene verificato solo quando k e m sono relativamente primi fra loro.

 

Proprietà iii)     Se ak º bk  (mod m) e MCD(k,m)=1, allora a º b  (mod m).

Dimostrazione

Generalizzando la proprietà ii) possiamo concludere che la relazione di congruenza è chiusa rispetto alla moltiplicazione e alla somma:

Proprietà iv)     Posto a º b  (mod m)  e a’ º b’  (mod m ), allora abbiamo

1)     (a+a’) º (b+b’)  (mod m),

2)     aa’ º bb’ (mod m).

Dimostrazione

Proprietà v)       Se a º b (mod m), allora per ogni n naturale positivo, aⁿ º bⁿ  (mod m).

Dimostrazione

Proprietà vi)     Se a º b (mod m), allora (-a) º (-b)  (mod m).

Dimostrazione

Il teorema che segue dice che se a è un intero non divisibile per un primo p, allora c’è una periodicità nei resti delle potenze di a.

 

Teorema di Fermat.

Sia p un primo e a un intero relativamente primo con p, allora

a^p-1 º 1  (mod p)            I formulazione;

a^p º a  (mod p)              II formulazione.

Le due formulazioni sono equivalenti.

Dimostrazione

Osservazione. Se si omette la condizione che MCD(a,p)=1, cioè che a e p siano relativamente primi fra loro, la tesi del teorema di Fermat non è più verificata.

Esempio