Dalam matematika, teorema sisa Tiongkok menyatakan bahwa jika diketahui sisa pembagian suatu bilangan bulat ${\displaystyle n}$ oleh beberapa bilangan bulat, maka dapat diketahui sisa pembagian ${\displaystyle n}$ 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).^[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

1. sisa pembagian dari ${\displaystyle n}$ ketika dibagi oleh ${\displaystyle 3}$ ialah ${\displaystyle 2}$,
2. sisa pembagian dari ${\displaystyle n}$ ketika dibagi oleh ${\displaystyle 5}$ ialah ${\displaystyle 3}$, dan
3. sisa pembagian dari ${\displaystyle n}$ ketika dibagi oleh ${\displaystyle 7}$ ialah ${\displaystyle 2}$

maka dapat ditentukan sisa pembagian dari ${\displaystyle n}$ ketika dibagi oleh ${\displaystyle 105}$ (darab dari ${\displaystyle 3}$, ${\displaystyle 5}$, dan ${\displaystyle 7}$) tanpa mengetahui nilai ${\displaystyle n}$. Dalam contoh ini, sisa pembagiannya ialah ${\displaystyle 23}$. Lebih lanjut, sisa pembagian ini merupakan satu-satunya nilai positif ${\displaystyle n}$ yang kurang dari ${\displaystyle 105}$.

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.

Pernyataan dari masalah ini muncul pertama kali dalam buku abad ke-5 Sunzi Suanjing karya matematikawan Tiongkok Sunzi.^[3]

Ada beberapa benda yang jumlahnya tidak diketahui. Jika dihitung dengan kelipatan tiga, tersisa dua; dengan kelipatan lima, tersisa tiga; dan dengan kelipatan tujuh, tersisa dua. Berapa banyak benda tersebut?^[4]

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.^[5] Algoritma pertama untuk menyelesaikan masalah ini pertama kali dideskripsikan oleh Aryaphata (abad ke-6).^[6] Kasus khusus dari teorema sisa Tiongkok juga diketahui oleh Brahmagupta (abad ke-7) dan muncul pada karya Fibonacci tahun 1202, Liber Abaci.^[7] Hasil tersebut kemudian diperumum menjadi solusi utuh yang disebut Da-yan-shu (大衍術code: zh is deprecated ) dalam karya Qin Jiushao tahun 1247, Risalah Matematika dalam Sembilan Bab^[8] yang kemudian diterjemahkan ke dalam bahasa Inggris pada awal abad ke-19 oleh misionaris asal Britania Raya, Alexander Wylie.^[9]

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

Teorema sisa Tiongkok juga dapat dinyatakan dengan menggunakan kekongruenan

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

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

Misalkan ${\displaystyle x}$ dan ${\displaystyle y}$ merupakan penyelesaian dari sistem kekongruenan linier yang diberikan. Oleh karena ${\displaystyle x}$ dan ${\displaystyle y}$ memiliki sisa pembagian yang sama ketika dibagi oleh ${\displaystyle n_{i}}$, maka selisih antar keduanya (yaitu ${\displaystyle x-y}$) merupakan kelipatan dari ${\displaystyle n_{i}}$, untuk sembarang ${\displaystyle i\in \left\{1,\,2,\,3,\,\ldots ,\,k\right\}}$. Diketahui bahwa ${\displaystyle n_{i}}$ koprima dengan ${\displaystyle n_{j}}$ untuk setiap ${\displaystyle 1\leq i<j\leq k}$, maka ${\displaystyle N}$ juga merupakan faktor dari ${\displaystyle x-y}$, sehingga ${\displaystyle x}$ dan ${\displaystyle y}$ akan kongruen dalam modulo ${\displaystyle N}$. Jika ${\displaystyle x}$ dan ${\displaystyle y}$ bernilai nonnegatif dan kurang dari ${\displaystyle N}$ (seperti pada isi pernyataan pertama), maka ${\displaystyle x-y}$ haruslah bernilai ${\displaystyle 0}$.

Perhatikan bahwa pemetaan $${\displaystyle f(x{\bmod {N}})=\left(x{\bmod {n}}_{1},\,x{\bmod {n}}_{2},\,x{\bmod {n}}_{3},\,\ldots ,\,x{\bmod {n}}_{k}\right)}$$ memetakan kelas-kelas kekongruenan modulo ${\displaystyle N}$ ke barisan kelas-kelas kekongruenan modulo ${\displaystyle n_{i}}$. 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 penyelesaian dari sistem kongruensinya dapat dilakukan dengan konstruksi bilangan ${\displaystyle x}$ secara eksplisit.^[13] Konstruksi ini melibatkan dua langkah berbeda, yaitu penyelesaian untuk kasus dua moduli, kemudian memperumum penyelesaian tersebut untuk sembarang ${\displaystyle k}$ moduli menggunakan induksi matematika.

Diberikan sistem kekongruenan linier $${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\end{aligned}}}$$ dengan ${\displaystyle n_{1}}$ koprima dengan ${\displaystyle n_{2}}$. Berdasarkan identitas Bézout, maka terdapat bilangan bulat ${\displaystyle p}$ dan ${\displaystyle q}$ sedemikian sehingga $${\displaystyle pn_{1}+qn_{2}=1}$$ Nilai dari ${\displaystyle p}$ dan ${\displaystyle q}$ dapat dicari dengan menggunakan algoritma Euclid diperluas.

