Il teorema cinese del resto, enunciato nel III secolo a.C. dal matematico cinese Sun Zi (o, adottando un'altra grafia, Sun Tzu), permette di risolvere i sistemi di congruenze.
Dato un sistema di due o più congruenze
               x = b_1 (mod n_1)
               x = b_2 (mod n_2)
               ...
               x = b_s (mod n_s)
dove n_1, n_2, ... n_s sono interi a due a due coprimi e b_1, b_2, ... b_s sono interi, questo è risolubile e ha infinite soluzioni legate dalla relazione
               x_k = x_0 + Nk,
in cui N è il prodotto di tutti gli n_i.
 
Riporto la dimostrazione, commentandola.
Sia N_i il prodotto di tutti gli n_j, tali che j≠i; in tal modo N_i e n_i sono primi fra loro.
Al primo membro della i-esima congruenza presente nel sistema si sostituisca il prodotto N_i*x', di modo che si venga a determinare la seguente equazione
(1)          N_i * x' ≣ b_i (mod n_i) 
che ha sempre una soluzione x'_i (in virtù di quanto esposto nel quesito precedente, perché il coefficiente dell'incognita e il modulo sono coprimi).
Si può determinare il numero x_0 così definito
               x_0 = sommatoria_{i=1}^{s} N_i*x'_i ;
questo è soluzione del sistema di partenza; infatti, spezzando la sommatoria isolando N_i*x'_i, si ha
(2)          x_0 = N_i*x'_i + sommatoria_{j≠i} N_j*x'_j ;
N_i*x'_i è il primo membro dell'equazione (1), perché x'_i ne è soluzione; considerando che la sommatoria nella (2) è ininfluente ai fini del modulo nella (1), dacché N_j è diviso da n_i, per definizione di N_j (che è il prodotto di tutti gli n_i meno che di n_j), allora x_0 è soluzione del sistema di partenza, perché, in modulo, è congruo a N_i*x'_i, che, dalla sostituzione iniziale, è uguale a x.
Per trovare le altre soluzioni x_k, basta considerare che devono essere multiple di ogni n_i, e sono quindi legate alla soluzione appena determinata dalla congruenza
               x_k ≣ x_0 (mod N)
e quindi
               x_k = x_0 + Nk.
 
 
Se il sistema presenta due sole congruenze, la condizione per cui sia verificato è ricavabile da quella di risoluzione delle equazioni diofantee: la differenza dei resti deve essere multipla del massimo comune divisore dei moduli.
E ora l'esempio.
Il sistema è
               x ≣ 6 (mod 7)
               x ≣ 5 (mod 9)
Le due equazioni, applicando il metodo appena descritto e risolvendo con l'algoritmo di Euclide per le equazioni diofantee, diventano
               9x = 6 + 7y     →     x = - 18;   y = - 24
               7x = 5 + 9y     →     x = 20;     y = 15
Le soluzioni utili ai fini del sistema sono le x: considerando che la prima è modulo 7 e la seconda modulo 9, si possono scrivere
               x'_1 = 3;          x'_2 = 2
Si può ora calcolare x_0 secondo quanto appena esposto:
               x_0 = 9*3 + 7*2 = 41;
una breve verifica conferma che si tratta di una soluzione del sistema.
Le altre sono
               x_k = 41 + 63k.
 
Buonasera, 
Samuele :)