|
[[File:Sun_Tzu_Chinese_remainder_theorem.svg|thumb|Rumusan asli Sunzi: {{nowrap|''x'' ≡ 2 (mod 3)}} {{nowrap|≡ 3 (mod 5)}} {{nowrap|≡ 2 (mod 7)}} {{nowrap|dengan solusi}} {{nowrap|''x'' <nowiki>=</nowiki> 23 + 105''k'',}} {{nowrap|dengan ''k'' adalah bilangan bulat}}]]
'''Teorema sisa Tiongkok''' adalah hasil dari [[aljabar abstrak]] dan [[teori bilangan]].
== Kongruensi Simultan dari bilangan bulat ==
Bentuk asli dari teorema ini, seperti terdapat dalam buku yang ditulis oleh ahli matematika dari [[Republik Rakyat CinaTiongkok]] [[Qin Jiushao]] dan diterbitkan pada tahun [[1247]], adalah suatu pernyataan tentang kongruensi simultan (lihat [[aritmatikaaritmetika modular]]).
Misalkan ''n''<sub>1</sub>, ..., ''n''<sub>''k''</sub> adalah [[bilangan bulat]] positif yang setiap pasangnya adalah [[koprima]] (yang artinya [[faktor persekutuan terbesar|FPB]]
(''n''<sub>''i''</sub>, ''n''<sub>''j''</sub>) = 1 untuk setiap ''i'' ≠ ''j''). Maka, untuk setiap bilangan bulat ''a''<sub>1</sub>, ..., ''a''<sub>''k''</sub>, selalu ada bilangan bulat ''x'' yang merupakan penyelesaian dari sistem kongruensi simultan
Terlebih lagi, semua penyelesaian ''x'' dari sistem ini adalah juga kongruen modulo dari perkalian ''n'' = ''n''<sub>1</sub>...''n''<sub>''k''</sub>.
Suatu penyelesaian ''x'' dapat ditemukan dengan cara sebagai berikut. Untuk setiap ''i'', bilangan bulat ''n<sub>i</sub>'' dan ''n''/''n<sub>i</sub>'' adalah koprima, dan menggunakan ekstensi [[algoritmaalgoritme Euklidean]] kita dapat menemukan bilangan bulat ''r'' dan ''s'' sehingga ''r n<sub>i</sub>'' + ''s'' ''n''/''n<sub>i</sub>'' = 1. Jika kita menentukan ''e<sub>i</sub>'' = ''s'' ''n''/''n<sub>i</sub>'', maka kita dapat
:<math>e_i \equiv 1 \pmod{n_i} \quad\mathrm{and}\quad
x % 5 == 2 % 5
Menggunakan [[ekstensi algoritmaalgoritme Euklidean]] untuk 3 dan 4×5 = 20, kita memperoleh (-13) × 3 + 2 × 20 = 1, di mana ''e''<sub>1</sub> = 40 <i>''(<code>e[1] == 40</code>)</i>''. Menggunakan algoritmaalgoritme Euklidean untuk 4 dan 3×5 = 15, kita memperoleh (-11) × 4 + 3 × 15 = 1. Oleh karena itu, ''e''<sub>2</sub> = 45 <i>''(<code>e[2] == 45</code>)</i>''. Akhirnya, menggunakan algoritmaalgoritme Euklidean untukruntuk 5 dan 3×4 = 12, kita memperoleh 5 × 5 + (-2) × 12 = 1, yang berarti ''e''<sub>3</sub> = -24 <i>''(<code>e[3] == -24</code>)</i>''. 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.
KadangkalaKadang kala, sistem kongruensi simultan dapat diselesaikan sekalipun <i>''n<sub>i</sub></i>'' (<i>''n[i]</i>'') setiap pasangnya tidak selalu koprima. Syarat-syarat yang lebih tepat adalah sebagai berikut: sistem mempunyai penyelesaian ''x'' jika dan hanya jika ''a<sub>i</sub>'' ≡ ''a<sub>j</sub>'' ('''mod''' fpb(''n<sub>i</sub>'', ''n<sub>j</sub>'')) (<code>a[i] == a[j] % gcd(n[i], n[j]</code>)) untuk semua ''i'' dan ''j''. Semua penyelesaian ''x'' adalah kongruen modulo [[kelipatan persekutuan terkecil]] dari ''n<sub>i</sub>'' (<code>n[i]</code>).
Dengan menggunakan [[metode substitusi]], kita seringkalisering kali bisa menemukan penyelesaian dari sistem kongruensi simultan, sekalipun setiap pasang modulusnya tidak selalu koprima.
== Pranala luar ==
* [http://www.cut-the-knot.org/blue/chinese.shtml Chinese remainder theorem]
[[Kategori:Teorema matematika|Sisa Tiongkok]]
[[ar:مبرهنة الباقي الصيني]]
[[cs:Čínská věta o zbytcích]]
[[de:Chinesischer Restsatz]]
[[en:Chinese remainder theorem]]
[[es:Teorema chino del resto]]
[[fr:Théorème des restes chinois]]
[[he:משפט השאריות הסיני]]
[[hu:Kínai maradéktétel]]
[[it:Teorema cinese del resto]]
[[ja:中国の剰余定理]]
[[mn:Үлдэгдлийн тухай Хятадын теорем]]
[[nl:Chinese reststelling]]
[[pl:Chińskie twierdzenie o resztach]]
[[pt:Teorema chinês do resto]]
[[ro:Teorema chinezească a resturilor]]
[[ru:Китайская теорема об остатках]]
[[simple:Chinese remainder theorem]]
[[sv:Kinesiska restklassatsen]]
[[ur:چینی تقسیم باقی مسلئہ اثباتی]]
[[vi:Định lý số dư Trung Quốc]]
[[zh:中国剩余定理]]
[[zh-classical:韓信點兵]]
| 