Berikut ini adalah masalah yang dikemukakan oleh Sun Tsu Suan-Ching (abad ke-4 AD):
=======================================================================
CHINESE REMAINDER THEOREM
KONDISI YANG MUNGKIN
Chinese Remainder Theorem berbunyi sebagai berikut.
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:
, akibatnya RHS juga dapat dibagi oleh . Maka:
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.. ^^
dan 
, kondisi di bawah selalu terpenuhi: