Teorema sisa Tiongkok: Perbedaan antara revisi
Tampilan
Konten dihapus Konten ditambahkan
k bot Menambah: ar:مبرهنة الباقي الصيني |
k Robot: Cosmetic changes |
||
Baris 3: | Baris 3: | ||
== Kongruensi Simultan dari bilangan bulat == |
== Kongruensi Simultan dari bilangan bulat == |
||
Bentuk asli dari teorema ini, seperti terdapat dalam buku yang ditulis oleh ahli matematika dari [[Republik Rakyat Tiongkok|Tiongkok |
Bentuk asli dari teorema ini, seperti terdapat dalam buku yang ditulis oleh ahli matematika dari [[Republik Rakyat Tiongkok|Tiongkok]] [[Qin Jiushao]] dan diterbitkan pada tahun [[1247]], adalah suatu pernyataan tentang kongruensi simultan (lihat [[aritmatika 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]] |
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'' |
(''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 |
||
:<math>x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \cdots, k</math> |
:<math>x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \cdots, k</math> |
||
Baris 22: | Baris 22: | ||
e_i \equiv 0 \pmod{n_j}</math> |
e_i \equiv 0 \pmod{n_j}</math> |
||
untuk ''j'' |
untuk ''j'' ≠ ''i''. |
||
for (i= 1; i <= k; i++) |
for (i= 1; i <= k; i++) |
||
Baris 38: | Baris 38: | ||
x += a[i] * e[i]; |
x += a[i] * e[i]; |
||
Sebagai contoh, misalkan kita ingin |
Sebagai contoh, misalkan kita ingin menemukan suatu bilangan bulat ''x'' sehingga |
||
:<math>x \equiv 2 \pmod{3} </math> |
:<math>x \equiv 2 \pmod{3} </math> |
||
Baris 48: | Baris 48: | ||
x % 5 == 2 % 5 |
x % 5 == 2 % 5 |
||
Menggunakan [[ekstensi algoritma Euklidean]] untuk 3 dan |
Menggunakan [[ekstensi algoritma 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 algoritma 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 algoritma Euklidean untukr 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. |
||
Kadangkala, 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>'' |
Kadangkala, 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 seringkali bisa menemukan penyelesaian dari sistem kongruensi simultan, sekalipun setiap pasang modulusnya tidak selalu koprima. |
Dengan menggunakan [[metode substitusi]], kita seringkali bisa menemukan penyelesaian dari sistem kongruensi simultan, sekalipun setiap pasang modulusnya tidak selalu koprima. |
||
==Pranala luar== |
== Pranala luar == |
||
* [http://www.cut-the-knot.org/blue/chinese.shtml Chinese remainder theorem] |
* [http://www.cut-the-knot.org/blue/chinese.shtml Chinese remainder theorem] |
||
[[ |
[[Kategori:Teorema|Sisa Tiongkok]] |
||
[[ar:مبرهنة الباقي الصيني]] |
[[ar:مبرهنة الباقي الصيني]] |