RELAZIONE DI CONGRUENZA
- I numeri relativi
- Divisione
- Relazione tra insiemi
- Relazioni in un insieme
- Relazione di equivalenza
- Congruenza modulo n in Z
- Implicazione logica
Nella lezione precedente abbiamo parlato della RELAZIONE DI CONGRUENZA nell'insieme Z.
La RELAZIONE DI CONGRUENZA è una RELAZIONE DI EQUIVALENZA, cioè essa gode:
- della PROPRIETA' RIFLESSIVA;
- della PROPRIETA' SIMMETRICA;
- della PROPRIETA' TRANSITIVA.
PROPRIETA' RIFLESSIVA.
E' chiaro che dividendo a per n otteniamo sempre lo stesso resto. Quindi:
che si legge
a congruo a modulo n.
PROPRIETA' SIMMETRICA.
Possiamo dire che a è congruo b modulo n se dividendo a e b per n otteniamo lo stesso resto. E' evidente allora che possiamo dire, indifferentemente, che a congruo b modulo n o che b congruo a modulo n.
che si legge
se a congruo b modulo n allora b congruo a modulo n.
PROPRIETA' TRANSITIVA.
Possiamo dire che a è congruo b modulo n se dividendo a e b per n otteniamo lo stesso resto, che chiamiamo r.
In questo caso, quindi, possiamo scrivere:
b = nk + r.
Possiamo dire che b è congruo c modulo n se dividendo b e c per n otteniamo lo stesso resto, che chiamiamo r'.
Di conseguenza possiamo scrivere:
b = nk + r'.
Ma poiché
b = b
dovrà essere anche
nk + r = nk + r'
e quindi deve essere
r = r'.
Quindi possiamo dire che
che si legge
se a congruo b modulo n e b congruo c modulo n allora a congruo c modulo n.
