Teorema sisa Tiongkok

Dalam matematika, teorema sisa Tiongkok menyatakan bahwa jika diketahui sisa pembagian suatu bilangan bulat  oleh beberapa bilangan bulat, maka dapat diketahui sisa pembagian  oleh darab dari bilangan-bilangan bulat tersebut, dengan syarat bahwa setiap pasang pembaginya saling prima (atau dengan kata lain, tidak ada dua pembagi yang memiliki faktor persekutuan selain 1 maupun -1).

Teorema ini juga dikenal sebagai teorema Sunzi. Kedua nama dari teorema ini merujuk kepada pernyataan yang pertama kali muncul dalam Sunzi Suanjing, sebuah manuskrip Tiongkok yang ditulis pada abad ke-3 hingga abad ke-5 Masehi. Pernyataan pertama ini terbatas pada contoh berikut:

Jika diketahui
 sisa pembagian dari  ketika dibagi oleh  ialah ,
 sisa pembagian dari  ketika dibagi oleh  ialah , dan
 sisa pembagian dari  ketika dibagi oleh  ialah 
maka dapat ditentukan sisa pembagian dari  ketika dibagi oleh  (darab dari , , dan ) tanpa mengetahui nilai . Dalam contoh ini, sisa pembagiannya ialah . Lebih lanjut, sisa pembagian ini merupakan satu-satunya nilai positif  yang kurang dari .

Teorema sisa Tiongkok banyak digunakan untuk perhitungan bilangan bulat yang besar, sebab teorema ini memungkinkan untuk mengganti perhitungan yang diketahui batas dari ukuran hasilnya dengan beberapa perhitungan serupa pada bilangan-bilangan bulat yang kecil.

Teorema sisa Tiongkok (saat diekspresikan menggunakan kekongruenan) juga berlaku pada setiap daerah ideal utama. Teorema ini telah diperumum untuk sembarang gelanggang, dengan perumusan yang melibatkan ideal dua sisi.

 Sejarah 
Pernyataan dari masalah ini muncul pertama kali dalam buku abad ke-5 Sunzi Suanjing karya matematikawan Tiongkok Sunzi.

Hasil Sunzi tidak akan dianggap sebagai teorema menurut standar modern, sebab Sunzi hanya memberikan satu masalah spesifik tanpa menunjukkan cara menyelesaikannya maupun bukti dari kasus umum atau algoritma umum untuk menyelesaikan masalah tersebut. Algoritma pertama untuk menyelesaikan masalah ini pertama kali dideskripsikan oleh Aryaphata (abad ke-6). Kasus khusus dari teorema sisa Tiongkok juga diketahui oleh Brahmagupta (abad ke-7) dan muncul pada karya Fibonacci tahun 1202, Liber Abaci. Hasil tersebut kemudian diperumum menjadi solusi utuh yang disebut Da-yan-shu () dalam karya Qin Jiushao tahun 1247, Risalah Matematika dalam Sembilan Bab yang kemudian diterjemahkan ke dalam bahasa Inggris pada awal abad ke-19 oleh misionaris asal Britania Raya, Alexander Wylie.

Gagasan mengenai kekongruenan pertama kali diperkenalkan dan digunakan oleh Carl Friedrich Gauss dalam karya tahun 1801 miliknya, Disquisitiones Arithmeticae.

 Isi pernyataan 

 Selang terbatas 

 Sistem kekongruenan simultan 

Teorema sisa Tiongkok juga dapat dinyatakan dengan menggunakan kekongruenan

 Isomorfisma gelanggang 

Berdasarkan sudut pandang ini, maka untuk melakukan serangkaian operasi aritmetika pada , teorema sisa Tiongkok memungkinkan untuk melakukan perhitungan serupa pada masing-masing  lalu memperoleh hasil akhirnya dengan menerapkan isomorfismanya (dari kanan ke kiri). Proses ini mungkin saja jauh lebih cepat dibandingkan perhitungan langsung, jika nilai  dan banyaknya operasi cukup besar.

 Bukti 
Kewujudan dan ketunggalan penyelesaian dapat dibuktikan secara terpisah. Akan tetapi, bukti pertama dari aspek kewujudan penyelesaian (lihat di bawah) akan memanfaatkan informasi ketunggalan penyelesaian.

 Ketunggalan 
