Persamaan Diophantine Linear

[latexpage]

Persamaan Diophantine adalah sebuah persamaan suku banyak di mana variabel – variabel yang terlibat didefinisikan atas bilangan bulat. Nama Diophantine sendiri diambil dari seorang matematikawan bernama Diophantus, yang mempelajari tipe persamaan tersebut pada abad ke-3. Ia juga merupakan salah satu matematikawan yang mengenalkan simbol pada bidang aljabar. Bidang yang mempelajari masalah-masalah pada persamaan Diophantine saat ini dikenal dengan nama Diophantine analysis atau analisis Diophantine. Masalah yang dipelajari biasanya terkait dengan mencari eksistensi solusi, banyak solusi, atau cara untuk mendapatkan semua solusi.

Secara umum, persamaan Diophantine terbagi menjadi dua kategori, yakni persamaan Diophantine linear dan persamaan Diophantine non-linear. Persamaan Diophantine linear hanya melibatkan suku banyak berorder $1$, sedangkan persamaan Diophantine non-linear melibatkan suku banyak berorder lebih dari $1$. Di samping itu, terdapat juga tipe persamaan Diophantine di mana suku pada pangkat yang terlibat berupa suatu variabel. Persamaan ini dikenal dengan persamaan Diophantine eksponensial.

Pada artikel ini akan dibahas mengenai persamaan Diophantine linear.

Secara umum, persamaan Diophantine linear dapat dinyatakan ke dalam bentuk
\begin{eqnarray}
a_1x_1+a_2x_2+\cdots+a_nx_n=b,\label{diophantine}
\end{eqnarray}
dengan $a_1,a_2,\dotsc,a_n, b$ merupakan bilangan bulat dan $a_i\neq0$ untuk setiap $i=1,2\dotsc,n$.

Tipe masalah yang umumnya ditanyakan pada pesamaan Diophantine linear adalah mencari solusi bulat persamaan tersebut. Tentunya dalam mencari solusi, perlu diselidiki terlebih dahulu apakah persamaan tersebut memiliki solusi bulat atau tidak. Teorema di bawah ini memberikan syarat cukup dan perlu kapan suatu persamaan Diophantine linear memiliki solusi bulat.

Teorema 1. [Identitas Bezout]
[box] Persamaan (\ref{diophantine}) memiliki solusi bulat jika dan hanya jika $FPB(a_1,a_2,\ldots,a_n)$ habis membagi $b$. Lebih lanjut, jika persamaan (\ref{diophantine}) memiliki solusi bulat, maka semua solusi bulat dari persamaan (\ref{diophantine}) dapat dinyatakan ke dalam $n-1$ parameter. [/box]

[learn_more caption=”Bukti:” state=”open”]

Untuk mempermudah penulisan, misalkan $d=FPB(a_1,a_2,\ldots,a_n)$.\\

\noindent $(\Rightarrow)$ Misalkan persamaan (\ref{diophantine}) memiliki solusi bulat. Andaikan $b$ tidak habis dibagi oleh $d$. Perhatikan bahwa ruas kiri dari persamaan (\ref{diophantine}) habis dibagi oleh $d$, sedangkan ruas kanannya tidak. Terjadi suatu kontradiksi. Dengan demikian, $b$ habis dibagi oleh $b$

\noindent $(\Leftarrow)$ Misalkan $d$ habis membagi $b$. Diperoleh bahwa persamaan (\ref{diophantine}) ekuivalen dengan
\begin{eqnarray}
a’_1x_1+a’_2x_2+\cdots+a’_nx_n=b’,\label{diophantine2}
\end{eqnarray}
dengan $a’_i=a_i\slash d,\i=1,2,\ldots,n$ dan $b’=b\slash d$. Jelas bahwa $FPB(a’_1,a’_2,\ldots,a’_n)=1$.
Akan digunakan induksi matematika untuk membuktikan persamaan (\ref{diophantine2}) memiliki solusi bulat.

