Il teorema cinese dei resti (esempio di calcolo)
Un sistema di congruenze lineari nella forma $$ \begin{cases} x ≡ r_1 \mod n_1 \\ x ≡ r_2 \mod n_2 \\ \vdots \\ x ≡ r_n \mod n_n \end{cases} $$ se per ogni i≠j $$ MCD(n_i,n_j)=1 $$ ammette un'unica soluzione x modulo N=n1·n2···nn $$ x = \frac{N}{n_1} x_1 +\frac{N}{n_2} x_2 +...+\frac{N}{n_n} x_n \mod N $$ dove x1, x2, x3 sono le soluzioni del sistema $$ \begin{cases} x ≡ x_1 \frac{N}{n_1} \mod n_1 \\ x ≡ x_2 \frac{N}{n_2} \mod n_2 \\ \vdots \\ x ≡ x_n \frac{N}{n_n} \mod n_n \end{cases} $$
Detto in altri termini, se i moduli delle congruenze lineari del sistema sono coppie di interi coprimi, esiste una soluzione x del sistema ed è unica.
Attenzione. Il teorema cinese dei resti trova la soluzione del sistema del sistema di congruenze lineari soltanto se i moduli sono coprimi tra loro. Se i moduli non sono coprimi, la soluzione va cercata con altri metodi.
Un esempio pratico
Ho il seguente sistema di congruenze lineari
$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$
I moduli sono coprimi tra loro.
$$ MCD(4.3) = 1 \\ MCD(4.5) = 1 \\ MCD(3.5) = 1 $$
Quindi, posso applicare il teorema dei resti cinese.
Trasformo il sistema nella forma del sistema equivalente
$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ x ≡ 2 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$
- Spiegazione
- Nella prima congruenza x=3 mi permette di soddisfare la congruenza x ≡ 3 mod 4 ossia 3 ≡ 3 mod 4
- Nella seconda congruenza x=2 mi permette di soddisfare la congruenza 2x ≡ 1 mod 3 ossia 2(2) ≡ 1 mod 3 che diventa 4 ≡ 1 mod 3 equivalente a 1 ≡ 1 mod 3
- Nella terza congruenza x=4 mi permette di soddisfare la congruenza x ≡ 4 mod 5 ossia 4 ≡ 4 mod 4
A questo punto calcolo il prodotto dei moduli
$$ N = n_1 \cdot n_2 \cdot n_3 = 4 \cdot 3 \cdot 5 = 60 $$
Sostituisco l'incognita x con la corrispondente espressione (N/ni)xi
$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ x ≡ 2 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} \frac{N}{n_1} x_1 ≡ 3 \mod 4 \\ \frac{N}{n_2} x_2 ≡ 2 \mod 3 \\ \frac{N}{n_3} x_3 ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} \frac{60}{4} x_1 ≡ 3 \mod 4 \\ \frac{60}{3} x_2 ≡ 2 \mod 3 \\ \frac{60}{5} x_3 ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} 15 x_1 ≡ 3 \mod 4 \\ 20 x_2 ≡ 2 \mod 3 \\ 12 x_3 ≡ 4 \mod 5 \end{pmatrix} $$
Semplifico le congruenze lineari
$$ \begin{pmatrix} 3 x_1 ≡ 3 \mod 4 \\ 2 x_2 ≡ 2 \mod 3 \\ 2 x_3 ≡ 4 \mod 5 \end{pmatrix} $$
Spiegazione. Il resto di 15 diviso 4 è 3. Il resto di 20 diviso 3 è 2. Il resto di 12 diviso 5 è 2.
Le soluzioni sono x1=1, x2=1, x3=2.
$$ \begin{pmatrix} 3 x_1 ≡ 3 \mod 4 \\ 2 x_2 ≡ 2 \mod 3 \\ 2 x_3 ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} 3 (1) ≡ 3 \mod 4 \\ 2 (1) ≡ 2 \mod 3 \\ 2 (2) ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} 3 ≡ 3 \mod 4 \\ 2 ≡ 2 \mod 3 \\ 4 ≡ 4 \mod 5 \end{pmatrix} $$
A questo punto posso trovare la soluzione unica dell'intero sistema di congruenze lineari usando la formula
$$ x = \frac{N}{n_1} x_1 + \frac{N}{n_2} x_2 + \frac{N}{n_3} x_3 $$
$$ x = \frac{60}{4} x_1 + \frac{60}{3} x_2 + \frac{60}{5} x_3 $$
$$ x = 15 x_1 + 20 x_2 + 12 x_3 $$
$$ x = 15 (1) + 20 (1) + 12 (2) $$
$$ x = 59 $$
E' la soluzione (x=59) del sistema di congruenze lineari.
Verifica. $$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$ $$ \begin{pmatrix} 59 ≡ 3 \mod 4 \\ 2(59) ≡ 1 \mod 3 \\ 59 ≡ 4 \mod 5 \end{pmatrix} $$ $$ \begin{pmatrix} 3 ≡ 3 \mod 4 \\ 1 ≡ 1 \mod 3 \\ 4 ≡ 4 \mod 5 \end{pmatrix} $$ La soluzione soddisfa tutte le congruenze lineari del sistema.
E così via.