Misalkan  dan  merupakan penyelesaian dari sistem kekongruenan linier yang diberikan. Oleh karena  dan  memiliki sisa pembagian yang sama ketika dibagi oleh , maka selisih antar keduanya (yaitu ) merupakan kelipatan dari , untuk sembarang . Diketahui bahwa  koprima dengan  untuk setiap , maka  juga merupakan faktor dari , sehingga  dan  akan kongruen dalam modulo . Jika  dan  bernilai nonnegatif dan kurang dari  (seperti pada isi pernyataan pertama), maka  haruslah bernilai .

 Kewujudan (bukti pertama) 
Perhatikan bahwa pemetaan

memetakan kelas-kelas kekongruenan modulo  ke barisan kelas-kelas kekongruenan modulo . Bukti ketunggalan menunjukkan bahwa pemetaan tersebut bersifat injektif. Oleh karena domain dari pemetaan tersebut memiliki kardinalitas yang sama dengan kodomainnya, maka pemetaan tersebut juga bersifat surjektif, sehingga penyelesaiannya terjamin ada.

Pembuktian ini cukup sederhana, tetapi tidak menyediakan metode atau cara untuk mencari penyelesaiannya. Selain itu, pembuktian ini tidak dapat diperumum ke situasi lain, berbeda dengan kedua bukti berikut.

 Kewujudan (bukti kedua) 
Kewujudan penyelesaian dari sistem kongruensinya dapat dilakukan dengan konstruksi bilangan  secara eksplisit. Konstruksi ini melibatkan dua langkah berbeda, yaitu penyelesaian untuk kasus dua moduli, kemudian memperumum penyelesaian tersebut untuk sembarang  moduli menggunakan induksi matematika.

Diberikan sistem kekongruenan linier

dengan  koprima dengan . Berdasarkan identitas Bézout, maka terdapat bilangan bulat  dan  sedemikian sehingga

Nilai dari  dan  dapat dicari dengan menggunakan algoritma Euclid diperluas.

Pandang bilangan

Perhatikan bahwa

yang menunjukkan bahwa  merupakan penyelesaian dari sistem yang diberikan.

Sekarang tinjau sistem kekongruenan linier

dengan  untuk setiap . Telah ditunjukkan sebelumnya bahwa dua kekongruenan pertama memiliki suatu penyelesaian, yaitu . Himpunan penyelesaian dari dua kekongruenan pertama ini ialah himpunan semua bilangan bulat  yang memenuhi

Oleh karena  koprima dengan setiap  lainnya, maka sistem kekongruenannya tereduksi menjadi  kekongruenan simultan, yaitu

Penyelesaian sistemnya akan diperoleh dengan melakukan iterasi serupa yang berulang sebanyak  kali.

 Kewujudan (bukti ketiga) 
Untuk mengonstruksikan penyelesaian, induksi pada banyaknya moduli tidaklah diperlukan. Namun, konstruksi langsung semacam ini akan melibatkan perhitungan yang lebih rumit dengan bilangan besar, yang membuat metode ini kurang efisien serta jarang digunakan. Walaupun demikian, interpolasi Lagrange merupakan kasus khusus dari konstruksi ini, yang diterapkan pada polinomial alih-alih bilangan bulat.

Misalkan  menyatakan darab dari semua moduli selain . Oleh karena setiap  koprima pasang demi pasang, maka  akan koprima dengan . Berdasarkan identitas Bézout, maka terdapat suatu bilangan bulat  dan  sedemikian sehingga

Pandang bilangan

Jika , maka berdasarkan definisi dari , perhatikan bahwa  merupakan kelipatan dari . Akibatnya,

untuk setiap , sehingga  merupakan penyelesaian dari sistem yang diberikan.

 Lihat juga 
 Sistem pelingkup
 Prinsip Hasse
 Sistem bilangan residu

 Catatan 

 Referensi 


 . Lihat Bagian 2.5, "Sifat Helly", hlm. 393–394.












 Bacaan lanjutan 
 . Lihat Bagian 31.5: Teorema sisa Tiongkok, hlm. 873–876.


 . Lihat Bagian 4.3.2 (hlm. 286–291), latihan 4.6.2–3 (halaman 456).

 Pranala luar 



  Full text of the Sun-tzu Suan-ching (Chinese) Chinese Text Project
  Teorema sisa Tiongkok di Cut-the-Knot.

Kategori:Artikel yang memuat pembuktian
Kategori:Penemuan matematika Tiongkok
Kategori:Aljabar komutatif
Kategori:Aritmetika modular
Kategori:Teorema dalam teori bilangan