Persamaan Diophantine Olim Matik SMP

         Blog Koma - Hallow sahabat koma, bagaimana kabarnya hari ini? Semoga baik-baik saja ya. Pada artikel ini kita akan membahas tentang Persamaan Diophantine Olim Matik SMP yang disertai dengan contoh soal dan pembahasan beberapa soal lainnya untuk mendukung pemahaman materinya yang lebih mendalam. Persamaan Diophantine Olim Matik SMP ini adalah salah satu materi paling mendasar yang harus dipahami oleh sahabat koma.

A. Pengertian Persamaan Diophantine

       Misalkan terdapat bilangan bulat $ a, b, $ dan $ c $ dengan $ a \neq 0, b \neq 0 $, persamaan $ ax + by =c $ disebut Persamaan Diophantine jika penyelesaiannya adalah bilangan bulat ($x $ dan $ y $ bilangan bulat).

Teorema:
       Persamaan Diophantine $ ax + by = c $ memiliki penyelesaian jika dan hanya jika FPB (Faktor Persekutuan Terbesar) dari $ a $ dan $ b $ habis membagi $ c $.

B. Penyelesaian Persamaan Diophantine

(i). Menggunakan Modulo
       Untuk menyelesaikan persamaan diophantine $ ax+by=c $ dapat dilakukan dengan penyelesaian salah satu bentuk modulo $ ax \equiv c \, (mod \, b) $ atau $ by \equiv c \, (mod \, a) $, selanjutnya solusi dari modulo tersebut disubstitusikan ke persamaan awal.

Contoh 1:
Tentukan penyelesaian bulat dari persamaan $ 10x + 17y = 35 $.

(ii). Teorema Penyelesaian Umum
       Misalkan $ d = FPB(a, b) $ dan $ x_0 , y_0 $ merupakan penyelesaian awal persamaan diophantine $ ax + by = c $, maka penyelesaian umum persamaan diophantine tersebut yaitu:
       $ x = x_0 + \left( \frac{b}{d} \right) k $
       $ y = y_0 - \left( \frac{a}{d} \right) k $
dengan $ k $ bilangan bulat.

Contoh 2:
Tentukan penyelesaian umum dari persamaan diophantine $ 738x + 621y = 45 $?

Contoh 3:
Tentukan $ x $ dan $ y $ bulat positif yang memenuhi persamaan $ 7x + 5y = 100 $?

Contoh 4:
Tentukan solusi dari persamaan diophantine $ 15x + 12y + 30z = 24 $?

Contoh 5:
Terdapat bilangan bulat $ x $ dan $ y $ dengan $ x > 1 $ yang memenuhi persamaan $ 2007x - 21y = 1923 $. Tentukan nilai minimum dari $ 2x + 3y $?

Contoh 6:
Digit-digit $ a, b, c $ membentuk bilangan tiga digit $ \overline{abc} $ yang memenuhi persamaan $ 49a + 7b + c = 286 $. Tentukkan bilangan tiga digit tersebut.?

Contoh 7:
Terdapat persamaan $ \frac{4}{3} x - a = \frac{2}{5}x + 140 $ yang memiliki solusi bilangan bulat positif. tentukan nilai minimum dari $ a $?

Contoh 8:
Tentukan solusi bulat dari persamaan $ 13x - 7y = 0 $ yang juga memenuhi kondisi $ 80 < x + y < 120 $?

Contoh 9:
Tentukan semua tripel bilangan $ (x, y, z) $ non negatif yang memenuhi sistem persamaan:
$ 5x + 7y + 5z = 37 $
$ 6x - y - 10z = 3 $.

Pembahasan Contoh Soal-soal:

       Berikut ada beberapa soal yang berkaitan dengan materi Persamaan Diophantine Olim Matik SMP untuk menambah wawasan dalam pemahaman materinya. Silahkan dicoba dulu soal-soalnya, kemudian untuk mengecek jawabannya salah atau benar, bisa lihat solusi dengan mengklik tombol solusi di bagian bawah setiap soalnya.

