Congruența modulo n

Congruența modulo n este o relație de echivalență definită pe mulțimea numerelor întregi ℤ. Două numere întregi a și b se consideră congruente modulo n dacă diferența lor este un multiplu al lui n: $$ a\rho b \:\: (mod \: n) \Leftrightarrow a - b = k \cdot n,\ \text{unde } k \in \mathbb{Z} $$

Exemplu

Exemplul 1

Fie a = 10 și b = 4. A afirma că a este congruent cu b modulo n = 2 înseamnă că diferența a - b trebuie să fie divizibilă cu 2:

$$ a \equiv_n b $$

$$ 10 \equiv_2 4 \Leftrightarrow 10 - 4 = 6 = 3 \cdot 2 $$

Deoarece diferența a - b = 6 este un multiplu al lui 2, congruența este îndeplinită.

Exemplul 2

Să luăm acum a = 7 și b = 4. Verificăm dacă 7 este congruent cu 4 modulo 2:

$$ a \equiv_n b $$

$$ 7 \equiv_2 4 \Leftrightarrow 7 - 4 = 3 = k \cdot 2 $$

Însă nu există niciun număr întreg k pentru care \( k \cdot 2 = 3 \), deci diferența nu este divizibilă cu 2.

În concluzie, 7 nu este congruent cu 4 modulo 2, iar congruența nu este validă.