Sistema di congruenze equivalente
Un sistema di congruenze lineari equivalente è un sistema con le stesse soluzioni di un altro.
Un sistema di congruenze lineari
$$ \begin{cases} a_1 x \equiv b_1 \:\: ( mod \: n_1) \\ a_2 x \equiv b_2 \:\: ( mod \: n_2) \\ \vdots \\ a_n x \equiv b_n \:\: ( mod \: n_n) \end{cases} $$
Il sistema di congruenze lineari equivalente
$$ \begin{cases} x \equiv c_1 \:\: ( mod \: n_1') \\ x \equiv c_2 \:\: ( mod \: n_2') \\ \vdots \\ x \equiv c_n \:\: ( mod \: n_n') \end{cases} $$
A cosa serve?
Il sistema equivalente ha le stesse soluzioni del sistema originale ma è più semplice da risolvere.
Come calcolare il sistema equivalente
- Un sistema di congruenze lineari può essere trasformato in un sistema equivalente se e solo se
- Tutte le congruenze sono compatibili ossia ammettono soluzioni $$ MCD(a,n)|b $$
- Tutti i moduli (n) del sistema sono coprimi a coppia. $$ MCD(n_i,n_j)=1 $$
Se il sistema di congruenze lineari soddisfa le precedenti condizioni, posso calcolare il sistema in forma equivalente dividendo ogni congruenza lineare ax≡b (mod n) per il corrispettivo massimo comune divisore MCD(a,n)
$$ \begin{cases} \frac{ a_1 x \equiv b_1 \:\: ( mod \: n_1) }{MCD(a_1,n_1)} \\ \frac{ a_2 x \equiv b_2 \:\: ( mod \: n_2) }{MCD(a_2,n_2)} \\ \vdots \\ \frac{a_n x \equiv b_n \:\: ( mod \: n_n) }{MCD(a_n,n_n)} \end{cases} $$
Il sistema equivalente ha la caratteristica d'avere un'unica soluzione per ogni congruenza.
Nota. Il massimo comune divisore MCD(a,n) è uguale a 1 in ogni congruenza lineare. Inoltre, il massimo comune divisore MCD(ni,nj) dei moduli presi a coppia è sempre uguale a 1.
Un esempio pratico
Ho un sistema composto da due congruenze lineari
$$ \begin{cases} 4 x \equiv 8 \:\: ( mod \: 10) \\ 6 x \equiv 3 \:\: ( mod \: 9) \end{cases} $$
Entrambe le congruenze sono compatibili perché ammettono soluzioni
$$ MCD(a_1, n_1)=MCD(4,10)=2 | 8 \\ MCD(a_2, n_2)=MCD(6,9)=3 | 3 $$
Quindi, la prima congruenza lineare ha 2 soluzioni mentre la seconda ha 3 soluzioni.
Nota. Una congruenza ax≡b (mod n) ha soluzioni se il MCD(a,n) divide b. In tale caso, il numero delle soluzioni è uguale al MCD(a,n).
Ci sono anche le condizioni per trasformarlo in un sistema equivalente, perché i due moduli sono coprimi tra loro.
$$ MCD(n_1,n_2)=MCD(10,9)=1 $$
A questo punto, divido ogni congruenza per il corrispettivo massimo comune divisore MCD(a,n).
$$ \begin{cases} \frac{4}{2} x \equiv \frac{8}{2} \:\: ( mod \: \frac{10}{2}) \\ \frac{6}{3} x \equiv \frac{3}{3} \:\: ( mod \: \frac{9}{3}) \end{cases} $$
$$ \begin{cases} 2 x \equiv 4 \:\: ( mod \: 5) \\ 2 x \equiv 1 \:\: ( mod \: 3) \end{cases} $$
In questa forma equivalente le congruenze hanno un'unica soluzione ciascuna
$$ MCD(a_1, n_1)=MCD(2,5)=1 \\ MCD(a_2, n_2)=MCD(2,3)=1 $$
E' una proprietà molto utile perché mi permette di sostituire ogni congruenza con la sua soluzione
$$ \begin{cases} x \equiv 2 \:\: ( mod \: 5) \\ x \equiv 2 \:\: ( mod \: 3) \end{cases} $$
Ho calcolato il sistema di congruenze lineari in forma equivalente.
Nota. Le soluzioni del sistema equivalente sono le stesse del sistema originale. Sono però più facili da calcolare. $$ \begin{cases} 4 x \equiv 8 \:\: ( mod \: 10) \\ 6 x \equiv 3 \:\: ( mod \: 9) \end{cases} $$ $$ \begin{cases} 4 (2) \equiv 8 \:\: ( mod \: 10) \\ 6 (2) \equiv 3 \:\: ( mod \: 9) \end{cases} $$ $$ \begin{cases} 8 \equiv 8 \:\: ( mod \: 10) \\ 3 \equiv 3 \:\: ( mod \: 9) \end{cases} $$
E così via.
