Materi, Soal, dan Pembahasan – Persamaan Diophantine

       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.

Diophantus dari Alexandria
Diophantus dari Alexandria

      Persamaan linear Diophantine, khususnya, dapat diselesaikan secara analitis menggunakan bantuan Algoritma Euclid. Oleh karena itu, sebaiknya dipelajari terlebih dahulu mengenai algoritma tersebut pada tautan di bawah.

Baca: Materi, Soal, dan Pembahasan – Algoritma Euclid

         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 berdasar pada Identitas Bezout berikut.

Identitas Bezout (Bezout’s Identity)

Misalkan $a, b$ bilangan bulat dengan $\text{FPB}(a, b) = d$ sedemikian sehingga akan ada bilangan bulat $x$ dan $y$ yang memenuhi persamaan $ax + by = d$. Secara umum, $ax + by$ merupakan kelipatan dari $d$.

Sebagai contoh, diberikan persamaan linear $8x + 12y = 15$.
      Dapat dengan mudah dicari bahwa $\text{FPB}(8, 12) = 4$. Karena $4$ tidak membagi habis $15$, maka persamaan linear di atas bukan persamaan Diophantine sebab 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$, maka 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:

  1. Tidak memiliki solusi.
  2. Hanya ada $1$ solusi.
  3. Lebih dari $1$ solusi dan berhingga.
  4. Memiliki solusi sebanyak tak berhingga, sehingga memunculkan istilah “solusi umum”.

Teorema Diophantine

Persamaan linear Diophantine $ax + by = c$ mempunyai solusi jika dan hanya jika $\text{FPB}(a,b)~|~ c$.

Bukti:
($\Rightarrow$) Akan dibuktikan bahwa jika $ax + by = c$ memiliki solusi, maka $\text{FPB}(a,b)~|~c$.
Berdasarkan Identitas Bezout, 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 sembarang 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

Mathematical truth is immutable; it lies outside physical reality… This is our belief; this is our core motivating force.

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$

Pembahasan

Misalkan banyak tembakan $2$ poin dan tembakan $3$ poin yang terjadi adalah $M$ dan $N$, maka diperoleh persamaan linear
$$2M + 3N = 20$$Bisa diperiksa untuk setiap skenario 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)

[collapse]

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$

Pembahasan

Persamaan di atas menunjukkan bahwa selama nilai $y$ bulat, maka 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)

[collapse]

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$

Pembahasan

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, namun tidak perlu dicari berapa nilainya.
Jadi, akan ada $200$ pasangan bilangan bulat positif $(a, b)$ yang memenuhi persamaan tersebut.
(Jawaban D)

[collapse]

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$

Pembahasan

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$, maka akan ada $8$ pasangan bilangan bulat $(x, y)$ yang memenuhi persamaan itu.
(Jawaban D)

[collapse]

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. tak hingga
C. $2$

Pembahasan

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$, maka 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 tak hingga, maka juga akan ada tak hingga pasangan bilangan asli $(x, y)$ yang memenuhi persamaan tersebut.
(Jawaban E)

[collapse]

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$

Pembahasan

Diketahui $m-1 = \dfrac{15}{n}$. Agar $m$ bulat, maka $m-1$ juga harus bulat, berakibat $\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)

[collapse]

Soal Nomor 7
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$

Pembahasan

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)

[collapse]

Soal Nomor 8
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$

Pembahasan

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)

[collapse]

Soal Nomor 9
Berapa banyak pasangan bilangan bulat $(a, b)$ yang memenuhi $a^b = 64$?
A. $1$                    C. $3$                    E. $5$
B. $2$                    D. $4$

Pembahasan

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)

[collapse]

Soal Nomor 10
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$

Pembahasan

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})$, maka 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, maka 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)

[collapse]

Soal Nomor 11
Sistem persamaan $$\begin{cases} x+y+2z & = 10 \\ 3x-y+z & = 5 \end{cases}$$ memiliki penyelesaian bilangan bulat non-negatif untuk $x, y$, dan $z$. Jumlah dari semua nilai bilangan bulat non-negatif $x$ yang memenuhi sistem itu adalah $\cdots \cdot$
A. $3$                     C. $7$                     E. $11$
B. $5$                     D. $9$

Pembahasan

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 non-negatif, 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)

[collapse]

Soal Nomor 12
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.

Koleksi Prangko

A. $4$                     C. $6$                    E. $8$
B. $5$                     D. $7$