• Basis induksi: $n=1$. Persamaan (\ref{diophantine2}) menjadi $x_1=b$ atau $-x_1=b$. Diperoleh $x_1=b$ atau $x_1=-b$ merupakan solusi, dan solusi ini tidak berisi parameter.
• Langkah induksi: Diasumsikan persamaan (\ref{diophantine2}) dengan $n-1$ variabel memiliki solusi bulat. Akan dibuktikan bahwa persamaan (\ref{diophantine}) dengan $n$ variabel memiliki solusi bulat. Misalkan $d_{n-1}=FPB(a’_1,a’_2,\ldots,a’_{n-1})$. Diperoleh bahwa setiap solusi bulat dari persamaan (\ref{diophantine2}) memenuhi
  \[
  a’_1x_1+a’_2x_2+\cdots+a’_n x_n\equiv b’\pmod{d_{n-1}},
  \]
  yang ekuivalen dengan
  \begin{eqnarray}
  a’_nx_n\equiv b’\pmod{d_{n-1}} \label{diophantine3}.
  \end{eqnarray}
  Dengan mengalikan kedua ruas pada persamaan (\ref{diophantine2}) dengan ${a’_n}^{\varphi(d_{n-1})-1}$ dan menggunakan fakta bahwa ${a’_n}^{\varphi(d_{n-1})}\equiv 1\pmod{d_{n-1}}$, diperoleh
  \[
  x_n\equiv c\pmod{d_{n-1}},
  \]
  dengan $c={a’_n}^{\varphi(d_{n-1})-1}b’$. Artinya, $x_n=c+d_{n-1}t_{n-1}$ untuk suatu bilangan bulat $t_{n-1}$. Dengan mensubstitusi $x_n$ ke persamaan (\ref{diophantine2}), diperoleh
  \[
  a’_1x_1+\cdots+a’_{n-1}x_{n-1}=b-a’_nc-a’_nd_{n-1}t_{n-1}.
  \]
  Hal ini berarti, $d_{n-1}$ habis membagi $b’-a’_nc-a’_{n-1}d_{n-1}t_{n-1}$ atau yang ekuivalen dengan $a’_nc\equiv b’\pmod{d_{n-1}}$, sebab $c={a’_n}^{\varphi(d_{n-1})-1}b’$. Akibatnya, dengan membagi kedua ruas persamaan terakhir dengan $d_{n-1}$, diperoleh
  \begin{eqnarray}
  a”_1x_1+a”_2x_2+\cdots+a”_{n-1}x_{n-1}=b”\label{diophantine4}
  \end{eqnarray}
  dengan $a”_i=a’_i\slash d_{n-1}$ untuk $i=1,2,\ldots,n$ dan $b”=(b’-a’_nc)\slash d_{n-1}+a’_{n}t_{n-1}$. Karena $\gcd(a”_1,a”_2,\ldots,a”_{n-1})=1$, maka sesuai asumsi induksi, persamaan (\ref{diophantine4}) memiliki solusi bulat dan solusinya dapat ditulis ke dalam $n-2$ parameter. Jika pada solusi tersebut ditambahkan $x_n=c+d_{n-1}t_{n-1}$, diperoleh persamaan (\ref{diophantine2}) memiliki solusi bulat dan solusinya dapat ditulis ke dalam $n-1$ parameter.

Terbukti bahwa persamaan (\ref{diophantine2}) memiliki solusi bulat dan solusinya dapat ditulis ke dalam $n-1$ parameter.

[/learn_more]

Contoh:

Selidiki apakah masing-masing persamaan berikut memiliki solusi bilangan bulat $(x,y)$? Jika ya, tentukan salah satu solusinya.

1. $96x+54y=20$.
2.  $96x+54y=24$.

Solusi:

Pertama-tama, akan dicari $FPB(96,54)$. Salah satu cara yang dapat digunakan adalah dengan menggunakan algoritma Euclid. Berdasarkan algoritma Euclid,
\begin{eqnarray*}
96&=&1.54+42\\
54&=&1.42+12\\
42&=&3.12+6\\
12&=&2.6+0.
\end{eqnarray*}
Jadi, $FPB(96,54)=6$.

1. Karena $6$ tidak habis membagi $20$, berdasarkan Teorema \ref{thm:diophantine}, persamaan $96x+54y=20$ tidak memiliki solusi bulat.
2. Karena $6$ habis membagi $12$, berdasarkan Teorema \ref{thm:diophantine} persamaan $96x+54y=24$ memiliki solusi bulat. Salah satu solusinya dapat dicari dengan menggunakan algoritma Euclid. Diperhatikan bahwa
   \begin{eqnarray*}
   6&=&42-3.12\\
   12&=&54-42\\
   42&=&96-54.
   \end{eqnarray*}
   Diperoleh
   \begin{eqnarray*}
   6&=&42-3(54-42)\\
   &=&4.42-3.54\\
   &=&4(96-54)-3.54\\
   &=&4.96-7.54,
   \end{eqnarray*}
   sehingga didapat $24=16.96+(-28)54$. Jadi, $x=16$ dan $y=-28$ memenuhi persamaan $96x+54y=24$.

Salah satu akibat langsung dari Teorema 1 adalah jaminan bahwa solusi persamaan \ref{diophantine} ada ketika faktor persekutuan terbesar dari koefisien-koefisien pada setiap variabel adalah 1.

Akibat 1.

[box] Jika pada persamaan (\ref{diophantine}) berlaku $FPB(a_1,a_2,\ldots,a_n)=1$, maka persamaan tersebut memiliki solusi bulat.[/box]

