Teorema Sisa Cina: Sejarah – Isi dan Contoh Soalnya

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.

Apa itu Teorema Sisa Cina?

Teorema sisa cina merupakan sebuah algoritma untuk menyelesaikan persoalan dengan prinsip kongruensi modulo (sisa pembagian).

Sejarah Teorema Sisa Cina

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.

Isi Teorema Sisa Cina

Berikut adalah isi dari teorema sisa cina:

Misalkan b₁, b₂, … , b_r adalah bilangan bulat positif sedemikian sehingga FPB(b_i, b_j) = 1 untuk i ≠ j. Maka sistem kongruensi linier satu variabel berikut akan mempunyai solusi simultan yang tunggal modulo bilangan bulat. x ≡ a₁ (mod b₁) x ≡ a₂ (mod b₂) ⁞ x ≡ a_r (mod b_r)

Sistem kongruensi linier terkait teorema sisa Cina dapat diselesaikan dengan langkah-langkah berikut.

• Tentukan FPB(b_i, b_j) untuk i ≠ j. Jika ditemukan FPB(b_i, b_j) = 1 maka sistem kongruensi linier tersebut mempunyai solusi
• Tentukan b = b₁b₂ … b_r dan B_k dengan rumus berikut

3. Selesaikan B_k x_k ≡ 1 (mod b_k) , k = 1, 2, … , r
4. Solusi yang diperoleh adalah x ≡ (a₁b₁x₁ + a₂b₂x₂ + … + a_rb_rx_r)(mod b)

Berdasarkan teorema sisa cina, maka persoalan yang ada pada buku Master Sun dapat ditulis secara matematis seperti berikut.

• barang itu dibagi 3 bersisa 2 ditulis :     x ≡ 2 (mod 3)
• barang itu dibagi 5 bersisa 3 ditulis :     x ≡ 3 (mod 5)
• barang itu dibagi 7 bersisa 2 ditulis :     x ≡ 2 (mod 7)

Contoh Soal dan Pembahasan Teorema Sisa Cina

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.

Contoh Soal 1

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.

• Memasukkan 5 durian dan bersisa 2 durian ditulis :     x ≡ 2 (mod 5)
• Memasukkan 6 durian dan bersisa 4 durian ditulis :     x ≡ 4 (mod 6)
• Perhatikan bahwa k = 1, 2 dan a₁ = 2, a₂ = 4, b₁ = 5, b₂ = 6

2. Selanjutnya ditentukan FPB(5,6) yaitu 1 sehingga sistem kongruensi linier tersebut mempunyai solusi

3. Menentukan b = 5 x 6 = 30 dan diperoleh

• B₁ = 30 / 5 = 6
• B₂ = 30 / 6 = 5

4. Dengan demikian diperoleh

• 6x₁ ≡ 1 (mod 5)
• 5x₂ ≡ 4 (mod 6)

5. Menentukan solusi untuk 6x₁ ≡ 1 (mod 5)

• 6x₁ ≡ 1 (mod 5)    ekuivalen dengan    6x₁ – 1 = 5k
• Untuk nilai k = 1 maka diperoleh nilai x₁ = 1

6. Menentukan solusi untuk 5x₂ ≡ 4 (mod 6)

• 5x₂ ≡ 1 (mod 6)    ekuivalen dengan    5x₂ – 1 = 6k
• Untuk nilai k = 4 maka x₄ = 5

7. Berdasarkan teorema sisa cina diperoleh solusi

• x ≡ ((2 x 6 x 1) + (4 x 5 x 5)) (mod 30)
• x ≡ (12 + 100) (mod 30)
• x ≡ 112 (mod 30)
• x ≡ 22 (mod 30)

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.

Contoh Soal 2

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 a₁ = 3, a₂ = 2, a₃ = 4, b₁ = 4, b₂ = 3, b₃ = 5,

2. Memeriksa apakah sistem mempunyai solusi

