Enunciato

Sia $ax \equiv b \ ( \text{mod } m)$ una equazione congruenziale.

Indichiamo con d il MCD tra $a$ e $b$

Allora valgono le seguenti:

1. Sia $x_0$ una soluzione dell’equazione, allora vale che $\forall h \in \Z \ x_o +h \cdot \frac{m}{d}$ è soluzione dell’eqazione
2. Siano $x_0$ e $x_0^{’}$ soluzioni dell’equazione, allora $\exist l \in \Z:x^{'}_0=x_0+l \cdot \frac{m}{d}$
3. Siano $y_l = x_0 + l \cdot \frac{m}{d}$ , $l=[0,d-1]$. x_0 è soluzione dell’equazione, allora:

$$ y_0 = x_0 \quad y_1 = x_0 + \frac{m}{d}, \quad y_2 = x_0 + \frac{2m}{d}, \dots \quad y_{d-1} = x_0 + \frac{(d-1)m}{d} \qquad \forall i,j : 0 \le i < j \le d-1 \qquad y_i \neq y_j \quad (m) $$

1. In particolare se $d=1$ la soluzione si riduce a $y_0$

Dimostrazione

todo