Teorema Sisa Cina

Posted on January 3, 2014 by Nursatria
Sumber: ciee.org

Sumber: ciee.org

Saya punya soal cerita sebagai berikut

Alkisah seorang Nenek pergi ke pasar dengan membawa keranjang berisi telur.Di pasar keranjang tersebut ditaruh di bawah, tanpa sengaja seorang pemuda menginjak keranjang tersebut sehingga pecah semua telur yang berada didalam keranjang. Pemuda tersebut berniat menganti kerugian dan bertanya kepada si nenek berapa jumlah telur di keranjang. Akan tetapi si Nenek tidak ingat berapa jumlah telur di keranjang.  Si Nenek hanya ingat jika jumlah telur tersebut dibagi 3 maka sisanya 2 telur. Jika dibagi 5 maka sisanya 3 telur dan jika dibagi 7 maka sisanya 2 telur.

Berapa jumlah telur terkecil yang mungkin dimiliki si Nenek?

Jika kita ubah kedalam bahasa matematis, soal tersebut meminta kita mencari solusi dari sitem linear kongkruen

x\equiv2\pmod3

x\equiv3\pmod5

x\equiv2\pmod7

Bagaimana mencari solusi dari sistem linear kongkruen?

Jangan khawatir, ada metodenya. Nah… yang menarik metode tersebut sudah ada sekitar abad 3-5 masehi, seorang Matematikawan Cina bernama Sun Zi menerbitkan sebuah buku berjudul Sun Zi Suanjing, Aritmatika Klasik  Sun Zi . Dalam buku tersebut diperkenalkan metode mencari solusi sistem linear kongkruen, sekarang metode tersebut dikenal Teorema Sisa Cina ( Chinese remainder theorem) disingkat TSC

Teorema sisa Cina: Diberikan bilangan bulat postitif m_{1},m_{2},\ldots,m_{r} yang kesemuanya salaing relatif prima dan bilangan bulat  a_{1},a_{2},\ldots,a_{r} maka sistem linear kongkruen

x\equiv a_{1}\pmod {m_{1}}

x\equiv a_{2}\pmod {m_{2}}

\vdots

x\equiv a_{r}\pmod {m_{r}}

mempunyai solusi  modulo tunngal M=m_{1}\cdot m_{2}\cdot\ldots\cdot m_{r} yaitu

{\displaystyle x\equiv a_{1}M_{1}y_{1}+a_{2}M_{2}y_{2}+\ldots+a_{r}M_{r}y_{r}\pmod M}

dengan M_i=M/m_i dan y_{i}=\left(M_{i}\right)^{-1}\pmod m_{1}, dengan kata lain y_{i}M_{i}=1\pmod m_{i} untuk 1\leq i\leq r

Bukti: Perhatikan bahwa FPB\left(M_{i},m_{1}\right)=1, untuk 1\leq i\leq r  oleh karena itu berdasarkan algoritma Euclid yang diperluas maka y_i eksis

Akan ditunjukan  x_{0}=a_{1}M_{1}y_{1}+a_{2}M_{2}y_{2}+\ldots+a_{r}M_{r}y_{r} adalah solusinya.

Diketahui  y_{i}M_{i}=1\pmod {m_{i}}, itu berarti a_iy_{i}M_{i}=a_i\pmod {m_{i}}, untuk  untuk 1\leq i\leq r. Disisi lain jika j\neq i maka m_{j}|M_{i}, yang berakibat a_{i}M_{i}y_{i}\equiv0\pmod {m_{j}}. Terbukti x_0\equiv a_{i}\pmod {m_{i}} untuk 1\leq i\leq r.

Selanjutnya akan ditunjukkan ketunggalan modulu dari solusi

Andaikan ada solusi lain yaitu x_1, itu berarti

x_0\equiv a_{i}\pmod {m_{i}} dan x_1\equiv a_{i}\pmod {m_{i}}

yang berakibat x_{0}-x_{1}\equiv0\pmod m_{i}, untuk semua i, so x_{0}-x_{1}\equiv0\pmod M. Terbukti keduanya mempunyai modulo yang sama

\square

Sekarang dengan mengunakan TSC, kita selesaikan masalah si Nenek diatas, Ambil M=3\cdot5\cdot7=105, diproleh

M_{1}=105/3=35,\quad y_{1}=2\equiv35^{-1}\pmod3

M_{2}=105/5=21,\quad y_{1}=1\equiv21^{-1}\pmod5

M_{3}=105/7=15,\quad y_{1}=1\equiv15^{-1}\pmod7

didapat solusi

x\equiv2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1\pmod{105}

x\equiv233\pmod{105}.

x=23

Kita sekarang memperoleh jawabnnya, jumlah telur yang ada di keranjang adalah 23 butir.

Advertisement

About Nursatria

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in pembuktian, Teori Bilangan and tagged , , , , . Bookmark the permalink.

6 Responses to Teorema Sisa Cina

  1. TunkFey says:
    January 23, 2014 at 19:51

    Kok kayaknya menurut saya agak ribet ya? Maklum, saya bukan orang matematika murni. Hehehe…
    Saya ada solusi yang menurut saya relatif lebih mudah. Caranya memang agak intuitif sih…
    Dari soal di atas, kita bisa mendapatkan persamaan berikut:
    S=3x+2=5y+3=7z+2 (1)
    dimana {S} menyatakan jumlah telur dengan {x}, {y}, dan {z} adalah bilangan bulat positif. Jika persamaan (1) kita sederhanakan, diperoleh:
    3x-5y=1 (2)
    3x-7z=0 (3)
    \displaystyle 5y-7z=-1(4)
    Dengan menggunakan persamaan (3), diperoleh:
    x=\frac{7}{3}z
    Pilih {z=3} (pemilihan nilai berdasarkan prinsip _trial and error_ asalkan {x}, {y}, dan {z} yang diperoleh memenuhi syarat persamaan (1)), sehingga didapat {x=7} dan {y=4}. Substitusikan salah satu nilai dari variabel tersebut ke persamaan (1), diperoleh:
    S=3x+2=3(7)+2=23

    Reply
  2. tian says:
    January 19, 2014 at 20:36

    Itu hanya berlaku untuk bilangan prima relatif ya? Kalau soal ini gimana: Suatu bilangan jika dibagi 5 sisanya 2,dibagi 7 sisanya 3,dibagi 9 sisanya 4,berapa kah nilai bilangan tersebut?

    Reply
  3. Istanamurah says:
    January 4, 2014 at 11:05

    Jadi inget sama nenek ane gan, ya walau dijadikan contoh. 😀

    Reply

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s