Lezioni di matematica on line
Definizione: siano x e y due interi e m∈N: m≥0. Si dice che x e y sono congruenti modulo n, in simboli a ≡ b se n divide x-y .
In altre parole, possiamo dire che x è congruente a y modulo m se x e y differiscono per un multiplo di m, cioè x ≡ y se m divide(x-y), ovvero se esiste un p∈Z tale che x-y = pm, ovvero x = y+pm, con p∈Z.
In particolare possiamo affermare che m divide x è come dire che x è congruente a 0 (basta porre y=0 nelle equivalenze sopra).
La relazione così definita è una relazione di equivalenza infatti, gode delle seguenti proprietà:
proprietà riflessiva: x ≡ x ∀ x≡Z; infatti x-x=0 è sempre divisibile per ogni intero m diverso da zero;
proprietà simmetrica: se x ≡ y, allora y ≡ x; infatti se m divide (x-y), allora m divide (y-x), per le proprietà della divisibilità fra interi;
proprietà transitiva: se x ≡ y e y ≡ z, allora x ≡ z. infatti se m divide(x-y) e m divide(z-y), allora esistono due interi p, q tali che x-y = pm e z-y = qm, quindi se consideriamo z-x = z-y-x+y = pm+qm = (p+q)m abbiamo che m divide(z-x).
Quindi se nell'insieme degli interi è definita una relazione di equivalenza modulo n, avremo un insieme quoziente costituito da n classi di equivalenza, ovvero tante quanti sono i possibi resti della divisione per n (da n-1 a 0). Come rappresentante della classe di equivalenza si pone il più piccolo della classe, ma le operazioni non cambiano se si pone uno qualsiasi dei rappresentanti della classe di equivalenza
Si può dimostrare che se:
x ≡ y (mod n) e se z ≡ w (mod n), allora (x+z) ≡ (y+w) (mod n). Da ciò si ricava la regola: [x]n + [y]n = [x + y]n