Contoh Soal-soal dan Solusinya:

Contoh 1:
Tentukan penyelesaian bulat dari persamaan $ 10x + 17y = 35 $.

$\spadesuit $ Konsep Dasar
*). $ a \equiv b \, (mod \, m) \leftrightarrow a = b + mk $
*). $ a \equiv b \, (mod \, m) \leftrightarrow a \times p \equiv b \times p \, (mod \, m) $

$\clubsuit $ Pembahasan
*). Menyelesaikan bentuk modulo
Bentuk $ 10x + 17y = 35 $, kita dapat menyelesaikan salah satu dari $ 10x \equiv 35 \, (mod \, 17 ) $ atau $ 17y \equiv 35 \, (mod \, 10) $.
$ \begin{align} 17y & \equiv 35 \, (mod \, 10) \\ 7y & \equiv 5 \, (mod \, 10) \, \, \, \text{(kali 3)} \\ 21y & \equiv 15 \, (mod \, 10) \\ y & \equiv 5 \, (mod \, 10) \\ y & = 5 + 10k \end{align} $

*). Substitusi $ y = 5 + 10k $ ke $ 10x + 17y = 35 $:
$ \begin{align} 10x + 17y & = 35 \\ 10x + 17(5 + 10k) & = 35 \\ 10x + 85 + 170k & = 35 \\ 10x + 170k & = -50 \\ 10x & = -50 - 170k \\ x & = -5 - 17k \end{align} $
Sehingga penyelesaian dari $ 10x + 17y = 35 $ yaitu
$ x = -5 - 17k $ dan $ y = 5 + 10k $
dengan $ k $ bilangan bulat.

Jadi, solusi umumnya $ x = -5 - 17k $ dan $ y = 5 + 10k . \, \heartsuit $

Contoh 2:
Tentukan penyelesaian umum dari persamaan diophantine $ 738x + 621y = 45 $?

$\spadesuit $ Konsep Dasar
*). Algoritma Euclide
*). Teorema penyelesaian umum persamaan diophantine

$\clubsuit $ Pembahasan
*). Menentukan FPB dari 738 dan 621 menggunakan algoritma euclide:
$ \begin{align} 738 & = 1 \times 621 + 117 \\ 621 & = 5 \times 117 + 36 \\ 117 & = 3 \times 36 + 9 \\ 36 & = 4 \times 9 + 0 \end{align} $
sehingga FPB(738, 621) = 9. Karena 9 habis membagi 45, maka persamaan diophantine $ 738x + 621y = 45 $ memiliki penyelesaian.

*). Menentukan solusi awal dengan membalik algoritma euclide:
$ \begin{align} 9 & = 117 - 3 \times 36 \\ & = 117 - 3 \times (621 - 5 \times 117) \\ & = -3 \times 621 + 16 \times 117 \\ & = -3 \times 621 + 16 (738 - 1 \times 621 ) \\ 9 & = 16 \times 738 - 19 \times 621 \, \, \, \text{(kali 5)} \\ 45 & = 80 \times 738 - 95 \times 621 \\ 45 & = 738x + 621y \end{align} $
kita peroleh: $ x_0 = 80 $ dan $ y_0 = -95 $, serta $ d = 9 $.

*). Penyelesaian Umumnya yaitu:
$ x = x_0 + \left( \frac{b}{d} \right) k = 80 + \left( \frac{621}{9} \right) k = 80 + 69k $
$ y = y_0 - \left( \frac{a}{d} \right) k = -95 - \left( \frac{738}{9} \right) k = -95 - 82k $
dengan $ k $ bilangan bulat.

Jadi, solusinya $ x = 80 + 69k $ dan $ y = -95 - 82k . \, \heartsuit $

Contoh 3:
Tentukan $ x $ dan $ y $ bulat positif yang memenuhi persamaan $ 7x + 5y = 100 $?