Setelah mengetahui eksistensi solusi bulat persamaan Diophantine linear, pertanyaan selanjutnya adalah bagaimana mencari seluruh solusi bulat persamaan tersebut. Secara umum, tidak terdapat formula khusus untuk mencari solusinya. Namun, untuk persamaan Diophantine linear dengan dua variabel, semua solusi bulat dapat diperoleh dengan memanfaatkan Teorema \ref{thm:diophantine1} berikut.

[box] Diberikan $a,b$ dan $c$ bilangan bulat dengan sifat $FPB(a,b)$ habis membagi $c$. Jika $(x_0,y_0)$ merupakan solusi bulat dari persamaan
\[
ax+by=c,
\]
maka setiap solusi bulat dari persamaan tersebut dinyatakan dalam bentuk
\[
x=x_0+\frac{b}{FPB(a,b)}t,\ y=y_0-\frac{a}{FPB(a,b)}t
\]
untuk suatu bilangan bulat $t$.[/box]

[learn_more caption=”Bukti:” state=”open”]

Karena $(x_0,y_0)$ merupakan solusi bulat dari persamaan $ax+by=c$, berlaku $ax_0+by_0=c$. Diambil sebarang $(x,y)$ solusi bulat persamaan $ax+by=c$. Diperoleh
\[ax+by=c=ax_0+by_0
\iff a(x-x_0)=b(y_0-y)
\]
Dengan membagi kedua ruas persamaan tersebut dengan $FPB(a,b)$, diperoleh
\[
a'(x-x_0)=b'(y_0-y).
\]
dengan $a’=\frac{a}{FPB(a,b)}$ dan $b’=\frac{b}{FPB(a,b)}$ di mana $FPB(a’,b’)=1$. Perhatikan bahwa $a’$ habis membagi ruas kiri persamaan terakhir. Akibatnya, $a’$ juga habis membagi $b'(y_0-y)$. Karena $FPB(a’,b’)=1$, diperoleh $a’$ habis membagi $y_0-y$. Artinya, terdapat bilangan bulat $t$ dengan sifat $y_0-y=a’t$ atau $y=y_0-a’t$. Dengan mensubstitusi nilai $y$ ke persamaan terakhir, diperoleh $x=x_0+b’t$. Terbukti.

[/learn_more]

Teorema \ref{thm:diophantine1} juga dapat dimanfaatkan untuk mencari solusi bulat persamaan Diophantine linear atas tiga variabel atau lebih.

Contoh:

Tentukan semua tripel bilangan bulat ($x,y,z$) yang memenuhi persamaan $3x+4y+5z=2020$.

Solusi:

Persamaan tersebut ekuivalen dengan $3x+4y=5(404-z)$. Misalkan $z=404-s$. Diperoleh
\[ 3x+4y=5s. \]
Perhatikan bahwa $(x,y)=(3s,-s)$ merupakan salat satu solusi bulat persamaan tersebut. Berdasarkan Teorema \ref{thm:diophantine1}, diperoleh $x=3s+4t$ dan $y=-s-3t$ untuk suatu bilangan bulat $t$. Dengan demikian, solusi dari persamaan tersebut adalah
\[ (x,y,z)=(3s+4t,-s-3t,404-s) \]
dengan $s$ dan $t$ merupakan bilangan bulat.

Perhatikan bahwa Akibat \ref{akb:diophantine} memberikan jaminan bahwa persamaan $ax+by=n$ selalu memiliki solusi bulat untuk setiap bilangan asli $n$ jika $FPB(a,b)=1$. Bagaimana jika solusi yang diinginkan adalah bilangan bulat non-negatif. Secara umum, terdapat ada tak berhingga bilangan asli $n$ sehingga persamaan tersebut memiliki solusi bulat non-negatif. Teorema Frobenius berikut memberikan banyaknya bilangan asli $n$ yang menyebabkan persamaan $ax+by=n$ tidak memiliki solusi bulat non-negatif.

Teorema [Teorema Frobenius]
[box] Diberikan bilangan bulat positif $a$ dan $b$ dengan $FPB(a,b)=1$. Banyaknya bilangan bulat positif $n$ yang menyebabkan persamaan $ax+by=n$ tidak memiliki solusi bulat non-negatif adalah $\displaystyle{\frac{(a-1)(b-1)}{2}}$ [/box].

[learn_more caption=”Bukti:” state=”open”]

Katakan bilangan bulat positif $n$ “baik” jika persamaan $ax+by=n$ tidak memiliki solusi bulat non-negatif. Perhatikan susunan berikut:
\[
\begin{array}{ccccccc}
0&1&2&\ldots&\ell&\ldots&a-1\\
a&a+1&a+2&\ldots&a+\ell&\ldots&2a-1\\
2a&2a+1&2a+2&\ldots&2a+\ell&\ldots&3a-1\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots
\end{array}
\]
di mana setiap kolom membentuk barisan artimatika dengan beda $a$.

