Congruenza

DEFINIZIONE

Sia n un intero dato. Scriviamo a ≡ b mod n se abbiamo che n | (a - b).

La relazione ora definita si chiama congruenza modulo n, n si dice modulo della relazione, e a ≡ b mod n si legge «a è congruo a b modulo n».

La relazione di congruenza gode delle seguenti proprietà fondamentali:

LEMMA

1. La relazione di congruenza modulo n definisce una relazione di equivalenza sull'insieme degli interi.
2. Questa relazione di equivalenza ha n distinte classi di equivalenza.
3. Se a ≡ b mod n e c ≡ d mod n, allora si ha a + c ≡ b + d mod n e ac ≡ bd mod n.
4. Se ab ≡ ac mod n e a è relativamente primo con n, allora b ≡ c mod n.

Dim. Verifichiamo dapprima che la relazione di congruenza modulo n è una relazione di equivalenza. Poiché n | 0, abbiamo che n | (a - a) da cui a ≡ a mod n per ogni a. Inoltre, se a ≡ b mod n allora n | (a - b), e dunque n | (b - a) = - (a - b); dunque b ≡ a mod n. Infine, se a ≡ b mod n e b ≡ c mod n, allora n | (a - b) e n | (b - c), e quindi è n | ((a - b) + (b - c)), cioè n | (a - c), e ciò vuol dire che a ≡ c mod n.

Denotiamo con [a] la classe di equivalenza di a in questa relazione; la chiamiamo classe di congruenza (mod n) di a. Dato un intero a, per l'algoritmo euclideo a = kn + r, con 0 ≤ r < n. Allora a ∈ [r] e dunque [a] = [r]. Vi sono così al più n classi di congruenza distinte e cioè [0], [1], ..., [n - 1], e queste sono effettivamente distinte poiché se [i] = [j] con 0 ≤ i < j < n, allora n | (j - i) dove j - i è un intero positivo minore di n, cosa impossibile. Di conseguenza vi sono precisamente n classi di equivalenza distinte [0], [1], ..., [n - 1]. Abbiamo così dimostrato i punti 1) e 2) del lemma.