$\spadesuit $ Konsep Dasar
*). Teorema penyelesaian umum persamaan diophantine

$\clubsuit $ Pembahasan
*). Menentukan solusi awal dari $ 7x + 5y = 100 $
FPB(7, 5) = 1. Karena 1 habis membagi 100, maka $ 7x + 5y = 100 $ memiliki penyelesaian.
Mudah dituliskan:
$ \begin{align} 1 & = 3 \times 7 - 4 \times 5 \, \, \, \text{(kali 100)} \\ 100 & = 300 \times 7 - 400 \times 5 \\ 100 & = 7x + 5y \end{align} $
artinya $ x_0 = 300 $ dan $ y_0 = -400 $ serta $ d = 1 $.

*). Penyelesaian Umumnya yaitu:
$ x = x_0 + \left( \frac{b}{d} \right) k = 300 + \left( \frac{5}{1} \right) k = 300 + 5k $
$ y = y_0 - \left( \frac{a}{d} \right) k = -400 - \left( \frac{7}{1} \right) k = -400 - 7k $
dengan $ k $ bilangan bulat.

*). Menentukan nilai $ k $ agar diperoleh Solusi positif
$ \begin{align} x & > 0 \rightarrow 300 + 5k > 0 \rightarrow k > -60 \\ y & > 0 \rightarrow -400 - 7k > 0 \rightarrow k < -57 \frac{1}{7} \end{align} $
kita peroleh: $ -60 < k < -57 \frac{1}{7} $
Nilai $ k = \{ -59, \, -58 \} $.

-). Untuk $ k = -59 $
$ x = 300 + 5k = 300 + 5(-59) = 300 - 259 = 5 $
$ y = -400 - 7k = -400 - 7(-59) = -400 + 413 = 13 $
-). Untuk $ k = -58 $
$ x = 300 + 5k = 300 + 5(-58) = 300 - 290 = 10 $
$ y = -400 - 7k = -400 - 7(-58) = -400 + 406 = 6 $

Jadi, solusinya $ (x, y) = \{ (5, 13) \, , (10, 6) \} . \, \heartsuit $

Contoh 4:
Tentukan solusi dari persamaan diophantine $ 15x + 12y + 30z = 24 $?

$\spadesuit $ Konsep Dasar
*). Algoritma Euclide
*). Teorema penyelesaian umum persamaan diophantine

$\clubsuit $ Pembahasan
*). Kita ubah $ 15x + 12y + 30z = 24 $ menjadi persamaan diophantine 2 variabel, misal kita pilih $ 12y + 30z = 6w $ sehingga menjadi $ 15x + 6w = 24 $.
*). FPB(15, 6) = 3, dan 3 membagi 24, sehingga $ 15x + 6w = 24 $ memiliki solusi bulat. Dengan mudah dapat ditentukan bahwa $ x_0 = 2 $ dan $ w_0 = -1 $ adalah salah satu solusi dari persamaan $ 15x + 6w = 24 $.
*). Solusi umum untuk $ x $ dan $ w $ yaitu:
$ x = x_0 + \left( \frac{b}{d} \right) k = 2 + \left( \frac{6}{3} \right) k = 2 + 2k $
$ w = w_0 - \left( \frac{a}{d} \right) k = -1 - \left( \frac{15}{3} \right) k = -1 - 5k $

*). Nilai $ w = -1 - 5k $ kita substitusi ke persamaan $ 12y + 30z = 6w $:
$ \begin{align} 12y + 30z & = 6w \\ 12y + 30z & = 6(-1 - 5k) \\ \end{align} $
FPB(12, 30) = 6, dimana 6 membagi $ 6(-1 - 5k) $.
$ 6 = 12 \times (-2) + 30 \times 1 $ ..... kali $(-1 - 5k) $
$ 6(-1 - 5k) = 12 \times (2 + 10k) + 30 \times (-1 - 5k) $
$ 6 (-1 - 5k) = 12y + 30 z $
artinya solusi awalnya $ y_0 = 2 + 10k $ dan $ z_0 = -1 - 5k $

*). Solusi umum untuk $ y $ dan $ z $ pada persamaan $ 12y + 30z = 6w $ yaitu:
$ y = y_0 + \left( \frac{b}{d} \right) t = (2 + 10k) + \left( \frac{30}{6} \right) t = 2 + 10k + 5t $
$ z = z_0 - \left( \frac{a}{d} \right) t = (-1 - 5k) - \left( \frac{12}{6} \right) t = -1 - 5k - 2t $
Dimana $ k $ dan $ t $ adalah bilangan bulat.

Jadi, solusinya $ x = 2 + 2k $, $ y = 2 + 10k + 5t $, dan $ z = -1 - 5k - 2t . \, \heartsuit $

Contoh 5:
Terdapat bilangan bulat $ x $ dan $ y $ dengan $ x > 1 $ yang memenuhi persamaan $ 2007x - 21y = 1923 $. Tentukan nilai minimum dari $ 2x + 3y $?

$\spadesuit $ Konsep Dasar
*). Bentuk $ \frac{a}{b} = \frac{m}{n} $, untuk $ a $ dan $ b $ positif, maka nilai minimum dari $ a $ dan $ b $ sama dengan $ a = m $ dan $ b = n $ dengan syarat FPB$(m,n)=1$.

$\clubsuit $ Pembahasan
*). Menyederhanakan dan mengubah soalnya:
$ \begin{align} 2007x - 21y & = 1923 \, \, \, \, \text{(bagi 3)} \\ 669x - 7y & = 641 \\ 669x - 7y & = 669 - 28 \\ 669x - 669 & = 7y - 28 \\ 669 ( x - 1) & = 7(y - 4) \\ \frac{x-1}{y-4} & = \frac{7}{669} \end{align} $
Karena $ x > 1 $ maka $ x - 1 > 0 $ dan $ y - 4 > 0 $.
Artinya $ x $ dan $ y $ minimum saat:
$ x - 1 = 7 \rightarrow x = 8 $
$ y - 4 = 669 \rightarrow y = 673 $

*). Menghitung nilai minimum dari $ 2x + 3y $
$ \begin{align} 2x + 3y & = 2 \times 8 + 3 \times 673 = 2043 \end{align} $

Jadi, nilai minimum $ 2x + 3y = 2043 . \, \heartsuit $

Catatan:
Soal ini bisa diselesaikan dengan konsep persamaan diophantine yaitu mencari solusi umumnya, kemudian gunakan batasan $ x > 1 $ untuk mencari batasan nilai $ k $.

Contoh 6:
Digit-digit $ a, b, c $ membentuk bilangan tiga digit $ \overline{abc} $ yang memenuhi persamaan $ 49a + 7b + c = 286 $. Tentukkan bilangan tiga digit tersebut.?

$\spadesuit $ Konsep Dasar
*). *). $ a \equiv b \, (mod \, m) \leftrightarrow a = b + mk $

$\clubsuit $ Pembahasan
*). Kita ambil modulo 7
$ \begin{align} 49a + 7b + c & = 286 \\ 49a + 7b + c & \equiv 286 \, (mod \, 7) \\ 0.a + 0.b + c & \equiv 6 \, (mod \, 7) \\ c & \equiv 6 \, (mod \, 7) \\ c & = 6 + 7k \end{align} $
Karena $ c $ sebuah digit bilangan, maka $ c = 6 $ saat $ k = 0 $.

*). Substitusi $ c = 6 $
$ \begin{align} 49a + 7b + c & = 286 \\ 49a + 7b + 6 & = 286 \\ 49a + 7b & = 280 \, \, \, \, \, \text{(bagi 7)} \\ 7a + b & = 40 \\ 7a & = 40 - b \end{align} $
Karena $ 0 \leq b \leq 9 $ , maka $ 31 \leq 40 - b \leq 40 $
$ \rightarrow 31 \leq 7a \leq 40 $
yang terpenuhi untuk $ 7a = 35 \rightarrow a = 5 $ dan $ b = 5 $.
Sehingga bilangannya yaitu 556.

