Matematika Diskrit : Chinese Remainder Problem

Chinese Remainder Problem

Pada abad pertama Masehi, seorang matematikawan China yang bernama Sun Tse mengajukan pertanyaan sebagai berikut:

Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7.

Misakan bilangan bulat tersebut = x. Formulasikan kedalam sistem kekongruenan linier:

x โ‰ก 3 (mod 5)

x โ‰ก 5 (mod 7)

x โ‰ก 7 (mod 11)

Teorema. (Chinese Remainder Theorem)

Misalkan m1, m2, โ€ฆ,mn adalah bilangan bulat positif sedemikian sehingga PBB(mi , mj ) = 1 untuk i โ‰  j. Maka sistem kekongruenan linier

x โ‰ก a1 (mod m1 )

x โ‰ก a2 (mod m2 )

โ‹ฏ

x โ‰ก an (mod mn )

mempunyai sebuah solusi unik dalam modulus m = m1 ยท m2 ยท โ€ฆ ยท mn (yaitu, terdapat solusi x dengan 0 โ‰ค x < m dan semua solusi lain yang kongruen dalam modulus m dengan solusi ini)

Contoh

Tentukan solusi dari pertanyaan Sun Tse tersebut

Penyelesaian:

x โ‰ก 3 (mod 5) โ†’ x = 3 + 5k1 (i)

Sulihkan (i) ke dalam kongruen kedua (yaitu x โ‰ก 5 (mod 7)) menjadi:

3 + 5k1 โ‰ก 5 (mod 7) โ†’ 5k1 โ‰ก 2 (mod 7) โ†’ k1 โ‰ก 6 (mod 7), atau k1 = 6 + 7k2 (ii)

Sulihkan (ii) ke dalam (i):

x = 3 + 5k1 = 3 + 5(6 + 7k2) = 33 + 35k2(iii)

Sulihkan (iii) ke dalam kongruen ketiga (yaitu x โ‰ก 7 (mod 11)) menjadi:

33 + 35k2 โ‰ก 7 (mod 11) โ†’ 35k2 โ‰ก -26 (mod 11) โ†’ k2 โ‰ก 9 (mod 11) atau k2 = 9 + 11k3

Sulihkan k2 ini ke dalam (iii) menghasilkan:

x = 33 + 35(9 + 11k3) = 348 + 385k3 atau x โ‰ก 348 (mod 385).

Ini adalah solusinya.

348 adalah bilangan bulat positif terkecil yang merupakan solusi sistem kekongruenan di atas.

Periksa bahwa bahwa 348 mod 5 = 3, 348 mod 7 = 5, dan 348 mod 11 = 7.

Perhatikan juga bahwa 385 = 5 ยท 7 ยท 11.


Solusi unik ini, yaitu x โ‰ก 348 (mod 385), modulus 385 merupakan m = m1 ยท m2 ยท m3 = 5 ยท 7 ยท 11 = 385

Secara umum, solusi sistem kekongruenan linier adalah berbentuk

x = a1M1y1 + a2M2y2 + โ€ฆ + anMnyn

yang dalam hal ini, Mk adalah perkalian semua modulus kecuali mk

yk adalah balikan Mk dalam modulus mk


Tinjau kembali persoalan Chinese remainder problem:

Hitung: m = 5 ยท 7 ยท 11 = 385

M1 = 7 ยท 11 = 77, M2 = 5 ยท 11 = 55, M3 = 5 ยท 7 = 35

y1 = 3 karena 77 ยท 3 โ‰ก 1 (mod 5)

y2 = 6 karena 55 ยท 6 โ‰ก 1 (mod 7)

y3 = 6 karena 35 ยท 6 โ‰ก 1 (mod 11)

maka solusi unik dari sistem kekongruenan tersebut adalah

x = a1M1y1 + a2M2y2 + โ€ฆ + a3M3Y3

= 3 ยท 77 ยท 3 + 5 ยท 55 ยท 6 + 7 ยท 35 ยท 6

= 3813

โ‰ก 348 (mod 385).


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Teori Bilangan, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up