Il sistema di congruenze lineari
Un sistema di congruenza lineari ammette una soluzione quando tutte le congruenze sono compatibili ed esiste almeno un numero intero x che soddisfa ogni singola congruenza lineare. $$ \begin{cases} a_1 x ≡ b_1 \mod n_1 \\ a_2 x ≡ b_2 \mod n_2 \\ \vdots \\ a_n x ≡ b_n \mod n_n \end{cases} $$
Una congruenza ax≡b mod n è detta compatibile quando il massimo comune divisore MCD(a,n) è un divisore di b.
Il sistema di congruenze lineari può ammettere una, più soluzioni oppure nessuna.
Nota. La compatibilità è una condizione necessaria ma non sufficiente per la risoluzione del sistema. Se una o più congruenze non sono compatibili il sistema non ha soluzioni. Tuttavia, se anche tutte le congruenze fossero compatibili, potrebbe non esistere un intero x che le soddisfi tutte.
Un esempio pratico
Ho il seguente sistema
$$ \begin{cases} 4x ≡ 2 \mod 6 \\ 3x ≡ 1 \mod 5 \end{cases} $$
Per prima cosa verifico se le congruenze lineari sono compatibili.
La congruenza 4x≡2 mod 6 è compatibile perché MCD(4,6)=2 è un divisore di 2.
$$ MCD(4,6)=2|2 $$
La congruenza 3x≡1 mod 5 è compatibile perché MCD(3,5)=1 è un divisore di 1.
$$ MCD(3,5)=1|1 $$
Nota. In questo esempio tutte le congruenze lineari sono compatibili e posso procedere nella ricerca delle soluzioni.
Dopo aver verificato la compatibilità, verifico se esiste una soluzione x comune a entrambe.
La prima soluzione della congruenza 4x≡2 mod 6 è x0=2
$$ 4x≡2 \mod 6 \\ 4(2)≡2 \mod 6 \\ 8≡2 \mod 6 \\ 2≡2 \mod 6 $$
Le soluzioni, considerando n=6 e d=mcd(4,6)=2 sono
$$ 2 \\ 2+\frac{6}{2} = 5 \\ 2+2\frac{6}{2} = 8 \\ \vdots $$
La prima soluzione della congruenza 3x=1 mod 5 è x0=2
$$ 3x≡1 \mod 5 \\ 3(2)≡1 \mod 5 \\ 6≡1 \mod 5 \\ 1≡1 \mod 5 $$
Le soluzioni, considerando n=5 e d=mcd(3,5)=1 sono
$$ 2 \\ 2+\frac{5}{1} = 7 \\ 2+2\frac{5}{1} = 12 \\ \vdots $$
Il numero intero x=2 soddisfa entrambe le congruenze lineari.
$$ \begin{cases} 4x ≡ 2 \mod 6 \\ 3x ≡ 1 \mod 5 \end{cases} $$
$$ \begin{cases} 4(2) ≡ 2 \mod 6 \\ 3(2) ≡ 1 \mod 5 \end{cases} $$
$$ \begin{cases} 8 ≡ 2 \mod 6 \\ 6 ≡ 1 \mod 5 \end{cases} $$
$$ \begin{cases} 2 ≡ 2 \mod 6 \\ 1 ≡ 1 \mod 5 \end{cases} $$
Quindi, una soluzione del sistema di congruenze lineari è x=2.
Il sistema di congruenze in forma equivalente
Se i moduli n del sistema di congruenze lineari compatibili sono interi coprimi tra loro $$ MCD(n_i, n_k) = 1 \:\:\: per \:\:\: i≠k $$ posso esprimere il sistema in questa forma equivalente. $$ \begin{cases} \frac{a_1}{d_1} x ≡ \frac{b_1}{d_1} \mod \frac{n_1}{d_1} \\ \frac{a_2}{d_2} x ≡ \frac{b_2}{d_2} \mod \frac{n_2}{d_2} \\ \vdots \\ \frac{a_n}{d_n} x ≡ \frac{b_n}{d_n} \mod \frac{n_n}{d_n} \end{cases} $$ dove di è il massimo comune divisore $$ d_i=MCD(a_i, n_i) $$
Qual è il vantaggio?
Questa forma equivalente è utile per cercare la soluzione del sistema tramite il teorema cinese dei resti.
Dimostrazione
In questa forma i valori ni/di sono coprimi con ai/di ossia il massimo comune divisore è uguale a uno.
$$ MCD( \frac{a_i}{d_i} , \frac{n_i}{d_i} ) = 1 $$
Il numero 1 è anche un divisore di b/d.
$$ MCD( \frac{a_i}{d_i} , \frac{n_i}{d_i} ) | \frac{b_i}{d_i} $$
Pertanto, dopo questa trasformazione ogni congruenza lineare del sistema ammette una soluzione intera si.
Nota. La congruenza ax=b mod n ammette soluzioni ( ossia è compatibile) soltanto se il massimo comune divisore MCD(a,n) è un divisore di b.
Quindi, il sistema di congruenze lineari ammette una soluzione soltanto se esiste un valore x tale che
$$ \begin{cases} x ≡ s_1 \mod \frac{n_1}{d_1} \\ x ≡ s_2 \mod \frac{n_2}{d_2} \\ \vdots \\ x ≡ s_n \mod \frac{n_n}{d_n} \end{cases} $$
E così via.