Jadi, bilangannya adalah $ 556 . \, \heartsuit $

Contoh 7:
Terdapat persamaan $ \frac{4}{3} x - a = \frac{2}{5}x + 140 $ yang memiliki solusi bilangan bulat positif. tentukan nilai minimum dari $ a $?

$\spadesuit $ Konsep Dasar
*). Bentuk $ \frac{p}{a} $ bulat jika $ p $ kelipatan $ a $.

$\clubsuit $ Pembahasan
*). Mengubah soalnya:
$ \begin{align} \frac{4}{3} x - a & = \frac{2}{5}x + 140 \\ a & = \frac{4}{3} x - \frac{2}{5}x - 140 \\ & = \frac{20}{15} x - \frac{6}{15}x - 140 \\ & = \frac{14}{15} x - 140 \\ a & = 14 \left( \frac{x}{15} - 10 \right) \end{align} $
Agar $ a $ bulat positif, maka $ x $ harus kelipatan 15 dan $ \frac{x}{15} - 10 > 0 $.
Nilai minimum tercapai saat $ x = 165 $.
Sehingga $ a = 14 \left( \frac{165}{15} - 10 \right) = 14 \left( 11 - 10 \right) = 14 $

Jadi, nilai minimumnya $ a = 14 . \, \heartsuit $

Contoh 8:
Tentukan solusi bulat dari persamaan $ 13x - 7y = 0 $ yang juga memenuhi kondisi $ 80 < x + y < 120 $?

$\spadesuit $ Konsep Dasar
*). Bentuk $ \frac{a}{b} = \frac{m}{n} \rightarrow a = mk $ dan $ b = nk $

$\clubsuit $ Pembahasan
*). Mengubah soalnya:
$ \begin{align} 13x - 7y & = 0 \\ 13x & = 7y \\ \frac{x}{y} & = \frac{7}{13} \\ x & = 7k \, \text{ dan } \, y = 13k \end{align} $

*). Substitusi ke bentuk $ 80 < x + y < 120 $
$ \begin{align} 80 & < x + y < 120 \\ 80 & < 7k + 13k < 120 \\ 80 & < 20k < 120 \\ 4 & < k < 6 \end{align} $
sehingga $ k = 5 $ yang memenuhi.
$ x = 7k = 7 \times 5 = 35 $
$ y = 13k = 13 \times 5 = 65 $

Jadi, nilai $ x = 35 $ dan $ y = 65 . \, \heartsuit $

Contoh 9:
Tentukan semua tripel bilangan $ (x, y, z) $ non negatif yang memenuhi sistem persamaan:
$ 5x + 7y + 5z = 37 $
$ 6x - y - 10z = 3 $.

$\spadesuit $ Konsep Dasar
*). Teorema penyelesaian umum persamaan diophantine

$\clubsuit $ Pembahasan
*). Eliminasi variabel $ z $:
$\begin{array}{c|c|cc} 5x + 7y + 5z = 37 & \times 2 & 10x + 14y + 10z = 74 & \\ 6x - y - 10z = 3 & \times 1 & 6x - y - 10z = 3 & + \\ \hline & & 16x + 13y = 77 & \end{array} $

*). Menentukan solusi awal dari $ 16x + 13y = 77 $ :
$ \begin{align} 16x + 13y & = 77 \\ 16x + 13y & = 64 + 13 \\ 16x - 64 + 13y - 13 & = 0 \\ 16(x - 4) + 13(y - 1) & = 0 \end{align} $
Salah satu solusinya yaitu $ x_0 = 4 $ dan $ y_0 = 1 $.