Pandang bilangan

$${\displaystyle x=a_{1}qn_{2}+a_{2}pn_{1}}$$

Perhatikan bahwa $${\displaystyle {\begin{aligned}x&=a_{1}(qn_{2})+a_{2}pn_{1}\\&=a_{1}\left(1-pn_{1}\right)+a_{2}pn_{1}\\&=a_{1}+\left(a_{2}-a_{1}\right)pn_{1}\\x&\equiv a_{1}{\pmod {n_{1}}}\\\\x&=a_{1}qn_{2}+a_{2}(pn_{1})\\&=a_{1}qn_{2}+a_{2}\left(1-qn_{2}\right)\\&=a_{2}+\left(a_{1}-a_{2}\right)qn_{2}\\x&\equiv a_{2}{\pmod {n_{2}}}\end{aligned}}}$$ yang menunjukkan bahwa ${\displaystyle x}$ merupakan penyelesaian dari sistem yang diberikan.

Sekarang tinjau sistem kekongruenan linier $${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\x&\equiv a_{3}{\pmod {n_{3}}}\\&\ldots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$$ dengan ${\displaystyle \operatorname {FPB} (a_{i},\,a_{j})=1}$ untuk setiap ${\displaystyle 1\leq i<j\leq k}$. Telah ditunjukkan sebelumnya bahwa dua kekongruenan pertama memiliki suatu penyelesaian, yaitu ${\displaystyle a_{1,\,2}}$. Himpunan penyelesaian dari dua kekongruenan pertama ini ialah himpunan semua bilangan bulat ${\displaystyle x}$ yang memenuhi $${\displaystyle x\equiv a_{1,\,2}{\pmod {n_{1}\cdot n_{2}}}}$$

Oleh karena ${\displaystyle n_{1}\cdot n_{2}}$ koprima dengan setiap ${\displaystyle n_{i}}$ lainnya, maka sistem kekongruenannya tereduksi menjadi ${\displaystyle k-1}$ kekongruenan simultan, yaitu $${\displaystyle {\begin{aligned}x&\equiv a_{1,\,2}{\pmod {n_{1}\cdot n_{2}}}\\x&\equiv a_{3}{\pmod {n_{3}}}\\&\ldots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$$ Penyelesaian sistemnya akan diperoleh dengan melakukan iterasi serupa yang berulang sebanyak ${\displaystyle k-2}$ kali.

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 ${\displaystyle N_{i}={\tfrac {N}{n_{i}}}}$ menyatakan darab dari semua moduli selain ${\displaystyle n_{i}}$. Oleh karena setiap ${\displaystyle n_{i}}$ koprima pasang demi pasang, maka ${\displaystyle N_{i}}$ akan koprima dengan ${\displaystyle n_{i}}$. Berdasarkan identitas Bézout, maka terdapat suatu bilangan bulat ${\displaystyle M_{i}}$ dan ${\displaystyle m_{i}}$ sedemikian sehingga $${\displaystyle M_{i}N_{i}+m_{i}n_{i}=1}$$

Pandang bilangan $${\displaystyle x=a_{1}M_{1}N_{1}+a_{2}M_{2}N_{2}+a_{3}M_{3}N_{3}+\ldots +a_{k}M_{k}N_{k}}$$ Jika ${\displaystyle i\neq j}$, maka berdasarkan definisi dari ${\displaystyle N_{i}}$, perhatikan bahwa ${\displaystyle N_{i}}$ merupakan kelipatan dari ${\displaystyle n_{j}}$. Akibatnya, $${\displaystyle {\begin{aligned}x&=a_{1}M_{1}N_{1}+a_{2}M_{2}N_{2}+a_{3}M_{3}N_{3}+\ldots +a_{k}M_{k}N_{k}\\x&\equiv a_{j}M_{j}N_{j}{\pmod {n_{j}}}\\&\equiv a_{j}(1-m_{j}n_{j}){\pmod {n_{j}}}\\&\equiv a_{j}{\pmod {n_{j}}}\end{aligned}}}$$ untuk setiap ${\displaystyle 1\leq j\leq k}$, sehingga ${\displaystyle x}$ merupakan penyelesaian dari sistem yang diberikan.

• Sistem pelingkup
• Prinsip Hasse
• Sistem bilangan residu

• Dauben, Joseph W. (2007), Katz, Victor J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India and Islam : A Sourcebook [Matematika Mesir, Mesopotamia, Tiongkok, India dan Islam : Buku Sumber] (dalam bahasa Inggris), Princeton University Press, hlm. 187–384, ISBN 978-0-691-11485-9
• Dence, Joseph B.; Dence, Thomas P. (1999), Elements of the Theory of Numbers [Elemen Teori Bilangan] (dalam bahasa Inggris), Academic Press, ISBN 9780122091308
• Duchet, Pierre (1995). "Hypergraphs". Dalam Graham, R. L.; Grötschel, M.; Lovász, L. (ed.). Handbook of combinatorics [Buku pegangan kombinatorika] (dalam bahasa Inggris). Vol. 1. Amsterdam: Elsevier. hlm. 381–432. MR 1373663.. Lihat Bagian 2.5, "Sifat Helly", hlm. 393–394.
• Gauss, Carl Friedrich (1986). Disquisitiones Arithemeticae (dalam bahasa Inggris). Diterjemahkan oleh Clarke, Arthur A. (Edisi kedua, telah diperbaiki). New York: Springer. ISBN 0-387-96254-9.
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory [Pengantar Klasik menuju Teori Bilangan Modern] (dalam bahasa Inggris) (Edisi ke-2), Springer-Verlag, ISBN 0-387-97329-X
• Kak, Subhash (1986), "Computational aspects of the Aryabhata algorithm" [Aspek komputasional dari algoritma Aryabhata] (PDF), Indian Journal of History of Science (dalam bahasa Inggris), 21 (1): 62–71
• Katz, Victor J. (1998), A History of Mathematics / An Introduction [Sejarah Matematika / Sebuah Pengantar] (dalam bahasa Inggris) (Edisi ke-2), Addison Wesley Longman, ISBN 978-0-321-01618-8
• Libbrecht, Ulrich (1973), Chinese Mathematics in the Thirteenth Century: the "Shu-shu Chiu-chang" of Ch'in Chiu-shao [Matematika Tiongkok Abad Tiga Belas: "Shu-shu Chiu-chang" karya Ch'in Chiu-shao] (dalam bahasa Inggris), Dover Publications Inc, ISBN 978-0-486-44619-6
• Ore, Øystein (1952), "The general Chinese remainder theorem" [Teorema Sisa Tiongkok Umum], The American Mathematical Monthly (dalam bahasa Inggris), 59 (6): 365–370, doi:10.2307/2306804, JSTOR 2306804, MR 0048481
• Ore, Øystein (1988) [1948]. Number Theory and its History [Teori Bilangan beserta Sejarahnya] (dalam bahasa Inggris). Dover. ISBN 0-486-65620-9.
• Pisano, Leonardo (2002), Fibonacci's Liber Abaci (dalam bahasa Inggris), diterjemahkan oleh Sigler, Laurence E., Springer-Verlag, hlm. 402–403, ISBN 0-387-95419-8
• Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications [Teori Bilangan Elementer beserta Penerapannya] (dalam bahasa Inggris) (Edisi ke-3), Addison-Wesley, ISBN 978-0201-57889-8
• Sengupta, Ambar N. (2012), Representing Finite Groups, A Semisimple Introduction [Merepresentasikan Grup Hingga, Pengantar Semisederhana] (dalam bahasa Inggris), Springer, ISBN 978-1-4614-1232-8
• Bourbaki, N. (1989), Algebra I (dalam bahasa Inggris), Springer, ISBN 3-540-64243-9

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms [Pengantar Algoritma] (dalam bahasa Inggris) (Edisi kedua), MIT Press and McGraw-Hill, ISBN 0-262-03293-7. Lihat Bagian 31.5: Teorema sisa Tiongkok, hlm. 873–876.
• Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography [Teorema Sisa Tiongkok: Penerapan pada Komputasi, Pengkodean, Kriptografi] (dalam bahasa Inggris), World Scientific Publishing, hlm. 1–213, ISBN 981-02-2827-9
• Hungerford, Thomas W. (1974), Algebra [Aljabar], Graduate Texts in Mathematics, Vol. 73 (dalam bahasa Inggris), Springer-Verlag, hlm. 131–132, ISBN 978-1-4612-6101-8
• Knuth, Donald (1997), The Art of Computer Programming [Seni Pemrograman Komputer] (dalam bahasa Inggris), vol. 2: Seminumerical Algorithms (Edisi ketiga), Addison-Wesley, ISBN 0-201-89684-2. Lihat Bagian 4.3.2 (hlm. 286–291), latihan 4.6.2–3 (halaman 456).

• (Inggris) Hazewinkel, Michiel, ed. (2001) [1994], "Chinese remainder theorem", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
• (Inggris) Weisstein, Eric W., "Teorema Sisa Tiongkok", MathWorld
• (Inggris) Teorema Sisa Tiongkok di PlanetMath.
• (Inggris) Full text of the Sun-tzu Suan-ching (Chinese) – Chinese Text Project
• (Inggris) Teorema sisa Tiongkok di Cut-the-Knot.