Materi Olimpiade SMP : Bab 3 Teori Bilangan [Basic] : FPB, KPK, dan Algoritma Pembagian

Materi sebelumnya : Materi Olimpiade SMP : Bab 2 Teori Bilangan [Basic] : Keterbagian dan Faktor

Sebelum melangkah lebih jauh, terlebih dahulu akan saya definisikan faktor persekutuan, Faktor Persekutuan Terbesar (FPB), dan Kelipatan Perseketuan Terkecil (KPK)

Bilangan $c$ dikatakan faktor persekutuan bilangan $a$ dan $b$ jika $c$ habis mebagi $a$ dan $b$

Bilangan positif $d$ disebut faktor persekutuan terbesar bilangan (FPB) $a$ dan $b$ jika $d$ adalah faktor persekutuan yang paling besar dari $a$ dan $b$

Bilangan positif $e$ disebut kelipatan persekutuan terkecil (KPK) bilangan $a$ dan $b$ jika $e$ adalah bilangan terkecil sedemikian sehingga $a$ dan $b$ habis membagi $e$

Tentukan FPB dari $2$ bilangan akan lebih mudah jika kedua bilangan tersebut kecil. Bagaimana jika kita dihadapkan dengan persoalan mencari FPB dari $13430204$ dan $34383$ ? Persoalan seperti ini biasanya diselesaikan dengan menggunakan algoritma pembagian

Teorema 1

Misalkan $b$ bilangan bulat positif, maka untuk setiap bilangan bulat $a$ terdapat secara tunggal bilangan bulat $q$ dan $s$ sehingga $a = qb + s$ dengan $0 \le s < b$. Jika $b|a$, maka $s = 0$

Teorema 2

Jika $a$ dan $b$ dua bilangan bulat dan $d = \text{FPB}(a, b)$, maka ada bilangan bulat $m$ dan $n$ sehingga $d = ma + nb$

Algoritma Pembagian

Misalkan kita akan mencari $\text{FPB}(2015, 275)$ dan mencari $m$ dan $n$ sedemikian sehingga $d = 2015m + 275n$. Dengan menggunakan algoritma pembagian (gunakan teorema 1 dan 2), perhatikan bahwa

$2015 = 7 \times 275 + 90$

$275 = 3 \times 90 + 5$

$90 = 19 \times 5 + 0$

Menurut algoritma pembagian, $\text{FPB}(2015, 275)$ adalah $5$. Jika kita balik proses pengerjaannya dari bawah, diperoleh

$5 = 275 - 3 \times 90 = 275 - 3 \times (2015 - 7 \times 275) = 22 \times 275 - 3 \times 2015$. Diperoleh $m = -3$ dan $n = 22$

Untuk mempermudah pemahaman untuk memahami materi ini, berikut saya sediakan beberapa contoh soal beserta solusi

Soal 1

Carilah FPB dari $3276$ dan $148614$

Solusi 

Dengan menggunakan algoritma pembagian

$148614 = 45 \times 3276 + 1194$

$3276 = 2 \times 1194 + 888$

$1194 = 1 \times 888 + 306$

$888 = 2 \times 306 + 276$

$306 = 1 \times 276 + 30$

$276 = 9 \times 30 + 6$

$30 = 5 \times 6 + 0$

Dari algoritma pembagian diperoleh bahwa $\text{FPB}(3276, 148614) = 6$

Soal 2

Carilah dua bilangan $m$ dan $n$ sehingga $126m + 65n = 1$

Solusi

Dengan algoritma pembagian diperoleh bahwa

$126 = 1 \times 65 + 61$

$65 = 1 \times 61 + 4$

$61 = 15 \times 4 + 1$

$4 = 4 \times 1 + 0$

Dengan proses terbalik, diperoleh bahwa

$1 = 61 - 15 \times 4 = (126 - 1 \times 65) - 15 \times (65 - 1 \times 61) = 126 - 16 \times 65 + 15 \times 61$

$= 126 - 16 \times 65 + 15 \times (126 - 1 \times 65) = 16 \times 126 - 31 \times 65$

Jadi diperoleh $m = 16$ dan $n = -31$

