Jelaskan untuk j ≠ i. dari Teorema sisa Tiongkok

for (i= 1; i <= k; i++)

{r, s}= ExtendedEuclid( n[i], n / n[i] );

e[i]= s * n / n[i];

for(j= 1; j <= k; j++)

assert( e[i] % n[i] == 1 && e[i] % n[j] == 0 );

Penyelesaian dari sistem kongruensi simultan ini adalah

for(i= 1; i <= k; i++)

x += a[i] * e[i];

Sebagai contoh, misalkan kita ingin menemukan suatu bilangan bulat x sehingga

x % 3 == 2 % 3 &&

x % 4 == 3 % 4 &&

x % 5 == 2 % 5

Menggunakan ekstensi algoritme Euklidean untuk 3 dan 4×5 = 20, kita memperoleh (-13) × 3 + 2 × 20 = 1, di mana e1 = 40 (e[1] == 40). Menggunakan algoritme Euklidean untuk 4 dan 3×5 = 15, kita memperoleh (-11) × 4 + 3 × 15 = 1. Oleh karena itu, e2 = 45 (e[2] == 45). Akhirnya, menggunakan algoritme Euklidean untukr 5 dan 3×4 = 12, kita memperoleh 5 × 5 + (-2) × 12 = 1, yang berarti e3 = -24 (e[3] == -24). Jadi, penyelesaian x adalah 2 × 40 + 3 × 45 + 2 × (-24) = 167. Semua penyelesaian yang lain adalah kongruen 167 modulo 60, yang berarti bahwa mereka semua kongruen 47 modulo 60.

Kadang kala, sistem kongruensi simultan dapat diselesaikan sekalipun ni (n[i]) setiap pasangnya tidak selalu koprima. Syarat-syarat yang lebih tepat adalah sebagai berikut: sistem mempunyai penyelesaian x jika dan hanya jika ai ≡ aj (mod fpb(ni, nj)) (a[i] == a[j] % gcd(n[i], n[j])) untuk semua i dan j. Semua penyelesaian x adalah kongruen modulo kelipatan persekutuan terkecil dari ni (n[i]).

Dengan menggunakan metode substitusi, kita sering kali bisa menemukan penyelesaian dari sistem kongruensi simultan, sekalipun setiap pasang modulusnya tidak selalu koprima.