• FPB(4,3) = FPB(4,5) = FPB(3,5) = 1 , maka sistem kongruensi ini mempunyai solusi

3. Menentukan b = 4 x 3 x 5 = 60 dan diperoleh

• B₁ = 60 / 4 = 15
• B₂ = 60 / 3 = 20
• B₃ = 60 / 5 = 12

4. Dengan demikian diperoleh

• 15x₁ ≡ 1 (mod 4)
• 20x₂ ≡ 1 (mod 3)
• 12x₃ ≡ 1 (mod 5)

5. Menentukan solusi untuk 15x₁ ≡ 1 (mod 4)

• 15x₁ ≡ 1 (mod 4)    ekuivalen dengan    15x₁ – 1 = 4k
• Untuk nilai k = 11 maka x₁ = 3

6. Menentukan solusi untuk 20x₂ ≡ 1 (mod 3)

• 20x₂ ≡ 1 (mod 3)     ekuivalen dengan    20x₂ – 1 = 3k
• Untuk nilai k = 13 maka x₂ = 2

7. Menentukan solusi untuk 12x₂ ≡ 1 (mod 5)

• 12x₃ ≡ 1 (mod 5)     ekuivalen dengan    12x₃ – 1 = 5k
• Untuk nilai k = 7 maka x₃ = 3

8. Berdasarkan teorema sisa cina diperoleh solusi

• x ≡ ((3 x 15 x 3) + (2 x 20 x 2) + (4 x 12 x 3)) (mod 60)
• x ≡ (135 + 80 + 144) (mod 60)
• x ≡ 359 (mod 60)
• x ≡ (59 mod 60)

9. Solusi dari sistem kongruensi linier pada soal adalah x ≡ (59 mod 60).

Contoh Soal 3

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.

• Jika dibagi 3 bersisa 1 ditulis :     x ≡ 1 (mod 3)
• Jika dibagi 5 bersisa 2 ditulis :     x ≡ 2 (mod 5)
• Jika dibagi 7 bersisa 3 ditulis :     x ≡ 3 (mod 7)
• Perhatikan bahwa k = 1, 2, 3 dan a₁ = 1, a₂ = 2, a₃ = 3, b₁ = 3, b₂ = 5, b₃ = 7

2. Memeriksa apakah sistem mempunyai solusi

• FPB(3, 5) = FPB(3, 7) = FPB(5, 7) = 1 , maka sistem kongruensi ini mempunyai solusi

3. Menentukan b = 3 x 5 x 7 = 105 dan diperoleh

• B₁ = 105 / 3 = 35
• B₂ = 105 / 5 = 21
• B₃ = 105 / 7 = 15

4. Dengan demikian diperoleh

• 35x₁ ≡ 1 (mod 3)
• 21x₂ ≡ 1 (mod 5)
• 15x₃ ≡ 1 (mod 7)

5. Menentukan solusi untuk 35x₁ ≡ 1 (mod 3)

• 35x₁ ≡ 1 (mod 3)    ekuivalen dengan    35x₁ – 1 = 3k
• Untuk nilai k = 23 maka x₁ = 2

6. Menentukan solusi untuk 21x₂ ≡ 1 (mod 5)

• 21x₂ ≡ 1 (mod 5)     ekuivalen dengan    21x₂ – 1 = 5k
• Untuk nilai k = 4 maka x₂ = 1

7. Menentukan solusi untuk 15x₃ ≡ 1 (mod 7)

• 15x₃ ≡ 1 (mod 7)     ekuivalen dengan    15x₃ – 1 = 7k
• Untuk nilai k = 2 maka x₃ = 1

8. Berdasarkan teorema sisa cina diperoleh solusi

• x ≡ ((1 x 35 x 2) + (2 x 21 x 1) + (3 x 15 x 1)) (mod 105)
• x ≡ (70 + 42 + 45) (mod 105)
• x ≡ 157 (mod 105)
• x ≡ 52 (mod 105)

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.