Sejarah, Pemahaman dan Contoh Soalan

Soalan yang dikemukakan dalam acara pertandingan matematik atau olimpiade matematik adalah berbeza dengan soalan yang dibincangkan di sekolah. Di peringkat Olimpik, banyak persoalan berkaitan kebolehan berfikir secara kritis dan kreatif.

Nah, ada satu jenis saal yang hamper selalu keluar dalam setiap compeision mathematika iaitu about Teorema Sisa Cina. Dari name saja sudah menarik ya! Adakah teorem ini berasal dari China? Atau apa sih sejarahnya sehpa nama Teorema Sisa Cina? And seperti apa juga mathematica related to Teorema Sisa Cina ini? Berikut berjamin lepkagannya.

Apa itu Teorema Sisa Cina?

Teorema sisa cina merupakan sebuah algoritma untuk silahan besalan dengan prinsip kongruensi modulo (sisa pembahagian).

Sejarah Teorema Sisa Cina

Teorema sisa cina sudah digunakan untuk menukar planet oleh para astronomi Cina. Jejak teorema sisa cina terdapat dalam buku berjudul Sun-tzu Suan-ching karya Jeneral Sun Tzu atau kitab terkenal bernama Master Sun.

Pada buku yang konon ditulis sejak abad ke-6, ia ditulis masalah yang berkaitan dengan teori China yang lain. Walau bagaimanapun, tiada penyelesaian kepada masalah yang berkaitan dengan baki teorem Cina yang ditulis dalam buku ini. Persoalan tersebut adalah

Ada barang yang tidak diktatura jumlamnya. Jika barang itu dibahagi 3, maka akan bersisa 2. Jika barang itu dibahagi dengan 5 maka akan bersisa 3. Jika barang itu dibahagi dengan 7 maka akan bersisa 2. Jadi berapa jumla barang tersebut?

Penyelesaian kepada masalah yang ditulis oleh Master Sun ditemui sekitar abad ke-6, dalam bentuk algoritma. Algoritma ini menggunakan modulo congruensi, dan sehingga kini ia dikenali sebagai Theorema Sisa Cina. Penggunaan nama ‘Cina’ kerana masalah awal yang dikaitkan dengan teorem ini terdapat di China.

Isi Teorema Sisa Cina

Berikut adalah isi dari teorema sisa cina:

Misalkan b₁b₂… , b_r adalah albanan bulat positif semanti sehat FPB(b_ib_J) = 1 untuk i ≠ j. Maka sistem kongruensi linear satu variabel berikut akan memana solutioni simultan yang tunggal modulo number bulat. x ≡ a₁ (mod b₁) x ≡ a₂ (mod b₂) ⁞ x ≡ a_r (mod b_r)

Sistem congruensi linear yang berkaitan dengan teorem Cina yang tinggal boleh diselesaikan langkah demi langkah di bawah.

• Tentukan FPB(b_ib_J) untuk i ≠ j. Jika didapati FPB (b_ib_J) = 1 maka sistem congruensi linear tersebut mempunyai penyelesaian
• Tentukan b = b₁b₂ … b_r Dan B_k dengan formula berikut

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

Berdasarkan teori seluruh negara China, masalah yang terdapat dalam buku Master Sun boleh ditulis seperti berikut secara matematik.

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

Contoh Soalan dan Pembahasan Teorema Sisa Cina

Jika hanya berpatokan pada teorem cina sisa dan melakukan langkah-langkah sama-samanya, sudah tentu ia akan tetap mengelirukan. Berikut adalah contoh soal pasalidar teorema sisa cina komplemen dengan dengan pesabhannya.

Contoh soalan 1

Pak Riko mempunyai beberapa buah durian yang baru dicelup dari belakang rumahnya. Jika anda menambah 5 buah durian setiap kali, akan ada 2 buah durian yang tinggal.

Jika ia meletakkan 6 buah durian masing-masing ke dalam jumbal karung karung ke dalam, maka masih ada 4 buah durian. Tentukan berapa banyak durian yang dimiliki paling sedikit oleh Pak Riko?

Pembahasan:

1. Maklumat soalan boleh ditulis seperti berikut

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

2. Seterusnya, tentukan FPB(5,6) yaitu 1 supaya sistem kongruensi linear mempunyai penyelesaian.

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

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

4. Dengan itu diperolehi

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

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

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

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

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

7. Berdasarkan teori sisa cina, penyelesaian diperolehi

• 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 congruensi linear pada soal adalah x ≡ 22 (mod 30). Dan dapat disimpulkan bahawa banyaknya durian yang dipanen oleh Pak Riko paling sedikt semanteh 22 buah.

Contoh Soalan 2

Pilih sistem kongruensi linear beringu menggunakan teorema sisa cina!

x ≡ 3 (mod 4)
x ≡ 2 (mod 3)
x ≡ 4 (mod 5)

Pembahasan:

1. Dari sistem kongruensi linear tersebut k = 1, 2, 3 dan a₁ = 3, a₂ = 2, a₃ = 4, b₁ = 4, b₂ = 3, b₃ = 5,

2. Semak sama ada sistem mempunyai penyelesaian

• FPB(4,3) = FPB(4,5) = FPB(3,5) = 1, jadi sistem yang serasi ini mempunyai penyelesaian

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

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

4. Dengan itu diperolehi

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

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

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

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

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

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

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

8. Berdasarkan teorem sisa cina, solusi diperolehi

• 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 linear pada soal adalah x ≡ (59 mod 60).

Contoh Soalan 3

Cari nombor yang membahagi dengan 3 dengan 1, membahagi dengan 5 dengan 2, dan membahagi dengan 7 dengan 3!

Pembahasan:

Berikut adalah langkah-langkah penyelesaian berdasarkan teori sisa cina.

1. Maklumat soalan boleh ditulis seperti berikut

• Jika anda membahagikan 3 dengan 1, ia ditulis: x ≡ 1 (mod 3)
• Jika anda membahagikan 5 dengan 2, ia ditulis: x ≡ 2 (mod 5)
• Jika anda membahagikan 7 dengan 3, ia ditulis: x ≡ 3 (mod 7)
• Perhatikan bahawa k = 1, 2, 3 dan a₁ = 1, a₂ = 2, a₃ = 3, b₁ = 3, b₂ = 5, b₃ = 7

2. Semak sama ada sistem mempunyai penyelesaian

• FPB(3, 5) = FPB(3, 7) = FPB(5, 7) = 1, jadi sistem yang serasi ini mempunyai penyelesaian

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

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

4. Dengan itu diperolehi

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

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

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

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

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

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

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

8. Berdasarkan teorem sisa cina, solusi diperolehi

• 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 congruensi linear pada soal adalah x ≡ 52 (mod 105).

10. Jadi, nombor yang membahagi 3 dengan 1, membahagi dengan 5 dengan 2, dan membahagi dengan 7 dengan 3 ialah 52.