Soal 3

$m$ dan $n$ adalah bilangan bulat positif dengan $mn = 40000$. Jika $m$ dan $n$ keduanya tidak habis dibagi $10$, tentukan $m + n$

Solusi

Perhatikan bahwa $40000 = 2^6 \times 5^4$ hanya memiliki faktor prima $2$ dan $5$. Karena $m$ dan $n$ masing - masing tidak habis dibagi $10$ haruslah $m$ dan $n$ merupakan permutasi dari $(2^6, 5^4)$. Jadi, $m + n = 2^6 + 5^4 = 64 + 625 = 689$

Soal 4

Pecahan $\frac{s}{t}$ adalah pecahan sejati jika $s < t$ dan faktor persekutuan terbesarnya adalah $1$. Jika $t$ mempunyai nilai $2$ sampai $9$, maka tentukanlah banyaknya pecahan sejati yang dapat dibentuk

Solusi

Perhatikan bahwa nilai $t$ berada pada $2$ sampai $9$ sehingga ada $8$ kasus sebagai berikut

• $t = 2$, maka $s$ yang memenuhi adalah $1$
• $t = 3$, maka $s$ yang memenuhi adalah $1, 2$
• $t = 4$, maka $s$ yang memenuhi adalah $1, 3$
• $t = 5$, maka $s$ yang memenuhi adalah $1, 2, 3, 4$
• $t = 6$, maka $s$ yang memenuhi adalah $1, 5$
• $t = 7$, maka $s$ yang memenuhi adalah $1, 2, 3, 4, 5, 6$
• $t = 8$, maka $s$ yang memenuhi adalah $1, 3, 5, 7$
• $t = 9$, maka $s$ yang memenuhi adalah $1, 2, 4, 5, 7, 8$

Jadi banyaknya pecahan sejati yang bisa dibentuk adalah $1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 = 27$

Soal 5

Untuk setiap bilangan asli $a$, buktikan bahwa $\text{FPB}(2a + 1, 9a + 4) = 1$

Solusi

Perhatikan bahwa $\text{FPB}(2a + 1, 4(2a + 1) + a) = \text{FPB}(2a + 1, a) = \text{FPB}(1, a) = 1$ 

Soal 6

Buktikan bahwa $n! + 1$ dan $(n+1)! + 1$ relatif prima

Catatan : Bilangan $a$ dan $b$ dinyatakan relatif prima jika $\text{FPB}(a, b) = 1$

Solusi

Perhatikan bahwa $\text{FPB}(n! + 1, (n+1)! + 1) = \text{FPB}(n! + 1, (n+1)(n! + 1) - n)$ 

$= \text{FPB}(n! + 1, n) = \text{FPB}(1, n) = 1$

Jadi terbukti bahwa  $n! + 1$ dan $(n+1)! + 1$ relatif prima

Sebagai latihan, berikut saya berikan soal - soal latihan agar bisa dicoba oleh para pembaca

Latihan 1

Tentukan FPB dari $8!$ dan $4^3$

Latihan 2

Carilah $2$ bilangan bulat $a$ dan $b$ dengan $a < b$ yang mempunyai $\text{FPB(a, b)} = 4$ dan $\text{KPK}(a, b) = 140$. Tentukan semua pasangan $(a, b)$ yang mungkin

Latihan 3

Jika $n$ adalah bilangan ganjil, buktikan bahwa $n$ dan $n - 2$ relatif prima

Latihan 4

Buktikan bahwa $\text{FPB}(\text{FPB}(a, b), a) = \text{FPB}(a, b)$

Latihan 5

Diberikan $\text{FPB} (a, b) = 1$, buktikan bahwa

(a) $\text{FPB}(a + b, a - b) = 1$ atau $2$

(b) $\text{FPB}(2a + b, a + 2b) = 1$ atau $3$

(c) $\text{FPB}(a + b, a^2 + b^2) = 1$ atau $2$

Latihan 6

Jumlah dua bilangan bulat positif adalah $5432$. Kelipatan persekutuan terkecilnya adalah $223020$. Carilah kedua bilangan tersebut