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

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