*). Penyelesaian Umumnya yaitu:
$ x = x_0 + \left( \frac{b}{d} \right) k = 4 + \left( \frac{13}{1} \right) k = 4 + 13k $
$ y = y_0 - \left( \frac{a}{d} \right) k = 1 - \left( \frac{16}{1} \right) k = 1 - 16k $
dengan $ k $ bilangan bulat.

*). Menentukan batas nilai $ k $ dengan $ x, y $ bulat non negatif:
$ \begin{align} x \geq 0 \rightarrow 4 + 13k & \geq 0 \\ k & \geq -\frac{4}{13} \\ y \geq 0 \rightarrow 1 - 16k & \geq 0 \\ k & \leq \frac{1}{16} \end{align} $
artinya $ -\frac{4}{13} \leq k \leq \frac{1}{16} $
yang terpenuhi hanya saat $ k = 0 $.
Sehingga $ x = 4 + 13k = 4 + 13(0) = 4 $
$ y = 1 - 16k = 1 - 16(0) = 1 $

*). Menentukan nilai $ z $ dengan substitusi $ x = 4 $ dan $ y = 1 $:
$ \begin{align} 5x + 7y + 5z & = 37 \\ 5(4) + 7(1) + 5z & = 37 \\ 20 + 7 + 5z & = 37 \\ 5z & = 10 \\ z & = 2 \end{align} $

Jadi, solusinya $ (x, y, z) = (4, 1, 2) . \, \heartsuit $

Soal-soal Latihan

       Berikut ada beberapa soal Latihan yang berkaitan dengan materi Persamaan Diophantine Olim Matik SMP untuk menambah wawasan dalam pemahaman materinya. Semoga bermanfaat.

1). Tentukan penyelesaian umum dari persamaan diophantine $ 754x + 221y = 13 $

2). Tentukan penyelesaian bulat dari persamaan $ 25x + 13y + 7z = 6 $

3). Jika $ k $ sebuah bilangan bulat positif sehingga persamaa dalam variabel $ x $ yaitu $ kx - 12 = 3k $ mempunyai solusi bulat, maka ada berapa banyak bilangan $ k $?

4). Tentukan salah satu solusi bilangan bulat positif dari persamaan $ 1990x - 1989y = 1991 $

5). Dua bilagnan bulat positif $ A $ dan $ B $ memenuhi persamaan $ \frac{A}{11} + \frac{B}{3} = \frac{17}{333} $. Tentukan nilai $ A^2 + B^2 $?

6). Tentukan banyak tripel bilangan $ (x, y, z) $ bilangan bulat non negatif yang memenuhi persamaan $ x + 2y + 5z = 100 $.

7). Tentukan penyelesaian tripel bilangan $ (x, y, z) $ bilangan bulat non negatif yang memenuhi sistem persamaan
$ 15x + 9y + z = 300 $
$ x + y + z = 100 $.

8). Misalkan $ x, y, $ dan $ z $ adalah bilagnan bulat positif sehingga $ x > y > z > 663 $ dan memenuhi:
$ x + y + z = 1998 $
$ 2x + 3y + 4z = 5992 $
Tentukan nilai $ x, y, $ dan $ z $.


Untuk Solusi Soal Latihan ini, silahkan ikuti link berikut ya:
Solusi Soal Latihan Persamaan Diophantine Olim Matik SMP.


Berikut Link Latihan Soal Pemantapan:
1). Soal Review Materi
2). Soal Latihan Timer A
3). Soal Latihan Timer B


Kembali ke Daftar Isi Olimpiade Matik SMP

       Demikian pembahasan materi Persamaan Diophantine Olim Matik SMP dan contoh-contohnya. Silahkan juga baca materi lain yang berkaitan dengan materi ini. Setiap artikel akan diupdate secara bertahap. Jika ada kritik dan saran, atau koreksi dari isi artikel di halaman ini, mohon bantuannya untuk menuliskannya di kolom komentar di bagian bawah setiap artikel. Ini sangat membantu untuk memperbaiki kualitas dari artikel di blog koma. Semoga bermanfaat. Terimakasih.