PERSAMAAN DIOPHANTINE

Download Tayangan

Persamaan Diophantine adalah persamaan matematika yang memiliki solusi bilangan bulat. Persamaan ini dinamai dari seorang matematikawan Yunani kuno bernama Diophantus, yang menulis buku “Arithmetica” yang membahas tentang masalah matematika, termasuk persamaan Diophantine.

Salah satu contoh persamaan Diophantine sederhana adalah:

    \[3x+7y=1.\]

Solusi untuk persamaan ini adalah x = -2 dan y = 1, karena 3(-2) + 7(1) = 1.

Persamaan Diophantine banyak digunakan dalam berbagai bidang ilmu seperti teori bilangan, kriptografi, dan optimasi kombinatorial. Dalam artikel ini, kita akan membahas tentang persamaan Diophantine linear.

Persamaan Diophantine linear memiliki bentuk umum sebagai berikut:

    \[a_1 x_1 + a_2 x_2 + \cots + a_n x_n = c,\]

dengan a_1, a_2, \dots, a_n, c, x_1, x_2, \dots, x_n adalah bilangan bulat. Tujuannya adalah mencari solusi x_1, x_2, \cdots, x_n yang memenuhi persamaan tersebut.

Contoh persamaan Diophantine linear adalah:

    \[5x+8y - 24.\]

Solusi untuk persamaan ini adalah x = 8 dan y = -3, karena 5(8) + 8(-3) = 24.

Untuk mencari solusi dari persamaan Diophantine linear, kita dapat menggunakan algoritma Euclidean untuk menentukan faktor persekutuan terbesar (FPB) dari a_1, a_2, \dots, a_n. Jika FPB dari a_1, a_2, \dots, a_n tidak membagi habis c, maka persamaan tidak memiliki solusi. Namun, jika FPB dari a_1, a_2, \dots, a_n membagi habis c, maka persamaan memiliki solusi dan kita dapat menggunakan algoritma Extended Euclidean untuk mencari solusinya.

Algoritma Extended Euclidean akan menghasilkan nilai-nilai s_1, s_2, \dots, s_n dan t_1, t_2, \dots, t_n yang memenuhi persamaan:

    \[a_1 s_1 + a_2 s_2 + \dots + a_n s_n = FPB(a_1, a_2, \dots, a_n ).\]

Dengan menggunakan nilai-nilai s_1, s_2, \dots, s_n dan t_1, t_2, \dots, t_n, kita dapat menentukan solusi dari persamaan Diophantine linear.

Tutorial: Soal Latihan dan Pembahasan Persamaan Diophantine