Dati $m >0$, $a,b \in \mathbb Z$, $ax \equiv b \space (mod \space m)$ è un’equazione congruenziale lineare
Dati $m>0$, $a,b \in \mathbb Z$, l’equazione $ax \equiv b \space (mod \space m)$ ha soluzione se $MCD(a,m)=1$
Tutte le possibili soluzioni sono gli elementi della classe di equivalenza $[s]_m = \{z \in \mathbb Z| az \equiv b \space (mod \space m) \}$
Dati $m>0$, $a,b \in \mathbb Z$, $t \in \mathbb Z$ tale che $t|a, t|b, t|m$
allora $ax \equiv b \space (mod \space m)$ ha soluzione $s \in \mathbb Z \Leftrightarrow \frac{a}{t}x \equiv \frac{b}{t} \space (mod \space \frac{m}{t})$
Osservazione: $s = \{z \in \mathbb Z|az \equiv b \space (mod \space m) = \{z \in \mathbb Z|\frac{a}{t}z \equiv \frac{b}{t} \}$
ma $s = [s]_\frac{m}{d} = [s]_m\cup [s+\frac{m}{d}]_m\cup[s+\frac{2m}{d}]_m\cup .. \cup [s+\frac{d-1}{d}m]_m$
Siano $m_1,..,m_k \in \mathbb N$ a due a due coprimi ($\forall i \neq j, MCD(m_i,m_j)=1$) e siano $b_1,..,b_k \in \mathbb Z$, allora il sistema
$\begin{cases} x \equiv b_1 \space (mod \space m_1) \\ .. \\ x \equiv b_k \space (mod \space m_k) \end{cases}$ ha soluzione $s$
L’insieme di tutte le soluzioni è $[s]_{m_1m_2..m_k}$
Generalizzazione: il sistema ha soluzione $\Leftrightarrow MCD(m_i,m_j)|b_i-b_j$ ($m_i \neq m_j$)