Chinese Remainder Theorem

Note: Untuk memahami post ini, sebaiknya kalian sudah mengetahui materi tentang divisibility, modulo, gcd, dan persamaan linear diophantine..

Berikut ini adalah masalah yang dikemukakan oleh Sun Tsu Suan-Ching (abad ke-4 AD):

Ada suatu benda yang jumlahnya tidak diketahui.. Secara berulang, jika dibagi dengan 3, maka sisanya adalah 2; jika dibagi dengan 5, maka sisanya adalah 7; dan jika dibagi dengan 7 maka sisanya adalah 2. Maka, berapakah jumlah benda tersebut?

Abad ke-6, Oystein Ore menjelaskan suatu masalah yang serupa:

Seorang wanita tua pergi ke pasar dan tiba-tiba seekor kuda menginjak keranjang telurnya.. Semua telur di keranjangnya pecah.. Karena hal itu, penunggang kuda tersebut menawarkan ganti rugi akan telur-telur yang rusak tadi. Ketika ditanyakan berapa jumlah telur yang rusak, ternyata sang wanita tua itu lupa.. Tapi, sang wanita tua ingat sesuatu.. Ketika dia mengambil telur-telur itu dua dua, maka telurnya akan bersisa satu.. Ketika ia mengambilnya tiga-tiga, maka sisa telurnya juga satu. Hal yang sama ketika ia mengambil telur-telurnya empat-empat, lima-lima, dan enam-enam, maka sisanya juga satu. Akan tetapi, ketika dia mengambil telurnya tujuh-tujuh, maka telurnya tidak bersisa.. Berapakah jumlah minimal telur yang ia punya?

Masalah seperti yang dikemukakan di atas secara universal dikenal sebagai Chinese Remainder Theorem atau disingkat dengan CRT. Bagaimana masalah tersebut dipecahkan? Lihat kelanjutan post ini.. ^^

=======================================================================

CHINESE REMAINDER THEOREM
KONDISI YANG MUNGKIN

Chinese Remainder Theorem berbunyi sebagai berikut.

Diberikan suatu bilangan (yang tidak diketahui) yang memenuhi kondisi berikut.



__


Maka, kita hanya dapat menemukan solusi untuk , jika untuk semua dan , kondisi di bawah selalu terpenuhi:

BUKTI:
Pandang 2 kondisi saja:


Maka: Kondisi 1 dapat ditulis ulang menjadi , sedangkan kondisi ke-2 dapat ditulis ulang menjadi: , di mana m dan n adalah bilangan bulat.
Dengan menggabungkan keduanya, maka kita dapatkan:

Dengan pindah ruas, kita dapatkan sbb:

Perhatikan bahwa LHS (ruas kiri) dapat dibagi oleh , akibatnya RHS juga dapat dibagi oleh . Maka:

Dengan analogi yang sama dengan banyak persamaan, maka akan kita dapatkan hasil teorema yang seperti di atas. Bukti pun selesai.

CONTOH SOAL 1:
Diberikan notasi untuk bilangan bulat positif. Jika dibagi 3, maka sisanya1. Jika dibagi 9 maka sisanya 1. Jika dibagi 12, maka sisanya 7. Jika dibagi 14, maka sisanya 7.
Pertanyaannya: Apakah bilangan dapat dicari?

Jawab:
Kita tulis kembali pernyataan di soal menjadi seperti di bawah:
... (i)
... (ii)
... (iii)
... (iv)

Karena yang ditanyakan hanya "apakah nilai itu ada?", maka yang kita lakukan sekarang hanyalah mengecek menggunakan Chinese Remainder Theorem.

