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 m₁, m₂, …,m_n adalah bilangan bulat positif sedemikian sehingga PBB(m_i , m_j ) = 1 untuk i ≠ j. Maka sistem kekongruenan linier

x ≡ a₁ (mod m₁ )

x ≡ a₂ (mod m₂ )

⋯

x ≡ a_n (mod m_n )

mempunyai sebuah solusi unik dalam modulus m = m₁ · m₂ · … · m_n (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 + 5k₁ (i)

Sulihkan (i) ke dalam kongruen kedua (yaitu x ≡ 5 (mod 7)) menjadi:

3 + 5k₁ ≡ 5 (mod 7) → 5k₁ ≡ 2 (mod 7) → k₁ ≡ 6 (mod 7), atau k₁ = 6 + 7k₂ (ii)

Sulihkan (ii) ke dalam (i):

x = 3 + 5k₁ = 3 + 5(6 + 7k₂) = 33 + 35k₂(iii)

Sulihkan (iii) ke dalam kongruen ketiga (yaitu x ≡ 7 (mod 11)) menjadi:

33 + 35k₂ ≡ 7 (mod 11) → 35k₂ ≡ -26 (mod 11) → k₂ ≡ 9 (mod 11) atau k₂ = 9 + 11k₃

Sulihkan k₂ ini ke dalam (iii) menghasilkan:

x = 33 + 35(9 + 11k₃) = 348 + 385k₃ 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 = m₁ · m₂ · m₃ = 5 · 7 · 11 = 385

Secara umum, solusi sistem kekongruenan linier adalah berbentuk

x = a₁M₁y₁ + a₂M₂y₂ + … + a_nM_ny_n

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

M₁ = 7 · 11 = 77, M₂ = 5 · 11 = 55, M₃ = 5 · 7 = 35

y₁ = 3 karena 77 · 3 ≡ 1 (mod 5)

y₂ = 6 karena 55 · 6 ≡ 1 (mod 7)

y₃ = 6 karena 35 · 6 ≡ 1 (mod 11)

maka solusi unik dari sistem kekongruenan tersebut adalah

x = a₁M₁y₁ + a₂M₂y₂ + … + a₃M₃Y₃

= 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