La congruenza modulo n

La congruenza modulo n è una classe di equivalenza definita sull'insieme Z tra due elementi a,b di Z $$ aρb \:\: (mod \: n) \Leftrightarrow a-b=k \cdot n, k \in Z $$

Esempio

Esempio 1

In questo caso a=10 congruo b=4 modulo n=2 equivale a dire che la differenza a-b è divisibile per n=2.

$$ a \equiv _n b $$

$$ 10 \equiv _2 4 \Leftrightarrow 10-4 = 6 = k \cdot n = 3 \cdot 2 $$

La differenza a-b=10-4 è uguale a 6.

Il modulo n=2 divide 6, quindi la congruenza modulo n è verificata.

Esempio 2

In quest'altro esempio a=7 congruo 4 modulo 2 equivale a dire che la differenza a-b è divisibile per n=2.

$$ a \equiv_n b $$

$$ 7 \equiv _2 4 \Leftrightarrow 7-4 = 3 = k \cdot n $$

In questo caso non c'è nessun numero intero k tale che kn=3

$$ k \cdot n = k \cdot 2 = 3 $$

La differenza a-b=7 non è divisibile per n=2.

Pertanto, non è una congruenza modulo n.