Relazione $m\mathbb Z$

$m\mathbb Z \subseteq \mathbb Z \times \mathbb Z$ è la relazione definita da:

$a \space m\mathbb Z \space b \Leftrightarrow \exist k \in \mathbb Z: a-b = mk \Leftrightarrow m|a-b \Leftrightarrow \exist k \in \mathbb Z : a = b+ mk$

Proposizione: $m\mathbb Z$ è una relazione d’equivalenza compatibile con le operazioni $+$ e $\cdot$, cioè $\forall a,b,c,d \in \mathbb Z$ se $a \space m\mathbb Z \space c$ e $b \space m \mathbb Z \space d$, allora $a+b \space m\mathbb Z \space c+d$ e $ab \space m\mathbb Z \space cd$

Congruenza

$m\mathbb Z$ è una congruenza (relazione d’equivalenza compatibile con le operazioni di $\mathbb Z$) ed è detta congruenza modulo $m$

L’insieme quoziente $\mathbb Z \backslash m\mathbb Z$ si indica con $\mathbb Z_m$ ed è detto insieme degli interi modulo m

Indichiamo gli elementi di $\mathbb Z_m$ con $[x]_m$ oppure $\overline{x}$

Proposizione

Dati $m,x \in \mathbb Z$ si ha $[x]_m= \{x+km|k \in \mathbb Z\}$ e, se $m \neq 0$, $[x]_m = [rest(x,n)]_m$

Teorema

Sia $m >0$, $\mathbb Z_m = \{ [0]_m, [1]_m,..,[m-1]_m\}$ e $|\mathbb Z_m| = m$

Lemma

Dati $a,b,m \in \mathbb Z$, si ha:

• $a \equiv b \space (mod \space m) \Leftrightarrow \forall t \in \mathbb Z, a+t \equiv b+t \space (mod \space m)$
• $a \equiv b \space (mod \space m) \Rightarrow \forall t \in \mathbb Z, at \equiv bt \space (mod \space m)$
• $at \equiv bt \space (mod \space m) \Rightarrow a \equiv b \space (mod \space m)$ se $MCD(t,m)=1$

Lemma