Jelas bahwa setiap kelipatan dari $b$ baik.
Perhatikan bahwa jika ada dua kelipatan dari $b$, katakan $vb$ dan $wb$ dengan $0\leq v,w\leq a-1$, berada pada kolom yang sama, maka kedua bilangan tersebut sama. Apabila kedua bilangan tersebut terletak pada kolom yang sama, maka berlaku $vb\equiv wb\pmod{a}$. Akibatnya $b(v-w)\equiv0\pmod{a}$. Karena $FPB(a,b)=1$, maka $v-w\equiv0\pmod{a}$. Karena $0\leq v,w\leq a-1$, maka $v=w$, sehingga $bv=bw$.

Akan ditunjukkan bahwa setiap bilangan yang berada di atas (dalam satu kolom) salah satu kelipatan $vb$, $0\leq v\leq a-1$, tidak baik. Perhatikan bahwa sebarang bilangan yang berada di atas $vb$ berbentuk $vb-ka$ untuk suatu bilangan bulat positif $k$. Jika $bv-ka$ baik, maka $ax+by=bv-ka$ untuk suatu bilangan bulat non-negatif $x$ dan $y$. Diperoleh $by\leq ax+by=bv-ka\leq bv$, yang berarti $0\leq y<v<a$. Akibatnya, $y\not\equiv v\pmod{a}$. Di sisi lain, dua bilangan yang terletak pada kolom yang sama kongruen dalam modulo $a$. Diperoleh $vb\equiv vb-ka\equiv ax+by\pmod{a}$, yang berarti $bv\equiv by\pmod{a}$. Karena $FPB(a,b)=1$, maka $v\equiv y\pmod{a}$, suatu kontradiksi.

Perhatikan bahwa jika $n$ baik, maka $n+ka$ juga baik untuk setiap bilangan asli $k$. Dengan demikian, banyaknya bilangan asli yang tidak baik sama dengan banyaknya bilangan yang berada di atas (dalam satu kolom) bilangan berbentuk $vb$, $0\leq v\leq a-1$. Diperhatikan bahwa pada kolom ke-$j$, terdapat $(vb-j)\slash a$ bilangan yang berada di atas $vb$. Akibatnya diperoleh banyaknya bilangan yang tidak baik adalah
\[
\sum_{v=0}^{a-1}\sum_{j=0}^{a-1}\frac{vb-j}{a}=\frac{(a-1)(b-1)}{2}.
\]

[/learn_more]

Berdasarkan bukti pada Teorema Frobenius di atas, diketahui bahwa bilangan asli terbesar $n$ yang menyebabkan persamaan $ax+by=n$ tidak memiliki solusi bulat non-negatif adalah $(a-1)b-a$. Dengan demikian, diperoleh syarat cukup untuk $n$ agar persamaan $ax+by=n$ memiliki solusi bulat non-negatif sebagai berikut.

Akibat 2
[box] Diberikan bilangan bulat positif $a$ dan $b$ yang saling prima. Persamaan
\[
ax+by=n
\]
tidak memiliki solusi bulat non-negatif untuk $n=ab-a-b$. Jika $n>ab-a-b$, maka persamaan tersebut memiliki solusi bulat non-negatif $x$ dan $y$. [\box]

Selanjutnya, Pembaca dapat mengerjakan soal-soal berikut sebagai latihan.

1. Tentukan semua solusi bulat persamaan-persamaan linear Diophantine berikut.
   a. $20x+19y=2019$.
   b. $20x+19y=2020$.
   c. $20x+20y=2019$.
   d. $20x+20y=2020$.
2. Tentukan semua solusi bulat $(a,b,c,d)$ dari persamaan
   \[
   (6a+9b)(7c+8d)=3.
   \]
3. Tentukan semua bilangan bulat $a$ dan $b$ sehingga $3a+4b$ habis membagi 2020.
4. Tunjukkan bahwa luas segitiga dengan titik-titik sudut $(0,0),(b,a),(x,y)$ adalah
   \[
   \frac{|ax-by|}{2}.
   \]
5. Tentukan bilangan bulat positif $a$ dan $b$ dengan sifat banyaknya bilangan bulat positif $n$ yang tidak dapat dinyatakan dalam bentuk $ax+by$ untuk suatu bilangan bulat non-negatif $x,y$ adalah 35 dan salah satu bilangan tersebut adalah 58.
6. Tentukan bilangan bulat positif terbesar yang tidak dapat dinyatakan dalam bentuk $42x+y$ untuk suatu bilangan bulat positif $x$ dan $y$ dengan $y$ komposit.