MATERI OLIMPIADE MATEMATIKA SMP KOMBINASI LINEAR DAN PERSAMAAN DIOPHANTINE

Materi Kombinasi Linier dan Persamaan Diophantine adalah kelanjutan yang sangat sempurna setelah siswa menguasai Algoritma Euclid. Ini adalah salah satu materi inti dalam Teori Bilangan yang sangat sering keluar dan menjadi penentu di kompetisi tingkat nasional maupun ajang bergengsi seperti Gema Lomba Matematika Undiksha.

Berikut adalah uraian materi yang disusun secara taktis untuk mempermudah pemahaman analitis siswa.

Kombinasi Linier dan Persamaan Diophantine Linier

Jika Algoritma Euclid digunakan untuk mencari nilai FPB, maka Kombinasi Linier (sering disebut Identitas Bézout) dan Persamaan Diophantine digunakan untuk mencari solusi bilangan bulat dari suatu persamaan yang melibatkan FPB tersebut.

1. Kombinasi Linier (Identitas Bézout)

Teorema Bézout menyatakan bahwa jika $d$ adalah FPB dari dua bilangan bulat $a$ dan $b$, maka selalu ada bilangan bulat $x$ dan $y$ yang memenuhi persamaan:

$$ax + by = d$$

Persamaan di atas disebut sebagai kombinasi linier dari $a$ dan $b$.

Cara Mencari Nilai $x$ dan $y$:

Kita menggunakan Algoritma Euclid Diperluas (berjalan mundur dari bawah ke atas pada langkah pembagian Euclid).

Contoh: Nyatakan FPB dari 24 dan 15 sebagai kombinasi linier dari 24 dan 15!

Langkah 1 (Euclid Biasa):

$24 = 15(1) + 9$

$15 = 9(1) + 6$

$9 = 6(1) + 3$ $\rightarrow$ (3 adalah FPB-nya)

$6 = 3(2) + 0$

Langkah 2 (Euclid Diperluas - Balikkan persamaannya mulai dari sisa sebelum 0):

$3 = 9 - 6(1)$

Langkah 3 (Substitusi sisa bagi sebelumnya dari bawah ke atas):

Ganti angka 6 dengan $(15 - 9(1))$:

$3 = 9 - [15 - 9(1)](1)$

$3 = 9 - 15 + 9$

$3 = 9(2) - 15(1)$

Ganti angka 9 dengan $(24 - 15(1))$:

$3 = [24 - 15(1)](2) - 15(1)$

$3 = 24(2) - 15(2) - 15(1)$

$3 = 24(2) + 15(-3)$

Jadi, kombinasi liniernya adalah $24(2) + 15(-3) = 3$, di mana nilai $x = 2$ dan $y = -3$.

2. Persamaan Diophantine Linier

Persamaan Diophantine adalah persamaan polinomial di mana kita hanya mencari solusi bilangan bulat. Bentuk liniernya adalah:

$$ax + by = c$$

Syarat Mutlak (Kunci Penyelesaian):

Persamaan $ax + by = c$ hanya memiliki solusi bulat jika dan hanya jika FPB dari $a$ dan $b$ habis membagi $c$.

Jika FPB$(a, b)$ tidak habis membagi $c$, ajarkan siswa untuk langsung menyimpulkan bahwa persamaan tersebut "tidak memiliki solusi".

Rumus Solusi Umum:

Jika siswa sudah menemukan satu solusi awal, sebut saja $(x_0, y_0)$, maka untuk mencari semua kemungkinan solusi lainnya (karena solusinya ada tak hingga), gunakan rumus:

$$x = x_0 + \frac{b}{d}k$$

$$y = y_0 - \frac{a}{d}k$$

Keterangan: * $d = \text{FPB}(a, b)$

$k$ adalah sembarang bilangan bulat ($0, 1, -1, 2, -2, \dots$)

3. Contoh Soal Tipe Kompetisi (Step-by-Step)

Soal: Tentukan semua solusi bilangan bulat dari persamaan $12x + 15y = 9$!

Langkah 1: Cek Syarat Mutlak

Cari FPB dari 12 dan 15. FPB(12, 15) = 3.

Apakah 3 habis membagi 9? Ya ($9 \div 3 = 3$). Maka persamaan ini punya solusi.

Langkah 2: Cari Solusi Awal $(x_0, y_0)$ dengan Kombinasi Linier

Buat kombinasi linier untuk FPB-nya terlebih dahulu: $12x + 15y = 3$.

Dengan inspeksi/tebakan cerdas atau Euclid diperluas, kita temukan:

$15(1) - 12(1) = 3 \rightarrow 12(-1) + 15(1) = 3$.

Karena di soal hasilnya harus 9 (bukan 3), kalikan seluruh ruas dengan 3:

$3 \times [12(-1) + 15(1)] = 3 \times 3$

$12(-3) + 15(3) = 9$

Maka, solusi awalnya adalah $x_0 = -3$ dan $y_0 = 3$.

Langkah 3: Masukkan ke Rumus Solusi Umum

$x = -3 + \frac{15}{3}k \rightarrow x = -3 + 5k$

$y = 3 - \frac{12}{3}k \rightarrow y = 3 - 4k$

(Untuk setiap $k$ bilangan bulat)

4. Strategi Cerdas untuk Siswa

Trik Hemat Waktu: Saat berlomba, melatih intuisi (trial and error cerdas) untuk mencari solusi awal $(x_0, y_0)$ seringkali jauh lebih cepat daripada menggunakan Algoritma Euclid Diperluas secara penuh, terutama jika angka koefisiennya relatif kecil. Euclid Diperluas baru dikeluarkan sebagai senjata terakhir jika angkanya ratusan atau ribuan.

5. LATIHAN SOAL

1. Tentukan satu pasang solusi bilangan bulat $(x, y)$ pertama yang memenuhi persamaan $47x + 30y = 1$.
2. Berapa banyak pasangan solusi bilangan bulat non-negatif $(x, y)$ yang memenuhi persamaan $7x + 11y = 200$?
3. Sebuah koin permainan bernilai 5 sen dan 8 sen. Berapakah nominal belanja terbesar yang TIDAK bisa dibayar menggunakan kombinasi kedua koin tersebut dengan uang pas?
4. Tentukan nilai $c$ positif terkecil agar persamaan $105x + 56y = c$ memiliki setidaknya satu solusi bilangan bulat.
5. Tentukan semua pasangan $(x,y)$ bulat positif yang memenuhi $15x + 16y = 300$.
6. Diberikan persamaan $3x - 5y = 19$. Jika $x$ dan $y$ dibatasi sebagai bilangan asli kurang dari 50, ada berapa pasang $(x, y)$ yang memenuhi?
7. Gunakan konsep invers modulo (kombinasi linier) untuk menentukan sisa $x$ jika dibagi 13 pada kongruensi $12x \equiv 5 \pmod{13}$.
8. Persamaan Diophantine $ax + 15y = 3$ memiliki salah satu penyelesaian $(x, y) = (2, -1)$. Tentukan nilai koefisien $a$ dan hitung $\text{FPB}(a, 15)$.
9. Temukan penyelesaian bulat terkecil (nilai mutlak $x$ dan $y$ minimal) untuk persamaan $101x + 37y = 2$.
10. Sebuah sekolah mengalokasikan dana Rp325.000 untuk membeli buku matematika seharga Rp30.000 dan buku fisika seharga Rp25.000. Jika dana harus habis, berapa banyak komposisi jumlah buku yang mungkin dibeli?