FPB, KPK,
& Persamaan Diophantine
Bab ini bergerak ke dua arah yang berlawanan. FPB mencari bilangan terbesar yang menyatukan dua bilangan — ia membagi keduanya. KPK mencari bilangan terkecil yang mempertemukan keduanya — ia adalah kelipatan bersama. Di ujung jalan, keduanya bergabung menjadi satu mesin penyelesai persamaan $ax + by = c$ dalam bilangan bulat.
PETA PERJALANAN BAB 3
- 3.1
FPB & Algoritma Euclid
Bagaimana mesin 2.000 tahun memangsa bilangan raksasa tanpa faktorisasi.
- 3.2
Identitas Bézout
FPB selalu bisa "dibongkar" menjadi $ax+by$. Inilah kuncinya segalanya.
- 3.3
Kelipatan Persekutuan Terkecil
Cermin kembaran FPB — dan jembatan $\gcd \cdot \mathrm{KPK} = ab$.
- 3.4
Persamaan Diophantine Linear
Kapan $ax+by=c$ punya solusi bulat, dan bagaimana menemukan semuanya.
Masalah Memotong
Pita merah panjangnya 56 cm, pita biru 36 cm. Keduanya akan dipotong menjadi potongan-potongan yang sama panjang dan tanpa sisa. Berapa panjang potongan terpanjang yang mungkin?
JAWABANNYA 4 — DAN KITA AKAN PAHAM MENGAPA DI §3.1.
Masalah Bertemu
Lampu kuning berkedip tiap 56 detik, lampu hijau tiap 36 detik. Saat ini keduanya menyala bersama. Kapan mereka menyala bersama lagi untuk pertama kalinya?
JAWABANNYA 504 DETIK — TUNGGU §3.3.
FAKTOR PERSEKUTUAN TERBESAR
Algoritma Euclid: mesin pembagi terbesar
Kita mulai dari nol. Sebelum bicara "terbesar", kita harus sepakat dulu apa arti "membagi". Semua yang luar biasa di bab ini tumbuh dari satu notasi kecil berikut.
Kita menulis $d \mid n$ (dibaca: "d membagi n") jika $n$ hasil kali $d$ dengan bilangan bulat lain.
$5 \nmid 56$ karena $56 = 5 \times 11 + 1$ (ada sisa!)
Faktor Persekutuan Terbesar $\gcd(a,b)$ adalah bilangan bulat positif terbesar yang membagi $a$ sekaligus membagi $b$.
Cara paling naif: tulis semua faktor masing-masing bilangan, cari yang sama, ambil yang terbesar. Coba sendiri dengan pegangan kita — klik tombol untuk menyalakan mode FPB:
Faktor persekutuan 56 dan 36 hanyalah {1, 2, 4}. Yang terbesar: 4.
JALAN 2 — FAKTORISASI PRIMA
Uraikan ke faktor prima, lalu ambil pangkat terkecil untuk setiap prima yang dimiliki keduanya:
$\gcd = 2^{\min(3,2)} \cdot 3^{\min(0,2)} \cdot 7^{\min(1,0)} = 2^2 = 4$
Mengapa pangkat terkecil? FPB tidak boleh memuat prima yang tidak dimiliki salah satu bilangan (makanya $3^0$ dan $7^0$), dan "tingginya" maksimal setinggi menara yang lebih pendek.
Coba daftarkan faktor $40902$ dan $24140$ secara manual — atau uraikan keduanya ke faktor prima. Butuh waktu lama dan rawan salah. Manusia butuh mesin. Euclid membangunnya sekitar 2.300 tahun lalu.
Setiap pembagian biasa $a$ oleh $b$ bisa ditulis:
$q$ = hasil bagi (quotient), $r$ = sisa (remainder). Contoh: $56 = 1 \times 36 + 20$.
Inti Algoritma Euclid adalah satu fakta ajaib:
Dari mana asalnya? Jika $d$ membagi $a$ dan $b$, maka $d$ pasti juga membagi selisihnya $a - qb$ (karena $a-qb$ hanyalah "kelipatan $a$ dikurangi kelipatan $b$"). Sebaliknya, jika $d$ membagi $b$ dan $a-qb$, maka $d$ membagi $a = qb + (a-qb)$. Jadi himpunan pembagi bersama $(a,b)$ sama persis dengan himpunan pembagi bersama $(b,\, a \bmod b)$ — dua pasang bilangan berbeda yang berbagi pembagi identik. Otomatis pembagi terbesarnya juga sama.
Akibatnya kita bisa menggulung bilangan berulang-ulang sampai sisa nol. Sisa terakhir yang bukan nol itulah FPB-nya. Lihat pegangan kita:
$36 = 1 \times 20 + \textcolor{#C2451E}{16}$
$20 = 1 \times 16 + \textcolor{#C2451E}{4}$
$16 = 4 \times 4 + \textcolor{#6E6455}{0}$ ← berhenti!
FPB(56, 36) = 4 — sisa bukan-nol terakhir.
Sekarang giliran Anda. Masukkan dua bilangan berapa pun (sampai 6 digit) dan biarkan mesin menggulungnya:
Pegangan tersimpan: 56 & 36. Langsung tekan JALANKAN.
Setiap langkah, sisa selalu $0 \le r \lt b$ — lebih kecil dari pembaginya. Praktisnya, sisa menyusut paling lambat seperti deret Fibonacci: jumlah langkah tidak pernah melebihi sekitar 5 kali jumlah digit bilangan terbesar (teorema Lamé). Untuk bilangan 6 digit: paling ~30 langkah. Itulah mengapa algoritma ini masih dipakai di dalam komputer modern.
gcd$(40902, 24140)$ dengan Euclid hanya butuh 8 baris:
40902 = 1·24140 + 16762
24140 = 1·16762 + 7378
16762 = 2·7378 + 2006
7378 = 3·2006 + 1360
2006 = 1·1360 + 646
1360 = 2·646 + 68
646 = 9·68 + 34 ← FPB = 34
68 = 2·34 + 0
FAKTA 1 — FPB DENGAN NOL
$\gcd(a, 0) = a$. Masuk akal: semua bilangan membagi 0, sehingga pembagi bersama terbesar $a$ dan $0$ adalah $a$ sendiri. Inilah sebabnya algoritma berhenti dengan rapi.
FAKTA 2 — KOPRIMA
Jika $\gcd(a,b) = 1$, kedua bilangan disebut koprima / relatif prima. Contoh: $\gcd(35, 12) = 1$ — mereka tidak punya faktor bersama selain 1.
Euclid tidak pernah menghitung faktor sama sekali. Ia hanya terus membagi dan membuang yang pasti terisi — dan sisa terakhirnya berbisik: aku adalah FPB.
IDENTITAS BÉZOUT
Membonceng dua bilangan dari FPB
Sekarang kita balik arah. Tadi kita menekan dua bilangan $(a,b)$ sampai mengeluarkan satu bilangan $d$. Bézout bertanya sebaliknya: bisakah $d$ dibongkar kembali memakai $a$ dan $b$?
Untuk bilangan bulat tak-nol $a$ dan $b$ dengan $d=\gcd(a,b)$, selalu ada bilangan bulat $x$ dan $y$ sehingga:
Bentuk $ax+by$ disebut kombinasi linear dari $a$ dan $b$. Teorema ini mengatakan: FPB selalu bisa dinyatakan sebagai kombinasi linear pembentuknya. Bahkan lebih kuat: himpunan semua kombinasi linear $\{ax+by\}$ adalah tepat semua kelipatan $d$.
Mengapa benar? Argumennya cantik dan memakai ulang Euclid. Baris pertama: $r_1 = a - qb$ jelas kombinasi linear. Baris kedua memakai $r_1$ dan $b$ — keduanya kombinasi linear — jadi $r_2$ juga. Begitu seterusnya: setiap sisa adalah kombinasi linear dari $a$ dan $b$, termasuk sisa terakhir yang bukan nol… yang tak lain adalah $d$ sendiri. Kita buktikan dengan menghitung:
| q | Sisa r | x | y | Artinya: r = 56·x + 36·y |
|---|---|---|---|---|
| – | 56 | 1 | 0 | $56 = 56\cdot 1 + 36\cdot 0$ |
| – | 36 | 0 | 1 | $36 = 56\cdot 0 + 36\cdot 1$ |
| 1 | 20 | 1 | −1 | $20 = 56\cdot 1 + 36\cdot(-1)$ |
| 1 | 16 | −1 | 2 | $16 = 56\cdot(-1) + 36\cdot 2$ |
| 1 | 4 | 2 | −3 | $4 = 56\cdot 2 + 36\cdot(-3)$ ← FPB! |
| 4 | 0 | – | – | berhenti |
Kolom x dan y dihitung dari dua baris di atasnya dengan resep yang sama seperti sisa: baru = lama − q·sebelumnya. Tabel ini disebut tabel Extended Euclid — mesin Diophantine di §3.4 memakainya.
Tanpa tabel pun bisa: tulis tiap sisa, lalu ganti sisa-sisa kecil memakai baris di atasnya, dari bawah ke atas. Jalankan stepper-nya pelan-pelan:
SOLUSINYA TAK TUNGGAL
Bukan hanya $4 = 56(2) + 36(-3)$. Cobalah $x=11, y=-17$: $56\cdot 11 - 36\cdot 17 = 616 - 612 = 4$. ✓
Semua pasangan $x = 2 + 9t,\; y = -3 - 14t$ untuk $t$ bulat juga berfungsi. Kita bedah tuntas pola ini di §3.4 — ia adalah kunci solusi umum Diophantine.
HADIAH BÉZOUT: UJI KOPRIMA INSTAN
$a$ dan $b$ koprima tepat jika ada $x,y$ dengan $ax+by=1$.
Contoh: $35(-1) + 12(3) = 1$, maka $\gcd(35,12)=1$ — terbukti tanpa faktorisasi.
KELIPATAN PERSEKUTUAN TERKECIL
KPK: cermin kembaran FPB
Ingat Masalah Bertemu di pembuka: lampu 56 detik dan lampu 36 detik. Kalau FPB menjawab soal memotong, KPK menjawab soal pertemuan — kapan dua siklus berdetak serempak lagi.
$m$ adalah kelipatan persekutuan $a$ dan $b$ jika $a \mid m$ dan $b \mid m$. Yang terkecil di antara yang positif disebut $\mathrm{KPK}(a,b)$ — atau $\mathrm{lcm}(a,b)$.
Kelipatan 36: $36, 72, \dots, 504, \dots$
KPK(56, 36) = 504
Kebalikan FPB: ambil pangkat terbesar untuk setiap prima yang muncul di salah satu bilangan:
$\mathrm{KPK} = 2^{\max(3,2)}\cdot 3^{\max(0,2)}\cdot 7^{\max(1,0)} = 2^3\cdot 3^2\cdot 7 = 504$
Dari mana asalnya? Lihat satu prima saja, katakan $2$. Pada $56$: pangkatnya $3$; pada $36$: pangkatnya $2$. Perhatikan pola pasti ini: pangkat terkecil + pangkat terbesar = jumlah kedua pangkat, yaitu $\min(3,2)+\max(3,2)=2+3$. Karena berlaku untuk setiap prima, hasil kalinya pun cocok: di ruas kiri, FPB menyumbang pangkat-min dan KPK menyumbang pangkat-max; di ruas kanan, $ab$ menyumbang jumlah keduanya. Identik!
PEGANGAN: $56 \times 36 = 2016$, lalu $2016 / 4 = 504$. COCOK.
Dua lampu berkedip: lampu A menyala sesaat setiap $p_A$ detik, lampu B setiap $p_B$ detik. Geser slider, jalankan waktunya, dan saksikan mereka "berpapasan" tepat pada kelipatan KPK:
Perhatikan: FPB × KPK selalu sama dengan pA × pB — teorema jembatan bekerja hidup-hidup.
Jawaban Masalah Bertemu: lampu 56 s dan 36 s menyala bersama lagi pada $\mathrm{KPK}(56,36) = \frac{56 \cdot 36}{4} = 504$ detik = 8 menit 24 detik. Satu kalimat FPB, satu kalimat KPK — dan dua teka-teki pembuka tuntas.
| Aspek | FPB / gcd | KPK / lcm |
|---|---|---|
| Makna | Pembagi bersama terbesar | Kelipatan bersama terkecil |
| Faktorisasi prima | Pangkat MIN per prima | Pangkat MAKS per prima |
| Contoh pegangan | gcd(56,36) = 4 | lcm(56,36) = 504 |
| Konteks cerita | Memotong / membagi rata tanpa sisa | Siklus bertemu lagi / sinkron |
| Jembatan | gcd(a,b) · lcm(a,b) = a · b | |
| Sifat skala | gcd(ka,kb) = k·gcd(a,b) | lcm(ka,kb) = k·lcm(a,b) |
| Kasus ekstrem | gcd(a,0) = a | a | b ⟺ lcm(a,b) = b |
Tiga bus berangkat dari terminal yang sama masing-masing tiap 12, 15, dan 20 menit. Pukul 07.00 mereka berangkat bersama. Kapan pertama kali mereka berangkat bersama lagi?
$\mathrm{KPK}(12,15) = 60$, lalu $\mathrm{KPK}(60,20) = 60$. Jadi mereka bertiga berangkat bersama lagi 60 menit kemudian, pukul 08.00.
PERSAMAAN DIOPHANTINE LINEAR
Kapan $ax + by = c$ punya solusi bulat?
Garis lurus $56x + 36y = 8$ punya tak hingga solusi bilangan real — gambar saja garisnya, setiap titik di atasnya adalah solusi. Tetapi pertanyaan yang jauh lebih menarik: kapan garis itu menyentuh titik-titik kisi bulat? Persamaan yang dicari solusinya di $\mathbb{Z}$ disebut persamaan Diophantine, dari nama matematikawan Yunani Diophantus (± 250 M).
Persamaan $ax + by = c$ dengan $a,b \neq 0$ memiliki solusi bilangan bulat tepat jika:
Mengapa ("hanya jika"): jika $(x,y)$ solusi, maka $d \mid a$ dan $d \mid b$, sehingga $d$ membagi $ax+by$ — yang berarti $d \mid c$. Kombinasi linear $a$ dan $b$ tak mungkin lolos dari $d$.
Mengapa ("jika"): jika $d \mid c$, tulis $c = dk$. Bézout memberi $ax_0 + by_0 = d$. Kalikan kedua ruas dengan $k$: $a(x_0 k) + b(y_0 k) = dk = c$. Selesai — solusinya $(x_0 k,\; y_0 k)$.
PENYANGKAL 1
$56x + 36y = 10$ → $4 \nmid 10$, maka tidak ada solusi bulat. Sekecil apa pun Anda mencoba, hasil $56x+36y$ selalu kelipatan 4 — mustahil menyentuh 10.
PENYANGKAL 2 (PARITAS)
$2x + 4y = 7$ → ruas kiri selalu genap, ruas kanan ganjil. Di baliknya: $\gcd(2,4)=2$ dan $2 \nmid 7$. Fenomena yang sama, hanya terlihat sebagai "genap vs ganjil".
LANGKAH 1 · UJI SYARAT
Hitung $d=\gcd(a,b)$. Jika $d$ tidak membagi $c$ → berhenti, tidak ada solusi bulat.
LANGKAH 2 · BÉZOUT
Cari satu solusi Bézout: $ax_0 + by_0 = d$ (substitusi mundur atau tabel Extended Euclid).
LANGKAH 3 · SKALA
Kalikan dengan $k = c/d$ untuk mendapat solusi partikular: $(x_0k,\; y_0k)$.
LANGKAH 4 · UMUMKAN
Tambahkan "gerak sepanjang garis" untuk mendapat SEMUA solusi.
Setelah punya satu solusi $(x_0,y_0)$, bagaimana menemukan semua solusi lain? Geser titiknya sepanjang garis: naikkan $x$ sebesar $\frac{b}{d}$ dan turunkan $y$ sebesar $\frac{a}{d}$.
Kenapa nilai persamaan tak berubah? Tambahan nilainya: $a\cdot\frac{b}{d} - b\cdot\frac{a}{d} = 0$ — kenaikan dan penurunan saling menghapus, presisi.
Kenapa SEMUA solusi tercakup? Selisih dua solusi apa pun $(\Delta x, \Delta y)$ memenuhi $a\,\Delta x = -b\,\Delta y$. Tulis $a = da',\, b = db'$ dengan $a', b'$ koprima; maka $a'\Delta x = -b'\Delta y$ memaksa $b' \mid \Delta x$, yaitu $\Delta x = \frac{b}{d}t$ dan otomatis $\Delta y = -\frac{a}{d}t$. Tidak ada solusi yang lolos.
Jika $d \mid c$, solusi bulat selalu tak hingga banyaknya (parameter $t$ bebas). Yang biasa diminta soal adalah solusi non-negatif — dan jumlahnya pasti hingga, karena $x \ge 0$ dan $y \ge 0$ memenjarakan $t$ di dalam sebuah selang. Cara menangkapnya: dua ketaksamaan sederhana (lihat contoh).
Langkah 1 — uji syarat
$d = \gcd(56,36) = 4$, dan $4 \mid 8$. ✓ Solusi ada.
Langkah 2 — Bézout (dari §3.2)
$56(2) + 36(-3) = 4$.
Langkah 3 — skala dengan $k = 8/4 = 2$
$x_0 = 2\cdot 2 = 4$, $y_0 = -3 \cdot 2 = -6$.
Cek: $56(4) + 36(-6) = 224 - 216 = 8$ ✓
Langkah 4 — solusi umum
$x = 4 + 9t$, $y = -6 - 14t$, $t \in \mathbb{Z}$.
| t | x = 4 + 9t | y = −6 − 14t | Cek: 56x + 36y |
|---|---|---|---|
| −1 | −5 | 8 | −280 + 288 = 8 ✓ |
| 0 | 4 | −6 | 224 − 216 = 8 ✓ |
| 1 | 13 | −20 | 728 − 720 = 8 ✓ |
| 2 | 22 | −34 | 1232 − 1224 = 8 ✓ |
Tiket A seharga Rp56.000 dan tiket B seharga Rp36.000 dibeli dengan total tepat Rp864.000. Berapa cara (kombinasi jumlah tiket) yang mungkin?
Modelnya: $56x + 36y = 864$. Bagi 4: $14x + 9y = 216$. Solusi gampang terlihat: $(0, 24)$. Maka $x = 0 + 9t$, $y = 24 - 14t$. Syarat $x,y \ge 0$: $t=0$ memberi $(0,24)$; $t=1$ memberi $(9,10)$; $t=2$ memberi $(18,-4)$ ✗. Ada 2 cara pembelian.
Buku tulis Rp4.000, pensil Rp6.000, uang tepat Rp58.000: $4x + 6y = 58$, bagi 2 → $2x + 3y = 29$ (koprima, pasti ada solusi). Satu solusi: $2(-1) + 3(1) = 1$, dikali 29: $x_0 = -29,\ y_0 = 29$. Umum: $x = -29 + 3t$, $y = 29 - 2t$.
Penjara $t$: $-29+3t \ge 0 \Rightarrow t \ge 10$; $29-2t \ge 0 \Rightarrow t \le 14$. Maka $t \in \{10, \dots, 14\}$: tepat 5 cara — $(1,9), (4,7), (7,5), (10,3), (13,1)$.
Masukkan $a$, $b$, dan $c$ sembarang; mesin akan menjalankan resep lengkap: uji syarat, tabel Extended Euclid, skala, solusi umum, sampai menyaring semua solusi non-negatif:
a, b ≥ 1 (maks 999); c bebas hingga ±99999. Default: persamaan pegangan.
FPB menentukan apakah solusi ada. Bézout menemukan satu solusi. Dan arah $\left(\tfrac{b}{d}, -\tfrac{a}{d}\right)$ menuntun kita menyusuri semua solusi lain di sepanjang garis.
RANGKUMAN · KUIS · LATIHAN
Dinding hafalan Bab 3
Empat kartu ini adalah seluruh mesin bab. Jika keempatnya melekat di kepala, semua soal FPB–KPK–Diophantine hanyalah variasi langkah kaki.
Gulung terus sampai sisa 0. FPB = sisa bukan-nol terakhir. Sisa selalu menyusut, jadi dijamin berhenti.
FPB selalu bisa dibongkar menjadi kombinasi linear. Pegangan: $56\cdot 2 + 36\cdot(-3) = 4$.
Per prima: pangkat-min + pangkat-maks = jumlah pangkat. Pegangan: $4 \times 504 = 56 \times 36 = 2016$.
Uji syarat → Bézout → skala ×(c/d) → umumkan. Solusi non-negatif dihitung dari penjara $t$: dua ketaksamaan.