Daftar isi
Soal-soal yang disajikan dalam ajang kompetesi matematika atau olimpiade matematika berbeda dengan soal-soal yang dibahas di sekolah. Pada tingkat olimpiade, seringkali soal-soalnya berkaitan dengan kemampuan berpikir kritis dan kreatif.
Nah, ada satu jenis soal yang hamper selalu keluar dalam setiap kompetisi matematika yaitu mengenai Teorema Sisa Cina. Dari namanya saja sudah menarik ya! Apakah teorema ini berasal dari Cina? Atau apa sih sejarahnya sehingga dinamakan Teorema Sisa Cina? Dan seperti apa juga soal matematika terkait Teorema Sisa Cina ini? Berikut ulasan lengkapnya.
Teorema sisa cina merupakan sebuah algoritma untuk menyelesaikan persoalan dengan prinsip kongruensi modulo (sisa pembagian).
Teorema sisa cina sudah digunakan untuk mengukur pergerakan planet oleh para astronomi Cina. Jejak teorema sisa cina ditemukan di buku yang berjudul Sun-tzu Suan-ching karya Jenderal Sun Tzu atau yang terkenal dengan sebutan Master Sun.
Pada buku yang konon ditulis sejak abad ke-6 itu tertulis sebuah permasalahan yang berkaitan dengan teorema sisa cina. Namun tidak ada penyelesaian dari persoalan terkait teorema sisa cina yang tertulis dalam buku tersebut. Persoalan tersebut adalah
Ada barang yang tidak diketahui jumlahnya. Jika barang itu dibagi 3, maka akan bersisa 2. Jika barang itu dibagi 5 maka akan bersisa 3. Jika barang itu dibagi 7 maka akan bersisa 2. Jadi berapa jumlah barang tersebut?
Penyelesaian terkait permasalahan yang dituliskan oleh Master Sun baru ditemukan sekitar abad ke-6 yaitu berupa sebuah algoritma. Algoritma ini memanfaatkan kongruensi modulo, dan sampai sekarang dikenal sebagai Teorema Sisa Cina. Penggunaan nama ‘Cina’ karena permasalahan awal terkait teorema ini ditemukan di Cina.
Berikut adalah isi dari teorema sisa cina:
Misalkan b1, b2, … , br adalah bilangan bulat positif sedemikian sehingga FPB(bi, bj) = 1 untuk i ≠ j. Maka sistem kongruensi linier satu variabel berikut akan mempunyai solusi simultan yang tunggal modulo bilangan bulat. x ≡ a1 (mod b1) x ≡ a2 (mod b2) ⁞ x ≡ ar (mod br)
Sistem kongruensi linier terkait teorema sisa Cina dapat diselesaikan dengan langkah-langkah berikut.
Berdasarkan teorema sisa cina, maka persoalan yang ada pada buku Master Sun dapat ditulis secara matematis seperti berikut.
Jika hanya berpatokan pada teorema sisa cina dan membaca langkah-langkah penyelesaiannya, tentunya masih akan membingungkan. Berikut diberikan beberapa contoh soal terkait teorema sisa cina dilengkapi dengan pembahasannya.
Pak Riko memiliki sejumlah durian yang baru saja dipetik dari halaman belakang rumahnya. Jika ia memasukkan 5 buah durian masing-masing ke dalam sejumlah karung secukupnya, maka akan ada 2 buah durian yang masih tersisa.
Jika ia memasukkan 6 buah durian masing-masing ke dalam sejumlah karung secukupnya, maka masih ada sisa 4 buah durian. Tentukan berapa banyak durian yang dimiliki paling sedikit oleh Pak Riko?
Pembahasan:
1. Informasi pada soal dapat dituliskan secara sistematis seperti berikut.
2. Selanjutnya ditentukan FPB(5,6) yaitu 1 sehingga sistem kongruensi linier tersebut mempunyai solusi
3. Menentukan b = 5 x 6 = 30 dan diperoleh
4. Dengan demikian diperoleh
5. Menentukan solusi untuk 6x1 ≡ 1 (mod 5)
6. Menentukan solusi untuk 5x2 ≡ 4 (mod 6)
7. Berdasarkan teorema sisa cina diperoleh solusi
8. Solusi dari sistem kongruensi linier pada soal adalah x ≡ 22 (mod 30). Dan dapat disimpulkan bahwa banyaknya durian yang dipanen oleh Pak Riko paling sedikit sebanyak 22 buah.
Selesaikan sistem kongruensi linier berikut menggunakan teorema sisa cina!
x ≡ 3 (mod 4)
x ≡ 2 (mod 3)
x ≡ 4 (mod 5)
Pembahasan:
1. Dari sistem kongruensi linier tersebut diperoleh k = 1, 2, 3 dan a1 = 3, a2 = 2, a3 = 4, b1 = 4, b2 = 3, b3 = 5,
2. Memeriksa apakah sistem mempunyai solusi
3. Menentukan b = 4 x 3 x 5 = 60 dan diperoleh
4. Dengan demikian diperoleh
5. Menentukan solusi untuk 15x1 ≡ 1 (mod 4)
6. Menentukan solusi untuk 20x2 ≡ 1 (mod 3)
7. Menentukan solusi untuk 12x2 ≡ 1 (mod 5)
8. Berdasarkan teorema sisa cina diperoleh solusi
9. Solusi dari sistem kongruensi linier pada soal adalah x ≡ (59 mod 60).
Tentukan sebuah bilangan yang jika dibagi 3 bersisa 1, jika dibagi 5 bersisa 2, dan jika dibagi 7 bersisa 3!
Pembahasan:
Berikut adalah langkah-langkah penyelesaian berdasarkan teorema sisa cina.
1. Informasi pada soal dapat dituliskan secara sistematis seperti berikut.
2. Memeriksa apakah sistem mempunyai solusi
3. Menentukan b = 3 x 5 x 7 = 105 dan diperoleh
4. Dengan demikian diperoleh
5. Menentukan solusi untuk 35x1 ≡ 1 (mod 3)
6. Menentukan solusi untuk 21x2 ≡ 1 (mod 5)
7. Menentukan solusi untuk 15x3 ≡ 1 (mod 7)
8. Berdasarkan teorema sisa cina diperoleh solusi
9. Solusi dari sistem kongruensi linier pada soal adalah x ≡ 52 (mod 105).
10. Jadi, bilangan yang jika dibagi 3 bersisa 1, jika dibagi 5 bersisa 2, dan jika dibagi 7 bersisa 3 adalah 52.