Lihat pers (i) dan (ii):
(1-1) habis dibagi (gcd(9,3)) 0 habis dibagi 3 BENAR.
Lihat pers (i) dan (iii):
(7-1) habis dibagi (gcd(12,3)) 6 habis dibagi 3 BENAR.
Lihat pers (i) dan (iv):
(7-1) habis dibagi (gcd(14,3)) 6 habis dibagi 1 BENAR.
Lihat pers (ii) dan (iii):
(7-1) habis dibagi (gcd(12,9)) 6 habis dibagi 3 BENAR.
Lihat pers (ii) dan (iv):
(7-1) habis dibagi (gcd(14,9)) 6 habis dibagi 1 BENAR.
Lihat pers (iii) dan (iv):
(7-7) habis dibagi (gcd(14,12)) 0 habis dibagi 2 BENAR.

Karena semua pengecekan bernilai benar, maka tentunya nilai itu ada dan dapat dicari.

CONTOH SOAL 2:
Budi mengatakan bahwa di memiliki koleksi lukisan yang jumlahnya tidak diketahui karena jumlahnya terlalu banyak. Ia mengatatakan bahwa jika lukisannya dibagikan ke 2 orang, maka sisanya adalah 1. Jika lukisannya dibagikan ke 3 orang, maka sisanya juga 1. Jika dibagi ke 4 orang, sisanya adalah 3. Jika dibagikan ke 12 orang, maka sisanya 1. Pertanyaannya: Apakah Budi benar-benar jujur?

Jawab:
Kita tulis kembali pernyataan di soal menjadi seperti di bawah:
... (i)
... (ii)
... (iii)
... (iv)

Soal ini setipe dengan soal sebelumnya, yaitu hanya mengecek apakah nilai itu ada dan dapat dicari.

Lihat pers (i) dan (ii):
(1-1) habis dibagi (gcd(3,2)) 0 habis dibagi 1 BENAR.
Lihat pers (i) dan (iii):
(3-1) habis dibagi (gcd(4,2)) 2 habis dibagi 2 BENAR.
Lihat pers (i) dan (iv):
(1-1) habis dibagi (gcd(12,2)) 0 habis dibagi 2 BENAR.
Lihat pers (ii) dan (iii):
(3-1) habis dibagi (gcd(4,3)) 2 habis dibagi 1 BENAR.
Lihat pers (ii) dan (iv):
(1-1) habis dibagi (gcd(12,3)) 0 habis dibagi 1 BENAR.
Lihat pers (iii) dan (iv):
(3-1) habis dibagi (gcd(12,4)) 2 habis dibagi 4 SALAH.

Karena tidak semua pengecekan bernilai benar, maka nilai itu tidak ada dan tidak dapat dicari. Artinya, Budi berbohong.

=======================================================================

ALGORITMA UNTUK MENYELESAIKAN MASALAH
CHINESE REMAINDER THEOREM

Algoritma yang original yang digunakan untuk menyelesaikan masalah CRT bisa kalian lihat di http://en.wikipedia.org/wiki/Chinese_remainder_theorem.. (Lihat di bagian contoh).. Namun, bagi saya, cara itu terlalu panjang.. Membutuhkan perhitungan berdigit banyak... Tidak efisien..!! Maka dari itu, sebaiknya kita menggunakan cara tradisional, yaitu dengan LOGIKA..!!! Kita akan mensubstitusikan setiap kondisi ke kondisi berikutnya menghasilkan integer yang bernilai lebih besar dari sebelumnya..

Langsung saja ke contoh soal..
Note: Semua variabel yang ada di sini merupakan variabel bilangan bulat.

CONTOH SOAL 3:
Diberikan notasi untuk bilangan bulat. Jika dibagi 3, maka sisanya1. Jika dibagi 9 maka sisanya 1. Jika dibagi 12, maka sisanya 7. Jika dibagi 14, maka sisanya 7. Tentukan nilai yang terkecil.

Jawab:
Kita tulis kembali pernyataan di soal menjadi seperti di bawah:
... (i)
... (ii)
... (iii)
... (iv)

Dimulai dari persamaan (i)

Dengan mensubstitusikannya ke pers (ii), maka kita dapatkan . Disederhanakan menjadi: . Substitusikan nilai m ini ke pers di atas, maka menjadi:



Dengan mensubstitusikannya ke pers. (iii), maka kita dapatkan . Disederhanakan menjadi: . Perhatikan bahwa sekarang kita menemui bentuk persamaan linear diophantine, dan kita ingin membentuk persamaan menjadi "n=...". Maka, dengan menyelesaikan pers diophantine tersebut, kita akan dapatkan , maka kita dapatkan . Substitusikan nilai n ini ke pers sebelumnya, maka menjadi:




Dengan mensubstitusikannya ke pers. (iv), maka kita dapatkan . Disederhanakan menjadi: . Lagi-lagi pers diophantine... Kita ingin membentuk persamaan menjadi "k=...". Dengan menyelesaikan pers diophantine tersebut, kita akan dapatkan . Dikalikan 6, maka hasilnya: . Maka . Namun, karena masih ada konstanta negatif, maka substitusikan a=b+2, maka hasilnya: . Substitusikan nilai k ke pers sebelumnya, maka menjadi:



... (Ini adalah persamaan gabungan dari 4 kondisi)

Maka, nilai terkecil didapat jika mensubstitusi b=0, maka = 91.

CONTOH SOAL 3B:
Diberikan notasi untuk bilangan bulat. Jika dibagi 3, maka sisanya1. Jika dibagi 9 maka sisanya 1. Jika dibagi 12, maka sisanya 7. Jika dibagi 14, maka sisanya 7. Tentukan nilai yang terkecil.

Jawab.
Mungkin ada yang bingung mengapa soal ini sama dengan soal nomor sebelumnya. Alasannya adalah karena saya ingin memberikan sequence yang berbeda, dan akan ditunjukkan bahwa hasilnya adalah sama.

Kita tulis kembali pernyataan di soal menjadi seperti di bawah:
... (i)
... (ii)
... (iii)
... (iv)

Dimulai dari persamaan (iv)

Dengan mensubstitusikannya ke pers (iii), maka kita dapatkan . Disederhanakan menjadi: . Merupakan persamaan trivial, maka kita dapatkan:. Artinya atau dapat ditulis atau . Substitusikan nilai m ini ke pers di atas, maka menjadi:



Dengan mensubstitusikannya ke pers (ii), maka kita dapatkan . Disederhanakan menjadi: . Lagi-lagi persamaan diophantine. Kita ingin membentuk persamaan menjadi "k=...". Dengan menyelesaikan pers diophantine tersebut, kita akan dapatkan . Dikalikan 2, maka hasilnya: . Jadi, dapat ditulis atau atau . Substitusikan nilai k ini ke persamaan sebelumnya.




Dengan mensubstitusikannya ke pers. (i), maka kita dapatkan . Disederhanakan menjadi: . Akan menghasilkan penyelesaian sbb: , sehingga dapat ditulis atau . Substitusikan nilai ini ke pers sebelumnya.

.
Maka, nilai terkecil didapat jika mensubstitusi b=0, maka = 91, merupakan jawaban yang sama seperti soal sebelumnya. Jadi, sequence (urutan) penyelesaian tidak jadi masalah.

====================================================================

CLOSING

Nah, udah ahh... Contohnya sepertinya udah cukup.. Aku lagi males buat contoh.. Kira-kira, ada yang udah ngerti lom?? Kalo belom silakan nanya...!!! Atau, kalo butuh contoh soal lagi, aku akan buatin... Dan, pastinya akan lebih seruuu.. ^^

Selanjutnya, mengenai masalah Sun Tsu Suan-Ching dan Oystein Ore (yang dikemukakan di awal post) kalo ada yang berniat memberikan jawaban, silakan tulis di comment yaaa.. ^^

Sumber :
http://en.wikipedia.org/wiki/Chinese_remainder_theorem
http://www.cut-the-knot.org/blue/chinese.shtml