Teorema sisa Tiongkok

Teorema sisa Tiongkok adalah hasil dari aljabar abstrak dan teori bilangan.

Rumusan asli Sunzi: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) dengan solusi x = 23 + 105k, dengan k adalah bilangan bulat

Kongruensi Simultan dari bilangan bulat

Bentuk asli dari teorema ini, seperti terdapat dalam buku yang ditulis oleh ahli matematika dari Tiongkok Qin Jiushao dan diterbitkan pada tahun 1247, adalah suatu pernyataan tentang kongruensi simultan (lihat aritmetika modular). Misalkan n₁, ..., n_k adalah bilangan bulat positif yang setiap pasangnya adalah koprima (yang artinya FPB (n_i, n_j) = 1 untuk setiap i ≠ j). Maka, untuk setiap bilangan bulat a₁, ..., a_k, selalu ada bilangan bulat x yang merupakan penyelesaian dari sistem kongruensi simultan

$x\equiv a_{i}{\pmod {n_{i}}}\quad \mathrm {for} \;i=1,\cdots ,k$

Pseudocode "subtitle":

x_solves_it=true;
for(i= 1; i <= k; i++)
   if(x % n[i] != a[i] % n[i])
      x_solves_it=false;

Terlebih lagi, semua penyelesaian x dari sistem ini adalah juga kongruen modulo dari perkalian n = n₁...n_k.

Suatu penyelesaian x dapat ditemukan dengan cara sebagai berikut. Untuk setiap i, bilangan bulat n_i dan n/n_i adalah koprima, dan menggunakan ekstensi algoritme Euklidean kita dapat menemukan bilangan bulat r dan s sehingga r n_i + s n/n_i = 1. Jika kita menentukan e_i = s n/n_i, maka kita dapat

$e_{i}\equiv 1{\pmod {n_{i}}}\quad \mathrm {and} \quad e_{i}\equiv 0{\pmod {n_{j}}}$

untuk j ≠ i.

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++)
    if (j != i)
      assert( e[i] % n[i] == 1 && e[i] % n[j] == 0 );

Penyelesaian dari sistem kongruensi simultan ini adalah

$x=\sum _{i=1..k}a_{i}e_{i}\$

for(i= 1; i <= k; i++)
  x += a[i] * e[i];

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

$x\equiv 2{\pmod {3}}$

$x\equiv 3{\pmod {4}}$

$x\equiv 2{\pmod {5}}$

 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 e₁ = 40 (e[1] == 40). Menggunakan algoritme Euklidean untuk 4 dan 3×5 = 15, kita memperoleh (-11) × 4 + 3 × 15 = 1. Oleh karena itu, e₂ = 45 (e[2] == 45). Akhirnya, menggunakan algoritme Euklidean untuk 5 dan 3×4 = 12, kita memperoleh 5 × 5 + (-2) × 12 = 1, yang berarti e₃ = -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 n_i (n[i]) setiap pasangnya tidak selalu koprima. Syarat-syarat yang lebih tepat adalah sebagai berikut: sistem mempunyai penyelesaian x jika dan hanya jika a_i ≡ a_j (mod fpb(n_i, n_j)) (a[i] == a[j] % gcd(n[i], n[j])) untuk semua i dan j. Semua penyelesaian x adalah kongruen modulo kelipatan persekutuan terkecil dari n_i (n[i]).

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

Pranala luar

• Chinese remainder theorem