Teorema sisa Tiongkok: Perbedaan antara revisi
k bot Menambah: ro:Teorema chinezească a resturilor |
k Robot: Cosmetic changes |
||
Baris 3:
== Kongruensi Simultan dari bilangan bulat ==
Bentuk asli dari teorema ini, seperti terdapat dalam buku yang ditulis oleh ahli matematika dari [[Republik Rakyat
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
|
Revisi per 16 Agustus 2008 10.58
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 Cina Qin Jiushao dan diterbitkan pada tahun 1247, adalah suatu pernyataan tentang kongruensi simultan (lihat aritmatika modular). Misalkan n1, ..., nk adalah bilangan bulat positif yang setiap pasangnya adalah koprima (yang artinya FPB (ni, nj) = 1 untuk setiap i ≠ j). Maka, untuk setiap bilangan bulat a1, ..., ak, selalu ada bilangan bulat x yang merupakan penyelesaian dari sistem kongruensi simultan
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 = n1...nk.
Suatu penyelesaian x dapat ditemukan dengan cara sebagai berikut. Untuk setiap i, bilangan bulat ni dan n/ni adalah koprima, dan menggunakan ekstensi algoritma Euklidean kita dapat menemukan bilangan bulat r dan s sehingga r ni + s n/ni = 1. Jika kita menentukan ei = s n/ni, maka kita dapat
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
for(i= 1; i <= k; i++) x += a[i] * e[i];
Sebagai contoh, misalkan kita ingin menemukan suatu bilangan bulat x sehingga
x % 3 == 2 % 3 && x % 4 == 3 % 4 && x % 5 == 2 % 5
Menggunakan ekstensi algoritma Euklidean untuk 3 dan 4×5 = 20, kita memperoleh (-13) × 3 + 2 × 20 = 1, di mana e1 = 40 (e[1] == 40
). Menggunakan algoritma Euklidean untuk 4 dan 3×5 = 15, kita memperoleh (-11) × 4 + 3 × 15 = 1. Oleh karena itu, e2 = 45 (e[2] == 45
). Akhirnya, menggunakan algoritma Euklidean untukr 5 dan 3×4 = 12, kita memperoleh 5 × 5 + (-2) × 12 = 1, yang berarti e3 = -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.
Kadangkala, sistem kongruensi simultan dapat diselesaikan sekalipun ni (n[i]) setiap pasangnya tidak selalu koprima. Syarat-syarat yang lebih tepat adalah sebagai berikut: sistem mempunyai penyelesaian x jika dan hanya jika ai ≡ aj (mod fpb(ni, nj)) (a[i] == a[j] % gcd(n[i], n[j]
)) untuk semua i dan j. Semua penyelesaian x adalah kongruen modulo kelipatan persekutuan terkecil dari ni (n[i]
).
Dengan menggunakan metode substitusi, kita seringkali bisa menemukan penyelesaian dari sistem kongruensi simultan, sekalipun setiap pasang modulusnya tidak selalu koprima.