Persamaan Diophantine adalah persamaan polinomial yang umumnya memuat dua atau lebih variabel dengan solusi berupa bilangan bulat. Ada beberapa jenis persamaan Diophantine, di antaranya persamaan linear Diophantine (misalnya $ax + by = c$) yang sering menjadi kajian dalam teori bilangan. Kata “Diophantine” sendiri diambil dari nama Diophantus, ahli matematika asal Alexandria. Beliau mempelajari dan merumuskan teorema terkait persamaan seperti itu.
Persamaan linear Diophantine, khususnya, dapat diselesaikan secara analitis menggunakan bantuan algoritma Euclides. Oleh karena itu, sebaiknya dipelajari terlebih dahulu mengenai algoritma tersebut pada tautan di bawah.
Baca: Materi, Soal, dan Pembahasan – Algoritma Euclides
Ketika kita diminta untuk mencari banyaknya segitiga siku-siku yang panjang sisinya berukuran bilangan bulat, itu artinya kita diminta untuk menyelesaikan persamaan kuadrat Diophantine berbentuk $a^2 + b^2 = c^2$. Khusus pada persamaan linear Diophantine berbentuk $ax + by = c$, penyelesaiannya ada jika dan hanya jika $\text{FPB}(a, b)$ membagi habis $c$. Hal ini berdasarkan pada identitas Bézout berikut.
Identitas Bézout (Bézout’s Identity)
Sebagai contoh, diberikan persamaan linear $8x + 12y = 15.$ Dapat dengan mudah dicari bahwa $\text{FPB}(8, 12) = 4$. Karena $4$ tidak membagi habis $15$, persamaan linear di atas bukan persamaan Diophantine karena tidak memiliki solusi bilangan bulat. Dengan kata lain, tidak akan ditemukan bilangan bulat $x$ dan $y$ sehingga persamaan tersebut terpenuhi.
Beda halnya kalau bilangan $15$ diganti menjadi $-4$, misalnya, menjadi $8x + 12y = -4$. Karena $-4$ membagi habis $4$, persamaan tersebut termasuk persamaan Diophantine. Salah satu solusi bilangan bulatnya adalah $x = 1$ dan $y = -1$. Nah, hal yang menjadi perhatikan kita di sini adalah mencari solusi bilangan bulat tersebut tanpa menebak-nebak.
Bagaimana dengan persamaan yang memuat bentuk faktorial atau eksponensial? Apakah persamaan seperti $x! + y! = z!$ dan $3^x-7=x^2$ termasuk dalam persamaan Diophantine? Sejumlah orang mungkin memiliki pendapat yang berbeda-beda. Namun secara umum, persamaan yang memiliki penyelesaian bilangan bulat tetap kita sebut sebagai persamaan Diophantine.
Pada tahun 1900, David Hilbert (1862–1943), matematikawan Jerman, mengusulkan persoalan mendasar kesepuluh (tenth fundamental problem) miliknya: Carilah suatu algoritma untuk menentukan apakah suatu persamaan Diophantine dengan koefisien bilangan bulat memiliki solusi atau tidak. Pada tahun 1970, Yuri Matiyasevich (1947), matematikawan Rusia, membuktikan bahwa algoritma seperti itu tidak akan pernah ada dan ini akan tetap menjadi kelemahan kita bersama dalam menyelesaikan persoalan seperti itu.
Persamaan Diophantine seperti $a^3+a+1 = 3^b$ sebetulnya dapat diselesaikan (ya, tebak saja, $a = 1$ dan $b = 1$), tetapi bisa jadi memakan waktu yang lama. Sampai sekarang belum ditemukan metode/cara yang pasti untuk menemukan penyelesaian bilangan bulat dari persamaan eksponensial Diophantine seperti itu. Ketika diberikan persoalan mengenai persamaan Diophantine yang nonlinear, kita dapat memanfaatkan cara-cara umum yang biasa dipakai, misalnya aturan keterbagian, melengkapi kuadrat sempurna, diskriminan, sifat eksponen, pemfaktoran, pembatasan pada selang, dan sebagainya. Sebagai contohnya, akan diberikan pada soal-soal di bawah.
Kemungkinan solusi persamaan Diophantine ada $4$, yaitu:
- Tidak memiliki solusi.
- Hanya ada $1$ solusi.
- Lebih dari $1$ solusi dan berhingga.
- Memiliki solusi sebanyak takhingga sehingga memunculkan istilah “solusi umum”.
Teorema Diophantine
Bukti:
($\Rightarrow$) Akan dibuktikan bahwa jika $ax + by = c$ memiliki solusi, maka $\text{FPB}(a,b)~|~c$. Berdasarkan identitas Bézout, persamaan $ax + by = \text{FPB}(a, b)$ memiliki solusi bulat. Misalkan $\text{FPB}(a, b) = m$ dan $c = km$, maka $ax + by = m$ dapat ditulis menjadi $a(kx) + b(ky) = km = c$ dan jelas memiliki solusi bulat.
($\Leftarrow$) Akan dibuktikan bahwa jika $\text{FPB}(a,b)~|~c$, maka $ax + by = c$ memiliki solusi. Misal $m = \text{FPB}(a,b)$, berarti $m~|~c$. Karena itu, $c = km$, untuk suatu bilangan bulat $k$. Karena $m = \text{FPB}(a,b)$, maka untuk suatu bilangan bulat $k, t, s$, berlaku
$$\begin{aligned} at + bs & = m \\ kat + kbs & = km \\ a(kt) + b(ks) & = c \end{aligned}$$Berarti $x = kt$ dan $y = ks$ sehingga $x$ dan $y$ merupakan bilangan bulat.
Khusus pada persamaan linear Diophantine berlaku aturan berikut:
Diberikan bilangan bulat $k$ dan $x_0, y_0$ merupakan salah satu penyelesaian persamaan linear Diophantine $ax+by=c$, maka penyelesaian umumnya dinyatakan oleh
$$\begin{cases} x & = x_0+\dfrac{b}{\text{FPB}(a, b)} \cdot k \\ y & = y_0-\dfrac{a}{\text{FPB}(a, b)} \cdot k. \end{cases}$$
Quote by Joel Spencer
Bagian Pilihan Ganda
Soal Nomor 1
Dalam suatu pertandingan bola basket, seorang pemain dapat melakukan tembakan $2$ poin dan tembakan $3$ poin. Jika total poin yang didapat oleh satu tim adalah $20$ poin, berapa banyak dari skenario berikut yang mungkin terjadi?
$$\begin{array}{ccc} \hline \text{Skenario} & \text{Tembakan 2 poin} & \text{Tembakan 3 poin} \\ \hline A & 3 & 5 \\ B & 4 & 4 \\ C & 8 & 1 \\ D & 10 & 0 \\ E & 1 & 6 \\ \hline \end{array}$$A. $1$ C. $3$ E. $5$
B. $2$ D. $4$
Misalkan banyak tembakan $2$ poin dan tembakan $3$ poin yang terjadi berturut-turut adalah $M$ dan $N.$ Dengan demikian, diperoleh persamaan linear Diophantine
$$2M + 3N = 20.$$Periksa setiap skenario berdasarkan nilai $M$ dan $N$ yang memenuhi persamaan tersebut.
Skenario $A$: $2(3) + 3(5) = 21$
Skenario $B$: $2(4)+ 3(4) = 20~~\checkmark$
Skenario $C$: $2(8) + 3(1) = 19$
Skenario $D$: $2(10) + 3(0) = 20~~\checkmark$
Skenario $E$: $2(1) + 3(6) = 20~~\checkmark$
Jadi, ada $\boxed{3}$ skenario yang mungkin terjadi agar menghasilkan total $20$ poin.
(Jawaban C)
Soal Nomor 2
Banyaknya pasangan bilangan asli $(x, y)$ yang memenuhi $x + 2y = 100$ adalah $\cdots \cdot$
A. $33$ C. $50$ E. $100$
B. $49$ D. $80$
Persamaan di atas menunjukkan bahwa selama nilai $y$ bulat, nilai $x$ juga akan bulat.
Nilai $y$ terkecil yang mungkin dipilih adalah $y = 1$ (bilangan asli), sedangkan nilai $y$ terbesarnya adalah $y = 49$. Masing-masing nilai $y$ menghasilkan bilangan asli $x$. Ini artinya, akan ada $\boxed{49}$ pasangan $(x, y)$ yang terbentuk.
(Jawaban B)
Soal Nomor 3
Banyaknya pasangan bilangan bulat positif $(a, b)$ yang memenuhi $a^4+b = 1.600.000.001$ adalah $\cdots \cdot$
A. $50$ C. $150$ E. $201$
B. $100$ D. $200$
Perhatikan bahwa
$$\begin{aligned} a^4+b & = 1.600.000.001 \\ a^4 + b & = 1.600.000.000 + 1 \\ a^4+b & = 16 \cdot 10^8 + 1 && (\text{Bentuk baku}) \\ a^4+b & = 2^4 \cdot 10^8 + 1 \\ a^4+b & = (2 \cdot 10^2)^4 + 1 \\ a^4+b & = 200^4 + 1. \end{aligned}$$Persamaan terakhir menunjukkan bahwa nilai $a$ terbesar yang mungkin adalah $200$. Oleh karena itu, dapat dibuat tabel berikut.
$$\begin{array}{|c|c|} \hline \text{Nilai}~a & \text{Nilai}~b \\ \hline 200 & 1 \\ \hline 199 & \text{Sekian} \\ \hline 198 & \text{Sekian} \\ \hline \vdots & \vdots \\ \hline 1 & \text{Sekian} \\ \hline \end{array}$$Catatan: Sekian pada tabel di atas memiliki arti bahwa nilai $b$ ada dan berupa bilangan asli, tetapi tidak perlu dicari berapa nilainya.
Jadi, akan ada $200$ pasangan bilangan bulat positif $(a, b)$ yang memenuhi persamaan tersebut.
(Jawaban D)
Soal Nomor 4
Banyak pasangan bilangan bulat $(x, y)$ yang memenuhi $1+\dfrac{2}{x}+\dfrac{3}{y}=0$ adalah $\cdots \cdot$
A. $3$ C. $6$ E. $9$
B. $4$ D. $8$
Perhatikan bahwa dengan mengalikan kedua ruas persamaan di atas dengan $xy$, kita peroleh
$$\begin{aligned} xy\left(1+\dfrac{2}{x}+\dfrac{3}{y}\right) & = xy(0) \\ xy + 2y + 3x & = 0 \\ (x + 2)(y+3)-6 & = 0 \\ (x+2)(y+3) & = 6. \end{aligned}$$Persamaan terakhir menunjukkan bahwa $(x+2)$ dan $(y+3)$ merupakan faktor dari $6$. Karena faktor dari $6$ ada sebanyak delapan, yaitu $\pm 1, \pm 2, \pm 3$, dan $\pm 6$, akan ada $8$ pasangan bilangan bulat $(x, y)$ yang memenuhi persamaan itu.
(Jawaban D)
Soal Nomor 5
Banyaknya pasangan bilangan asli $(x, y)$ yang memenuhi persamaan $\sqrt{x}-\sqrt{17} = \sqrt{y}$ adalah $\cdots \cdot$
A. $0$ D. $3$
B. $1$ E. takhingga
C. $2$
Diketahui $\sqrt{x}-\sqrt{17} = \sqrt{y}$.
Kuadratkan kedua ruas, kita peroleh
$$\begin{aligned} \left(\sqrt{x}-\sqrt{17}\right)^2 & = \left(\sqrt{y}\right)^2 \\ x-2\color{red}{\sqrt{17x}} + 17 & = y. \end{aligned}$$Agar diperoleh bilangan asli $y$, haruslah $x = 17n^2$ untuk suatu bilangan bulat $n \geq 2$ ($n = 1$ menyebabkan nilai $y$ negatif).
Substitusi $x = 17n^2$, kita peroleh
$$\begin{aligned} y & = 17n^2-2\sqrt{17(17n^2)} + 17 \\ & = 17n^2-34n+17 \\ & = 17(n^2-2n+1) \\ & = 17(n-1)^2. \end{aligned}$$Karena bilangan bulat $n \geq 2$ ada sebanyak takhingga, juga akan ada takhingga pasangan bilangan asli $(x, y)$ yang memenuhi persamaan tersebut.
(Jawaban E)
Soal Nomor 6
Jika $m-1 = \dfrac{15}{n}$ dengan $m$ dan $n$ berupa bilangan bulat, maka banyak nilai $m$ yang mungkin adalah $\cdots \cdot$
A. $12$ C. $9$ E. $6$
B. $10$ D. $8$
Diketahui $m-1 = \dfrac{15}{n}$. Agar $m$ bulat, $m-1$ juga harus bulat. Akibatnya, $\dfrac{15}{n}$ juga harus bulat sehingga $n$ harus merupakan faktor dari $15$, yaitu $\{\pm 1, \pm 3, \pm 5, \pm 15\}$. Jadi, ada $8$ nilai $n$ yang mungkin. Dengan kata lain, nilai $m$ yang mungkin juga ada $\boxed{8}$
(Jawaban D)
Soal Nomor 7
Untuk $x$ dan $y$ anggota bilangan bulat, solusi dari $2x-2y-xy-12=0$ ada sebanyak $\cdots$ pasang.
A. $1$ C. $5$ E. $10$
B. $2$ D. $8$
Diketahui $\color{red}{2x-2y-xy}-12 =0$. Perhatikan bahwa bentuk pada ruas kiri dapat kita faktorkan dengan memperhatikan nilai konstanta.
$$\begin{aligned} \color{red}{\left[(x + 2)(-y + 2)-4\right]}-12 & = 0 \\ (x+2)(-y+2) & = 16 \\ x+2 & = \dfrac{16}{-y+2} \\ x & = \dfrac{16}{-y+2}-2. \end{aligned}$$Nilai $x$ akan bulat ketika bentuk $(-y+2)$ merupakan faktor bulat dari $16$, yaitu $\{\pm 1, \pm 2, \pm 4, \pm 8, \pm 16\}$. Ini artinya, akan ada $10$ nilai $y$ yang memenuhi, begitu juga dengan pasangannya, yaitu $x$. Jadi, ada $\boxed{10}$ pasang nilai $(x, y)$ anggota bilangan bulat yang memenuhi persamaan tersebut.
(Jawaban E)
Soal Nomor 8
Bilangan asli $x$ dan $y$ memenuhi $x^3+4x^3y^3 = 827 + 8y^3$. Nilai $4xy = \cdots \cdot$
A. $18$ C. $27$ E. $32$
B. $24$ D. $28$
Persamaan di atas termasuk persamaan Diophantine (nonlinear) karena memiliki solusi bilangan bulat (ingat bahwa bilangan asli juga termasuk bilangan bulat).
Cara untuk menyelesaikan persamaan seperti ini adalah dengan menggunakan pemfaktoran.
$$\begin{aligned} x^3+4x^3y^3 & = 827 + 8y^3 \\ 4x^3y^3+x^3-8y^3 & = 827 \\ (x^3-2)(4y^3+1)+2 & = 827 \\ (x^3-2)(4y^3+1) & = 825 \\ (x^3-2)(4y^3+1) & = 3 \cdot 5^2 \cdot 11. \end{aligned}$$Berdasarkan persamaan terakhir, kita peroleh bahwa $(x^3-2)$ dan $(4y^3+1)$ keduanya merupakan faktor dari $825$. Oleh karena itu, kita harus temukan dua bilangan yang dikalikan menghasilkan $825$, sekaligus memenuhi $x, y$ bilangan asli.
Dari bentuk $x^3-2$, nilai-nilai yang mungkin agar $x$ bilangan asli adalah $-1, 6, 25, 62$, dan seterusnya. Karena $25$ adalah salah satu faktor dari $825$, kita dapat mengatakan bahwa $x^3-2 = 25$, berakibat $x = 3$. Ini juga menunjukkan bahwa $4y^3+1 = 3 \cdot 11 = 33$, berakibat $y = 2$. Keduanya ternyata bilangan asli.
Dengan demikian, nilai dari $\boxed{4xy = 4(3)(2) = 24}$
(Jawaban B)
Soal Nomor 9
Banyaknya pasangan bilangan bulat $(m, n)$ dengan $mn \geq 0$ yang memenuhi persamaan $m^3+n^3+99mn=33^3$ adalah $\cdots \cdot$
A. $33$ C. $36$ E. $100$
B. $34$ D. $99$
Perhatikan bahwa
$$\begin{aligned} (m+n)^3 & = m^3+3m^2n+3mn^2+n^3 \\ & = m^3+n^3+3mn(m+n). \end{aligned}$$Persamaan pada soal dapat ditulis sebagai berikut.
$$\begin{aligned} m^3+n^3& = 33^3-99mn \\ (m+n)^3-3mn(m+n) & = 33(33^2-33mn) \\ \text{Faktorkan}~(m+n)&~\text{pada ruas kiri} \\(m+n)((m+n)^2-3mn) & = 33(33^2-33mn). \end{aligned}$$Persamaan terakhir menunjukkan bahwa $m+n = 33$.
Adapun pasangan bilangan bulat $(m, n)$ yang memenuhi persamaan $m+n=33$ dengan $mn \geq 0$ adalah $(0, 33)$, $(1, 32)$, $(2, 31)$, $\cdots$, $(33, 0)$.
Jadi, ada $\boxed{34}$ pasangan bilangan bulat $(m, n)$ yang memenuhi persamaan itu.
(Jawaban B)
Soal Nomor 10
Berapa banyak pasangan bilangan bulat positif $(a, b)$ yang memenuhi $a^b = 64$?
A. $1$ C. $3$ E. $5$
B. $2$ D. $4$
Perhatikan bahwa $64 = 2^6$ (bentuk faktorisasi prima) dan hanya $2$ sebagai faktor primanya, maka $a$ pasti merupakan bentuk pangkat dari $2$. Misalkan $a = 2^n$, maka $a^b = (2^n)b = 2^{nb}$ sehingga kita peroleh $nb = 6.$
Ini menunjukkan bahwa $n$ adalah faktor dari $6$, yaitu $\{1, 2, 3, 6\}.$ Kita dapat tuliskan $64 = 2^6 = 4^3 = 8^2 = 64^1.$
Jadi, akan ada $\boxed{4}$ pasangan bilangan bulat positif $(a, b)$ yang memenuhi.
(Jawaban D)
Soal Nomor 11
Jumlah semua bilangan bulat positif $b$ sehingga $b^2=a^3+1$ dengan $a$ bilangan prima adalah $\cdots \cdot$
A. $3$ C. $5$ E. $11$
B. $4$ D. $8$
Kita bagi menjadi dua kasus.
Kasus 1: $b$ ganjil
Jika $b$ ganjil, maka akibatnya $b^2$ juga ganjil. Ruas kanan $a^3+1$ akan bernilai ganjil bila $a$ genap. Satu-satunya bilangan prima yang genap adalah $2$. Jadi, kita peroleh $a = 2$ dan $b = 3$.
Kasus 2: $b$ genap
Perhatikan bahwa $b^2=a^3+1$ dapat ditulis menjadi
$$\begin{aligned}b^2-1 & =a^3 \\ (b+1)(b-1) & = a^3. \end{aligned}$$Karena $\text{FPB}(b+1, b-1) = \text{FPB}(b+1, \color{red}{2})$, itu berarti $(b+1)$ dan $(b-1)$ saling relatif prima.
Catatan: Bilangan $\color{red}{2}$ di atas didapat dari selisih $b+1$ dan $b-1$.
Karena $a$ bilangan prima, satu-satunya bentuk perkalian bilangan yang relatif prima dengan $a^3$ adalah $1 \times a^3$, atau ditulis $(b-1)(b+1) = 1 \times a^3.$
Ini menunjukkan $b-1 = 1$, atau didapat $b = 2$, dan akibatnya $a^3 = 3.$ Tidak ada solusi untuk nilai $a$ jika $b$ genap.
Jadi, satu-satunya nilai $b$ adalah $3$ sehingga jumlah semua nilai $b$ tetap $\boxed{3}$
(Jawaban A)
Soal Nomor 12
Sistem persamaan $$\begin{cases} x+y+2z & = 10 \\ 3x-y+z & = 5 \end{cases}$$ memiliki penyelesaian bilangan bulat nonnegatif untuk $x, y$, dan $z$. Jumlah dari semua nilai bilangan bulat nonnegatif $x$ yang memenuhi sistem itu adalah $\cdots \cdot$
A. $3$ C. $7$ E. $11$
B. $5$ D. $9$
Diketahui $$\begin{cases} x+y+2z & = 10 && (\cdots 1) \\ 3x-y+z & = 5 && (\cdots 2) \end{cases}$$Penjumlahan kedua persamaan itu menghasilkan
$$\begin{aligned} 4x+3z & = 15 \\ 3z & = 15-4x \\ z & = 5-\dfrac43x \end{aligned}$$Substitusi $z$ pada Persamaan $(2)$.
$$\begin{aligned} 3x-y+z & = 5 \\ y & = 3x+z-5 \\ y & = 3x+\left(5-\dfrac43x\right)-5 \\ y & = 3x-\dfrac43x = \dfrac{5}{3}x \end{aligned}$$Kita peroleh $(x, y, z) = \left(x, \dfrac53x, 5-\dfrac43x\right)$. Agar diperoleh penyelesaian bilangan bulat nonnegatif, pilih $\color{blue}{x = 0}$ dan $\color{blue}{x = 3}$, masing-masing menghasilkan $(0, 0, 5)$ dan $(3, 5, 1)$. Jadi, jumlah semua nilai bilangan bulat negatif $x$ yang memenuhi sistem adalah $\boxed{0+5=5}$
(Jawaban B)
Soal Nomor 13
Petugas suatu kantor pos menjual prangko dengan $3$ jenis berbeda berdasarkan harganya, yaitu $25$ sen, $10$ sen, dan $5$ sen. Jika kita ingin membeli $20$ prangko dengan total harga $2$ dolar, berapa banyak kombinasi $3$ jenis prangko yang dapat dibeli?
Catatan: Kita dimungkinkan untuk tidak membeli satu jenis prangko sama sekali.
A. $4$ C. $6$ E. $8$
B. $5$ D. $7$
Misalkan $x, y, z$ berturut-turut menyatakan banyak prangko seharga $25$ sen, $10$ sen, dan $5$ sen, dengan $x, y, z$ berupa bilangan cacah.
Masalah di atas dapat dinyatakan sebagai sistem persamaan linear Diophantine berikut.
$$\begin{cases} x + y + z & = 20 && (\cdots 1) \\ 25x + 10y + 5z & = 200 && (\cdots 2) \end{cases}$$Keterangan: $1$ dolar = $100$ sen.
Persamaan $(2)$ dibagi $5$, lalu dikurangkan dengan Persamaan $(1)$, kita peroleh
$$4x + y = 20 \Rightarrow y = 20-4x$$Substitusikan pada Persamaan $(1)$, didapat
$$\begin{aligned} x + \color{red}{y} + z & = 20 \\ x + (20-4x) + z & = 20 \\ -3x + 20 + z & = 20 \\ z & = 3x. \end{aligned}$$Karena $z = 3x$ dan $y = 20-4x$, nilai $x$ terbatas pada interval $0 \leq x \leq 5.$
Untuk masing-masing keenam nilai $x$ tersebut, kita akan peroleh nilai $y$ dan $z$. Ini artinya, ada $\boxed{6}$ kombinasi berbeda untuk membeli prangko tersebut.
(Jawaban C)
Soal Nomor 14
Suatu pabrik mempekerjakan $20$ orang untuk menjalankan usaha produksinya. Gaji mingguan yang diterima oleh pekerja pria adalah $3$ shilling, pekerja wanita $2$ shilling, dan khusus untuk pemagang diberi gaji setengah shiling. Jika beban gaji untuk $20$ orang tersebut selama seminggu adalah $20$ shilling dan pabrik itu setidaknya mempekerjakan seorang pria dan seorang wanita, maka banyak pemagang di pabrik itu adalah $\cdot$ orang.
Catatan: Shilling adalah nama mata uang di negara persemakmuran Inggris.
A. $1$ C. $9$ E. $14$
B. $5$ D. $12$
Misalkan $x, y, z$ berturut-turut menyatakan banyak pekerja pria, pekerja wanita, dan pemagang, dengan $x, y, z$ berupa bilangan cacah dan $x, y \geq 1$.
Masalah di atas dapat dinyatakan sebagai sistem persamaan linear Diophantine berikut.
$$\begin{cases} x + y + z & = 20 && (\cdots 1) \\ 3x + 2y + \dfrac12z & = 20 && (\cdots 2) \end{cases}$$Persamaan $(1)$ dikali $2$, lalu dikurangkan dengan Persamaan $(2)$, kita peroleh
$$\begin{aligned} 5x + 3y & = 20 \\ 3y & = 20-5x \\ y & = \dfrac13(20-5x) \end{aligned}$$Substitusikan pada Persamaan $(2)$, didapat
$$\begin{aligned} x + \color{red}{y} + z & = 20 \\ x + \dfrac13(20-5x) + z & = 20 \\ \dfrac{3x}{3}+\dfrac13(20-5x)+z & = \dfrac{60}{3} \\ \dfrac13(20-2x) + z & = \dfrac{60}{3} \\ z & = \dfrac{60-20+2x}{3} \\ z & = \dfrac{40+2x}{3} \end{aligned}$$Karena $y = \dfrac13(20-5x) = \dfrac53(4-x),$ haruslah $(4-x)$ haruslah berkelipatan $3$, yaitu $x = 1$ atau $x = 4.$ Namun bila dipilih $x = 4,$ berakibat $y = 0,$ padahal $y \geq 1.$
Dengan demikian, nilai $x = 1$, mengimplikasikan $y = 5$ dan $z = 14$. Jadi, banyak pemagang di pabrik itu adalah $\boxed{14}$ orang.
(Jawaban E)
Bagian Uraian
Soal Nomor 1
Dengan menggunakan algoritma Euclides, tentukan solusi khusus dari persamaan linear Diophantine berikut.
a. $17x + 13y = 200$
b. $21x + 15y = 93$
c. $60x + 42y = 104$
d. $588x + 234y = 63$
Jawaban a)
Diketahui $17x + 13y = 200$.
Dengan menggunakan algoritma Euclides, kita peroleh
$$\begin{aligned} 17 & = 1 \times 13 + 4 \\ 13 & = 3 \times 4 + \color{red}{1} \\ 4 & = 4 \times 1 + 0 \end{aligned}$$Diperoleh $\text{FPB}(17, 13) = 1$. Karena $1$ habis membagi $200$, persamaan itu memiliki solusi bulat.
Dengan menggunakan pembalikan algoritma Euclides, didapat
$$\begin{aligned} 1 & = 13-3 \times 4 \\ 1 & = 13-3 \times (17-1 \times 13) \\ 1 & = -3 \times 17 + 4 \times 13 \\ \text{Kedua}&~\text{ruas dikalikan}~200 \\ 200 & = -600 \times 17 + 800 \times 13 \end{aligned}$$Jadi, solusi khusus persamaan tersebut bila dicari menggunakan algoritma Euclides adalah $x_0 = -600$ dan $y_0 = 800$.
Jawaban b)
Diketahui $21x + 15y = 93$, dapat disederhanakan menjadi $7x + 5y = 31$.
Dengan menggunakan algoritma Euclides, kita peroleh
$$\begin{aligned} 7 & = 1 \times 5 + 2 \\5 & = 2 \times 2 + \color{red}{1} \\ 2 & = 2 \times 1 + 0 \end{aligned}$$Diperoleh $\text{FPB}(7, 5) = 1$. Karena $1$ habis membagi $31$, persamaan itu memiliki solusi bulat.
Dengan menggunakan pembalikan algoritma Euclides, didapat
$$\begin{aligned} 1 & = 5-2 \times 2 \\ 1 & = 5-2 \times (7-1 \times 5) \\ 1 & = -2 \times 7 + 3 \times 5 \\ \text{Kedua}&~\text{ruas dikalikan}~31 \\ 31 & = -62 \times 7 + 93 \times 5 \end{aligned}$$Jadi, solusi khusus persamaan tersebut bila dicari menggunakan algoritma Euclides adalah $x_0 = -62$ dan $y_0 = 93$.
Jawaban c)
Diketahui $60x + 42y = 104$, dapat disederhanakan menjadi $30x + 21y = 52$.
Dengan menggunakan algoritma Euclides, kita peroleh
$$\begin{aligned} 30 & = 1 \times 21 + 9 \\ 21 & = 2 \times 9 + \color{red}{3} \\ 9 & = 3 \times 3 + 0 \end{aligned}$$Diperoleh $\text{FPB}(30, 21) = 3$. Karena $3$ tidak habis membagi $52$, persamaan itu tidakcmemiliki solusi bulat.
Jawaban d)
Diketahui $588x + 234y = 63$, dapat disederhanakan menjadi $196x + 78y = 21$.
Dengan menggunakan algoritma Euclides, kita peroleh
$$\begin{aligned} 196 & = 2 \times 78 + 40 \\ 78 & = 1 \times 40 + 38 \\ 40 & = 1 \times 38 + \color{red}{2} \\ 38 & = 19 \times 2 + 0 \end{aligned}$$Diperoleh $\text{FPB}(196, 78) = 2$. Karena $2$ tidak habis membagi $21$, persamaan itu tidak memiliki solusi bulat.
Soal Nomor 2
Periksa apakah persamaan linear berikut memiliki solusi bulat atau tidak.
$$17x-34y = 2$$
Ada $2$ pendekatan yang dapat dipakai untuk menyelesaikan persoalan ini.
Menggunakan identitas Bézout:
Perhatikan bahwa $\text{FPB}(17, 34) = 17$ dan $17$ tidak habis membagi $2$ sehingga persamaan tersebut tidak memiliki solusi bulat.
Menggunakan keterbagian:
Persamaan di atas dapat ditulis kembali menjadi
$$\begin{aligned} 17x & = 34y + 2 \\ x & = 2y + \dfrac{2}{17} \end{aligned}$$Berapa pun nilai bilangan bulat $y$, $x$ tidak akan bernilai bulat sehingga disimpulkan bahwa persamaan itu tidak memiliki solusi bulat.
Soal Nomor 3
Tentukan semua solusi bilangan bulat positif yang memenuhi persamaan $12x+5y=125$ dengan menggunakan teknik:
a. keterbagian;
b. teorema Diophantine.
Jawaban a)
Perhatikan bahwa
$\begin{aligned} 12x+5y & = 125 \\ 5y & = 125-12x \\ y & = 25-\dfrac{12}{5}x \end{aligned}$
Agar menghasilkan bilangan bulat $y$, $x$ harus habis dibagi $5$. Karena $x$ juga diharuskan positif, kita pilih:
- Nilai $x = 5$ sehingga $y = 25-12 = 13$.
- Nilai $x = 10$ sehingga $y = 25-12(2) = 1$.
- Nilai $x = 15$ sehingga $y = 25-12(3)=-11$ (tidak memenuhi).
Jadi, semua solusi bilangan bulat positif persamaan tersebut adalah $(5, 13)$ atau $(10, 1)$.
Jawaban b)
Diketahui $12x+5y = 125$.
Pertama, akan dicari $\text{FPB}(12, 5)$ menggunakan algoritma Euclides.
$$\begin{aligned} 12 & = 2 \cdot 5 + 2 && (\text{Iter}\text{asi}~1) \\ 5 & = 2 \cdot 2 + \color{blue}{1} && (\text{Iter}\text{asi}~2) \\ 2 & = 2 \cdot 1 + 0 && (\text{Iter}\text{asi}~3) \end{aligned}$$Jadi, $\text{FPB}(12, 5) = \color{blue}{1}$. Jelas bahwa $\color{blue}{1}$ membagi habis $125$ (konstanta persamaan di atas) sehingga persamaan memiliki solusi bulat.
Sekarang, kita kerjakan secara mundur dimulai dari iterasi 2 seperti berikut.
$$\begin{aligned} 1 & = 5-2\cdot 2 \\ 1 & = 5-2 \cdot (12-2 \cdot 5) \\ 1 & = 5 \cdot 5-2 \cdot 12 \\ \text{Kedua}~&\text{ruas dikalikan}~125 \\ 125 & = \color{red}{625} \cdot 5\color{blue}{-250} \cdot 12 \end{aligned}$$Dari persamaan $12x+5y=125$, kita peroleh satu solusi $x = -250$ dan $y = 625$, tetapi ini belum memenuhi kriteria solusi bilangan bulat positif.
Selanjutnya, kita mencari solusi umumnya dengan melakukan manipulasi aljabar memakai parameter $t$.
$$\begin{aligned} 125 & = 625 \cdot 5-250 \cdot 12 \\ & = 625 \cdot 5 + 5 \cdot 12 \cdot t-250 \cdot 12-5 \cdot 12 \cdot t \\ & = (625+12t) \cdot 5+(-250-5t) \cdot 12 \end{aligned}$$Jadi, solusi umum persamaan Diophantine tersebut adalah $x =-250-5t $ dan $y = 625+12t$ untuk setiap bilangan bulat $t.$
Agar diperoleh solusi bulat positif, haruslah $x = -250-5t > 0$ dan $y = 625+12t > 0,$ yang berturut-turut mengimplikasikan $t < -50$ dan $t > -52,cdots.$ Artinya, nilai $t$ yang memenuhi ada dua, yaitu $t = -51$ dan $t = -52.$
Untuk $t = -51,$ didapat $x = 5$ dan $y = 13.$ Sementara itu, untuk $t = -52,$ didapat $x = 10$ dan $y = 1.$
Soal Nomor 4
Tentukan solusi umum dari persamaan linear Diophantine $3x-4y = 12.$
Perhatikan bahwa
$$\begin{aligned} 3x-4y & = 12 \\ 3x & = 12 + 4y \\ x & = 4 + \dfrac43y \end{aligned}$$Sekarang, misalkan $y = 3n$ dengan $n$ bilangan bulat, naka diperoleh $x = 4 + \dfrac43(3n) = 4 + 4n$.
Jadi, solusi umum persamaan linear Diophantine tersebut adalah $x = 4 + 4n$ dan $y = 3n$ dengan untuk setiap bilangan bulat $n.$
Ilustrasi: Jika kita pilih $n = 2$, maka diperoleh $x = 12$ dan $y = 6$. Substitusikan pada persamaan linear tersebut dan ternyata terpenuhi bahwa $3(12)-4(6) = 36-24 = 12$.
Soal Nomor 5
Tentukan solusi umum persamaan linear Diophantine $35x+54y = 1.$
Pertama, akan dicari $\text{FPB}(35, 54)$ menggunakan algoritma Euclides.
$$\begin{aligned} 54 & = 1 \cdot 35 + 19 && (\text{Iter}\text{asi}~1) \\ 35 & = 1 \cdot 19 + 16 && (\text{Iter}\text{asi}~2) \\ 19 & = 1 \cdot 16 + 3 && (\text{Iter}\text{asi}~3) \\ 16 & = 5 \cdot 3 + \color{red}{1} && (\text{Iter}\text{asi}~4) \\ 3 & = 3 \cdot 1 + 0 && (\text{Iter}\text{asi}~5) \end{aligned}$$Jadi, $\text{FPB}(35, 54) = \color{blue}{1}$. Jelas bahwa $\color{blue}{1}$ membagi habis $1$ (konstanta persamaan di atas) sehingga ada solusi bulat.
Sekarang, kita kerjakan secara mundur dimulai dari iterasi 4 seperti berikut.
$$\begin{aligned} 1 & = 16-5 \cdot 3 \\ & = (35-19)-5 \cdot (19-16) \\ & = 35-6 \cdot 19 + 5 \cdot 16 \\ & = 35-6(54-35) + 5(35-19) \\ & = 12 \cdot 35-6 \cdot 54-5 \cdot 19 \\ & = 12 \cdot 35-6 \cdot 54-5 \cdot (54-35) \\ & = \color{red}{17} \cdot 35\color{blue}{-11} \cdot 54 \end{aligned}$$Dari persamaan $35x+54y = 1$, kita peroleh satu solusi $x = 17$ dan $y = -11$.
Untuk mencari solusi umumnya, lakukan manipulasi aljabar dengan melibatkan sebuah parameter $t$.
$$\begin{aligned} 1 & = 17 \cdot 35-11 \cdot 54 \\ & = 17 \cdot 35 \color{blue}{+ 35 \cdot 54 \cdot t}-11 \cdot 54\color{blue}{- 35 \cdot 54 \cdot t} \\ & = (17 +54t) \cdot 35+(-11-35t) \cdot 35 \end{aligned}$$Jadi, solusi umum persamaan Diophantine tersebut adalah $x = 17+54t$ dan $y = -11-35t$ untuk setiap bilangan bulat $t.$
Soal Nomor 6
Tentukan solusi umum persamaan linear Diophantine $25x+95y = 970.$
Persamaan $25x+95y=970$ dapat disederhanakan terlebih dahulu dengan membagi kedua ruas dengan $5$ sehingga diperoleh $5x + 19y = 194.$
Berikutnya, akan dicari $\text{FPB}(5, 19)$ menggunakan algoritma Euclides.
$$\begin{aligned} 19 & = 3 \cdot 5 + 4 && (\text{Iter}\text{asi}~1) \\ 5 & = 1 \cdot 4 + \color{red}{1} && (\text{Iter}\text{asi}~2) \\ 4 & = 4 \cdot 1 + 0 && (\text{Iter}\text{asi}~3) \end{aligned}$$Jadi, $\text{FPB}(5, 19) = \color{red}{1}$. Jelas bahwa $\color{red}{1}$ membagi habis $194$ (konstanta persamaan di atas) sehingga persamaan memiliki solusi bulat.
Sekarang, kita kerjakan secara mundur dimulai dari iterasi 2 seperti berikut.
$$\begin{aligned} 1 & = 5-1 \cdot 4 \\ & = 5-1(19-3 \cdot 5) \\ & = 4 \cdot 5-1 \cdot 19 \\ 194 & = 776 \cdot 5-194 \cdot 19. \end{aligned}$$Dari sini, diperoleh solusi khusus dari persamaan tersebut, yaitu $x_0 = 776$ dan $y_0 = -194.$ Untuk mencari solusi umumnya, lakukan manipulasi aljabar dengan melibatkan sebuah parameter $t$.
$$\begin{aligned} 194 & = 776 \cdot 5-194 \cdot 19 \\ & = 776 \cdot 5 + 5 \cdot 19t -194 \cdot 19-5 \cdot 19t \\ & = (776+19t)5+(-194-5t)19. \end{aligned}$$Jadi, solusi umum persamaan Diophantine tersebut adalah $x = 776+19t$ dan $y = -194-5t$ untuk setiap bilangan bulat $t.$
Soal Nomor 7
Tentukan solusi umum persamaan linear Diophantine $30x+47y = -11.$
Pertama, akan dicari $\text{FPB}(30, 47)$ menggunakan algoritma Euclides.
$$\begin{aligned} 47 & = 1 \cdot 30 + 17 && (\text{Iter}\text{asi}~1) \\ 30 & = 1 \cdot 17 + 13 && (\text{Iter}\text{asi}~2)\\ 17 & = 1 \cdot 13 + 4 && (\text{Iter}\text{asi}~3) \\ 13 & = 3 \cdot 4 + \color{red}{1} && (\text{Iter}\text{asi}~4) \\ 4 & = 4 \cdot 1 + 0 && (\text{Iter}\text{asi}~5) \end{aligned}$$Jadi, $\text{FPB}(30, 47) = \color{red}{1}$. Jelas bahwa $\color{red}{1}$ membagi habis $-11$ (konstanta persamaan di atas) sehingga persamaan memiliki solusi bulat.
Sekarang, kita kerjakan secara mundur dimulai dari iterasi 4 seperti berikut.
$$\begin{aligned} 1 & = 13-3 \cdot 4 \\ & = 13-3(17-1\cdot 13) \\ & = 4 \cdot 13-3 \cdot 17 \\ & = 4(30-1\cdot 17)-3 \cdot 17) \\ & = 4 \cdot 30-7 \cdot 17 \\ & = 4 \cdot 30-7 \cdot (47-1 \cdot 30) \\ & = 11 \cdot 30-7 \cdot 47 \\ -11 & = -121 \cdot 30 + 77 \cdot 47 \end{aligned}$$Dari sini, diperoleh solusi khusus dari persamaan tersebut, yaitu $x_0 = -121$ dan $y_0 = 77.$ Untuk mencari solusi umumnya, lakukan manipulasi aljabar dengan melibatkan sebuah parameter $t$.
$$\begin{aligned} -11 & = -121 \cdot 30 + 77 \cdot 47 \\ & = -121 \cdot 30 + 30 \cdot 47t + 77 \cdot 47-30 \cdot 47t \\ & = (-121 + 47t)30 + (77-30t)47 \end{aligned}$$Jadi, solusi umum persamaan Diophantine tersebut adalah $x = -121+47t$ dan $y = 77-30t$ untuk setiap bilangan bulat $t.$
Soal Nomor 8
Seorang pria membeli sejumlah apel dan jeruk dengan total harga $\$8,\!39.$ Jika sebuah apel dan sebuah jeruk berturut-turut memiliki harga $25$¢ dan $18$¢, berapa banyak apel dan jeruk yang pria tersebut beli?
Misalkan $x$ dan $y$ berturut-turut menyatakan banyak apel dan jeruk yang dibeli pria tersebut. Karena $1$ dolar sama dengan $100$ sen, kita peroleh persamaan linear Diophantine $25x + 18y = 839.$ Dalam kasus ini, akan dicari bilangan bulat nonnegatif $x$ dan $y$ yang memenuhi persamaan tersebut.
Pertama, akan dicari $\text{FPB}(25, 18)$ menggunakan algoritma Euclides.
$$\begin{aligned} 25 & = 1 \cdot 18 + 7 && (\text{Iter}\text{asi}~1) \\ 18 & = 2 \cdot 7 + 4 && (\text{Iter}\text{asi}~2)\\ 7 & = 1 \cdot 4 + 3 && (\text{Iter}\text{asi}~3) \\ 4 & = 1 \cdot 3 + \color{red}{1} && (\text{Iter}\text{asi}~4) \\ 3 & = 3 \cdot 1 + 0 && (\text{Iter}\text{asi}~5) \end{aligned}$$Jadi, $\text{FPB}(25, 18) = \color{red}{1}$. Jelas bahwa $\color{red}{1}$ membagi habis $839$ (konstanta persamaan di atas) sehingga persamaan memiliki solusi bulat.
Sekarang, kita kerjakan secara mundur dimulai dari iterasi 4 seperti berikut.
$$\begin{aligned} 1 & = 4-1\cdot 3 \\ & = 4-1(7-1 \cdot 4) \\ & = 2 \cdot 4 -1\cdot 7 \\ & = 2(18-2\cdot 7)-1 \cdot 7 \\ & = 2 \cdot 18-5 \cdot 7 \\ & = 2 \cdot 18-5(25-1 \cdot 18) \\ & = 7 \cdot 18-5 \cdot 25 \\ 839 & = 5.873 \cdot 18-4.195 \cdot 25\end{aligned}$$Dari sini, diperoleh solusi khusus dari persamaan tersebut, yaitu $x_0 = -4.195$ dan $y_0 = 5.873.$ Untuk mencari solusi umumnya, lakukan manipulasi aljabar dengan melibatkan sebuah parameter $t$.
$$\begin{aligned} 839 & = 5.873 \cdot 18-4.195 \cdot 25 \\ & = 5.873 \cdot 18 + 18 \cdot 25t -4.195 \cdot 25 -18 \cdot 25t \\ & = (5.873+25t)18+(-4.195-18t)25 \end{aligned}$$Jadi, solusi umum persamaan Diophantine tersebut adalah $x = -4.195-18t$ dan $y = 5.873+25t$ untuk setiap bilangan bulat $t.$
Agar diperoleh solusi bulat nonnegatif, haruslah $x = -4.195-18t \ge 0$ dan $y = 5.873 + 25t \ge 0,$ yang berturut-turut mengimplikasikan $t \le -233,\cdots$ dan $t \ge -234,\cdots.$ Dari sini, satu-satunya nilai $t$ yang memenuhi adalah $t = -234.$ Substitusi nilai $t$ tersebut pada $x$ dan $y$ akan menghasilkan $x = -4.195-18(-234) = 17$ dan $y = 5.873 + 25(-234) = 23.$ Artinya, pria tersebut membeli $17$ buah apel dan $23$ buah jeruk.
Soal Nomor 9
Nyatakan solusi sistem persamaan linear Diophantine berikut dalam bentuk parameter.
$$\begin{cases} x+y+z & = 100 \\ x+8y+50z & = 156 \end{cases}$$
Diketahui
$$\begin{cases} x+y+z & = 100 && (\cdots 1) \\ x+8y+50z & = 156 && (\cdots 2) \end{cases}$$Kurangi Persamaan $(2)$ dengan Persamaan $(1)$.
$$\begin{aligned} (x+8y+50z)-(x+y+z) & = 156-100 \\ 7y+49z & = 56 \\ y + 7z & = 8 \end{aligned}$$Persamaan di atas menunjukkan bahwa berapapun nilai $z$ yang diambil, nilai $y$ selalu bulat. Misalkan $z = 1$, maka diperoleh $y = 1.$
Kita peroleh solusi khususnya untuk persamaan $y+7z=8$, yaitu $(y_0, z_0) = (1, 1)$.
Berdasarkan teorema Diophantine, persamaan tersebut akan memiliki solusi umum
$$\begin{aligned} y & = y_0 + \dfrac{b}{\text{FPB}(a, b)} \cdot k \\ & = 1+\dfrac{7}{\text{FPB}(1,7)} \cdot k \\ & = 1+\dfrac{7}{1}k = 1+7k \\ z & = z_0-\dfrac{b}{\text{FPB}(a, b)} \cdot k \\ & = 1-\dfrac{1}{\text{FPB}(1,7)} \cdot k \\ & = 1-\dfrac{1}{1}k = 1-k \end{aligned}$$untuk setiap bilangan bulat $k.$
Sekarang, dari persamaan semula $x+y+z=100$, diperoleh
$\begin{aligned} x+(1+7k)+(1-k) & = 100 \\ x + 2+6k & = 100 \\ x & = 98-6k \end{aligned}$
Dengan demikian, solusi umum sistem persamaan linear Diophantine tersebut adalah $\boxed{\left(98-6k, 1+7k, 1-k\right)}$
Soal Nomor 10
Tentukan semua pasangan bilangan bulat $(x, y)$ yang memenuhi $x+y =xy-1$ dan $x \leq y.$
Perhatikan bahwa persamaan $x+y =xy-1$ dapat ditulis sebagai berikut.
$$\begin{aligned} \color{blue}{xy-x-y}-1 & = 0 \\ \color{blue}{\left[(x-1)(y-1)-1\right]}-1 & = 0 \\ (x-1)(y-1) & = 2 \Rightarrow \begin{cases} 1 \cdot 2 \\ 2 \cdot 1 \\ (-1) \cdot (-2) \\ (-2) \cdot (-1) \end{cases} \end{aligned}$$Kemungkinan 1:
$$\begin{aligned} (x-1) = 1 & \Leftrightarrow x = 2 \\ (y-1) = 2 & \Leftrightarrow y = 3 \end{aligned}$$Kemungkinan 2:
$$\begin{aligned} (x-1) = 2 & \Leftrightarrow x = 3 \\ (y-1) = 1 & \Leftrightarrow y = 2 \end{aligned}$$Tidak memenuhi syarat $x \le y$. Penyelesaian ditolak.
Kemungkinan 3:
$$\begin{aligned} (x-1) = -1 & \Leftrightarrow x = 0 \\ (y-1) = -2 & \Leftrightarrow y = -1 \end{aligned}$$Tidak memenuhi syarat $x \le y$. Penyelesaian ditolak.
Kemungkinan 4:
$$\begin{aligned} (x-1) = -2 & \Leftrightarrow x = -1 \\ (y-1) = -1 & \Leftrightarrow y = 0 \end{aligned}$$Jadi, HP = $\{(x, y) \mid (2, 3), (-1, 0)\}.$
Soal Nomor 11
Ada $2$ jenis bungkus suatu permen, masing-masing isinya $6$ butir permen dan $9$ butir permen. Apakah ada kombinasi jumlah bungkus permen tersebut sehingga banyak permen yang dimiliki sama dengan $100$ butir?
Misalkan $x, y$ berturut-turut menyatakan banyak bungkus permen yang isinya $6$ butir dan $9$ butir, maka kita peroleh persamaan linear Diophantine
$$6x + 9y = 100.$$Perhatikan bahwa $6x+9y = 3(2x+3y)$ sehingga total permen akan selalu berkelipatan $3$. Karena $100$ bukan kelipatan $3$, tidak ada kombinasi jumlah bungkus permen agar tepat diperoleh $100$ butir permen.
Soal Nomor 12
Selesaikan sistem persamaan linear Diophantine berikut.
$$\begin{cases} 3x-4y-z & = 5 && (\cdots 1) \\ 3y-4z+2w & = -5 && (\cdots 2) \\ 2x+w & = 10 && (\cdots 3) \end{cases}$$dengan $x, y, z, w$ bilangan bulat nonnegatif. Tentukan nilai $x + y+z+w$.
Dari Persamaan $(3)$, kita peroleh $w = 10-2x.$
Substitusikan pada Persamaan $(2)$.
$$\begin{aligned} 3y-4z+2\color{red}{w} & = -5 \\ 3y-4z+2(10-2x) & = -5 \\ 3y-4z+20-4x & = -5 \\ -4x+3y-4z & = -25 \\ 4x-3y+4z & = 25 && (\cdots 4) \end{aligned}$$Persamaan $(1)$ dikali $4$, lalu ditambah dengan Persamaan $(4)$, diperoleh
$$\begin{aligned} 16x-19y & = 45 \\ -19y & = 45-16x \\ y & = \dfrac{1}{19}(16x-45) \end{aligned}$$Substitusikan pada Persamaan $(1)$, diperoleh
$$\begin{aligned} 3x-4y-z & = 5 \\ z & = 3x-4y-5 \\ z & = 3x-\dfrac{4}{19}(16x-45)-5 \\ z & = \dfrac{1}{19}(57x-64x+180-95) \\ z & = \dfrac{1}{19}(85-7x) \end{aligned}$$Agar $y$ bernilai bulat, haruslah
$$\begin{aligned} 16x-45 & \equiv 0~(\text{mod}~19) \\ 16x & \equiv 45~(\text{mod}~19) \\ 16x & \equiv (45+19) ~(\text{mod}~19) \\ 16x & \equiv 64~(\text{mod}~19) \\ 16x & \equiv 16(4)~(\text{mod}~19) \\ x & \equiv 4~(\text{mod}~19) \end{aligned}$$Karena $w = 10-2x \geq 0$, berarti $0 \leq x \leq 5$, $x = 4$ merupakan satu-satunya nilai $x$ yang memenuhi sistem tersebut. Oleh karena itu, kita peroleh $y = 1$, $z = 3$, dan $w = 2$.
Jadi, nilai $$\boxed{x+y+z+w = 4+1+3+2=10}$$
Baca: Materi, Soal, dan Pembahasan – Kongruensi Modulo
Soal Nomor 13
Jane membeli $5$ buah semangka, $3$ buah apel, dan $20$ buah ceri seharga $46$ dolar. Luis membeli $2$ buah semangka, $5$ buah apel, dan $12$ buah ceri seharga $27$ dolar. Jika harga sebuah semangka dan apel bernilai bulat (dalam satuan dolar), berapakah harga sebuah apel? Misalkan $S, A, C$ berturut-turut menyatakan banyaknya buah semangka, apel, dan ceri sehingga banyak uang yang dikeluarkan Jane dan Luis dapat dinyatakan dalam sistem persamaan linear Diophantine berikut.
$$\begin{cases} 5S + 3A + 20C & = 46 && (\cdots 1) \\ 2S + 5A + 12C & = 27 && (\cdots 2) \end{cases}$$Samakan koefisien $S$ dengan cara Persamaan $(1)$ dikali $2$ dan Persamaan $(2)$ dikali $5$.
$$\begin{cases} 10S + 6A + 40C & = 92 && (\cdots 3) \\ 10S + 25A + 60C & = 135 && (\cdots 4) \end{cases}$$Kurangi Persamaan $(4)$ dengan Persamaan $(3)$.
$$\begin{aligned} 19A + 20C & = 43 \\ 20C & = 43-19A \\ C & = \dfrac{1}{20}(43-19A) \end{aligned}$$Substitusikan pada Persamaan $(1)$.
$$\begin{aligned} 5S+3A+20\color{red}{C} & = 46 \\ 5S+3A+(43-19A) & = 46 \\ 5S-16A+43 & = 46 \\ 5S & = 16A+3 \\ S & = \dfrac15(16A+3) \end{aligned}$$Karena $C = \dfrac{1}{20}(43-19A)$, nilai $A$ berada pada interval $0 < A < \dfrac{43}{19}$. Juga karena $S$ bilangan bulat positif, haruslah
$$\begin{aligned} 16A+3 & \equiv 0 (\text{mod}~5) \\ A & \equiv 2 (\text{mod}~5). \end{aligned}$$Dengan demikian, $A = 2$ merupakan satu-satunya solusi yang memenuhi kedua syarat di atas.
Jadi, harga sebuah apel adalah $\boxed{2}$ dolar.