Pembahasan

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$, maka 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)

[collapse]

Soal Nomor 13
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$

Pembahasan

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)

[collapse]

Bagian Uraian

Soal Nomor 1
Dengan menggunakan Algoritma Euclid, tentukan solusi khusus dari persamaan linear Diophantine berikut.
a. $17x + 13y = 200$
b. $21x + 15y = 93$
c. $60x + 42y = 104$
d. $588x + 231y = 63$

Pembahasan

Jawaban a)
Diketahui $17x + 13y = 200$.
Dengan menggunakan Algoritma Euclid, 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$, maka persamaan itu memiliki solusi bulat.
Dengan menggunakan pembalikan Algoritma Euclid, 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 Euclid adalah $x = -600$ dan $y = 800$.
Jawaban b)
Diketahui $21x + 15y = 93$, dapat disederhanakan menjadi $7x + 5y = 31$.
Dengan menggunakan Algoritma Euclid, 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$, maka persamaan itu memiliki solusi bulat.
Dengan menggunakan pembalikan Algoritma Euclid, 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 Euclid adalah $x = -62$ dan $y = 93$.
Jawaban c)
Diketahui $60x + 42y = 104$, dapat disederhanakan menjadi $30x + 21y = 52$.
Dengan menggunakan Algoritma Euclid, 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$, maka persamaan itu tidakcmemiliki solusi bulat.
Jawaban d)
Diketahui $588x + 231y = 63$, dapat disederhanakan menjadi $196x + 78y = 21$.
Dengan menggunakan Algoritma Euclid, 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$, maka persamaan itu tidak memiliki solusi bulat.

[collapse]

Soal Nomor 2
Periksa apakah persamaan linear berikut memiliki solusi bulat atau tidak.
$$17x-34y = 2$$

Pembahasan

Ada $2$ pendekatan yang dapat dipakai untuk menyelesaikan persoalan ini.
Menggunakan Identitas Bezout:
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.

[collapse]

Soal Nomor 3
Tentukan semua solusi bilangan bulat positif yang memenuhi persamaan $12x+5y=125$ dengan menggunakan teknik:
a. keterbagian;
b. Teorema Diophantine.

Pembahasan

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$, maka $x$ harus habis dibagi $5$. Karena $x$ juga diharuskan positif, maka kita pilih:

  1. Nilai $x = 5$, sehingga $y = 25-12 = 13$.
  2. Nilai $x = 10$, sehingga $y = 25-12(2) = 1$.
  3. 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 Euclid.
$$\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 ada 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 $t$ sembarang bilangan bulat.
Agar diperoleh solusi bulat positif, ambil $t = -51$, sehingga didapat $x = 5$ dan $y = 13$, kemudian ambil $t = -52$, sehingga didapat $x = 10$ dan $y = 1$.

[collapse]

Soal Nomor 4
Tentukan solusi umum dari persamaan linear Diophantine berikut.
$$3x-4y = 12$$

Pembahasan

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 $n$ sembarang bilangan bulat.
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$.

[collapse]

Soal Nomor 5
Tentukan solusi umum persamaan linear Diophantine $35x+54y = 1$.

Pembahasan

Pertama, akan dicari $\text{FPB}(35, 54)$ menggunakan Algoritma Euclid.
$$\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 $t$ sembarang bilangan bulat.

[collapse]

Soal Nomor 6
Nyatakan solusi sistem persamaan linear Diophantine berikut dalam bentuk parameter.
$$\begin{cases} x+y+z & = 100 \\ x+8y+50z & = 156 \end{cases}$$

Pembahasan

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}$$di mana $k$ merupakan parameter berupa sembarang bilangan bulat.
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)}$

[collapse]

Soal Nomor 7
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?

Pembahasan

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$, maka tidak ada kombinasi jumlah bungkus permen agar tepat diperoleh $100$ butir permen.

[collapse]

Soal Nomor 8
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 non-negatif. Tentukan nilai $x + y+z+w$.

Pembahasan

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, maka 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$, maka $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}$$

[collapse]

Baca: Materi, Soal, dan Pembahasan – Kongruensi Modulo

Soal Nomor 9
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?

Pembahasan

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)$, maka nilai $A$ berada pada interval $0 < A < \dfrac{43}{19}$. Juga karena $S$ bilangan bulat positif, maka
$$\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.

[collapse]

Baca: Materi, Soal, dan Pembahasan – Teorema Sisa Cina

Tinggalkan Balasan

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *