FPB dan KPK
A). Faktor Persekutuan Terbesar (FPB)
(i). Pengertian FPB
Suatu bilangan \(d\) disebut faktor persekutuan terbesar (greater common divisor / GCD) dari bilangan \(a\) dan \(b\) jika:
- \(d\) membagi habis \(a\) dan \(b\) (\(d|a\) dan \(d|b\)).
- Untuk setiap bilangan \(e\) pembagi habis \(a\) dan \(b\), maka \(e|d\) dan \(e \le d\).
Selanjutnya, faktor persekutuan terbesar \(d\) dari bilangan \(a\) dan \(b\) dinotasikan:
\(\text{FPB}(a, b) = d\) atau \(\text{GCD}(a, b) = d\) atau \((a, b) = d\)
(ii). Sifat-sifat FPB
Beberapa sifat berkaitan FPB:
- \((0, 0) = 0\)
- \((a, 0) = |a|\)
- \((a, b) = (|a|, |b|)\)
- \((a, b) = (b, a)\)
- \((a, b, c) = (a, (b, c))\)
- \((a + cb, b) = (a, b)\)
- Jika \((a, b) = d\), maka \(\left(\frac{a}{d}, \frac{b}{d}\right) = 1\).
- \((ma, mb) = m(a, b)\).
- \(0 \le (a, b) \le \min(|a|, |b|)\).
(iii). Pengertian Relatif Prima
Dua buah bilangan bulat \(a\) dan \(b\) disebut relatif prima (relative prime) jika \(\text{FPB}(a, b) = 1\).
Definisi Fungsi Euler
Untuk setiap bilangan bulat positif \(N\), didefinisikan \(\phi(N)\) adalah banyaknya bilangan bulat positif yang kurang dari atau sama dengan \(N\) yang relatif prima dengan \(N\). Misalkan faktorisasi prima \(N\) yaitu \(N = p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \dots \times p_n^{k_n}\).
Maka \(\phi(N) = p_1^{k_1-1}(p_1 - 1) \dots p_n^{k_n-1}(p_n - 1)\) atau \(\phi(N) = N\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_n}\right)\).
Contoh 1:
Tentukan:
a. nilai dari \(\phi(100)\)?
b. jumlah semua nilai \(n\) sehingga \(\phi(n) = 20\).
Penyelesaian Contoh 1:
a. Faktorisasi prima dari \(100 = 2^2 \times 5^2\).
\(\phi(100) = 100 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{5}\right) = 100 \times \frac{1}{2} \times \frac{4}{5} = 40\).
b. Diketahui \(\phi(n) = 20\). Nilai \(n\) yang memenuhi dapat dianalisis dari rumus fungsi Euler:
- Jika \(n = 25 \implies \phi(25) = 5^1(5 - 1) = 20\).
- Jika \(n = 33 \implies \phi(33) = \phi(3)\phi(11) = 2 \times 10 = 20\).
- Jika \(n = 44 \implies \phi(44) = \phi(4)\phi(11) = 2 \times 10 = 20\).
- Jika \(n = 50 \implies \phi(50) = \phi(2)\phi(25) = 1 \times 20 = 20\).
- Jika \(n = 66 \implies \phi(66) = \phi(2)\phi(3)\phi(11) = 1 \times 2 \times 10 = 20\).
Nilai \(n\) yang memenuhi adalah \(25, 33, 44, 50, \text{dan } 66\).
Jumlah semua nilai \(n = 25 + 33 + 44 + 50 + 66 = 218\).
(iv). Identitas Bezout
Jika \(a\) dan \(b\) dua buah bilangan bulat dan \(\text{FPB}(a, b) = d\), maka terdapat bilangan bulat \(m\) dan \(n\) sehingga \(d = ma + nb\).
(v). Cara Menentukan FPB
Ada beberapa cara untuk menentukan FPB yaitu cara mendaftar, cara tabel, faktorisasi prima, Algoritma Euclid, dan lainnya. Kita akan membahas dua cara terakhir.
a). Menentukan FPB dengan Faktorisasi Prima
Misalkan terdapat dua buah bilangan bulat yaitu \(a\) dan \(b\) yang kita ubah ke dalam bentuk faktorisasi primanya:
\(a = p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \dots \times p_n^{k_n}\)
\(b = p_1^{m_1} \times p_2^{m_2} \times p_3^{m_3} \times \dots \times p_n^{m_n}\)
Maka \(\text{FPB}(a, b) = p_1^{\min(k_1, m_1)} \times p_2^{\min(k_2, m_2)} \times p_3^{\min(k_3, m_3)} \times \dots \times p_n^{\min(k_n, m_n)}\).
Min artinya minimum (nilai terkecil).
Contoh 2:
Tentukan FPB dari 36 dan 30?
Penyelesaian Contoh 2:
\(36 = 2^2 \times 3^2\)
\(30 = 2^1 \times 3^1 \times 5^1\)
\(\text{FPB}(36, 30) = 2^{\min(2,1)} \times 3^{\min(2,1)} \times 5^{\min(0,1)} = 2^1 \times 3^1 = 6\).
b). Menentukan FPB dengan Algoritma Euclid
- Teorema Euclid:
Misalkan \(a\) dan \(b\) adalah bilangan bulat dengan syarat \(b > 0\). Jika \(a\) dibagi dengan \(b\), maka terdapat dua buah bilangan bulat unik \(q\) (quotient) dan \(r\) (remainder), sedemikian sehingga \(a = b \cdot q + r\) dengan \(0 \le r < b\). - Cara mencari \(\text{FPB}(a, b)\) dengan \(a > b\) yaitu:
\(a = b \cdot q_1 + r_1, \quad 0 \le r_1 < b\)
\(b = r_1 \cdot q_2 + r_2, \quad 0 \le r_2 < r_1\)
\(r_1 = r_2 \cdot q_3 + r_3, \quad 0 \le r_3 < r_2\)
\(\dots\)
\(r_{n-2} = r_{n-1} \cdot q_n + r_n, \quad 0 \le r_n < r_{n-1}\)
\(r_{n-1} = r_n \cdot q_{n+1} + 0\)
Maka \(\text{FPB}(a, b) = r_n\).
Contoh 3:
Tentukan FPB dari bilangan berikut dengan algoritma Euclid:
a. 18 dan 30
b. 10 dan 45
c. 105, 140, dan 350
Penyelesaian Contoh 3:
a. 18 dan 30:
\(30 = 18(1) + 12\)
\(18 = 12(1) + 6\)
\(12 = 6(2) + 0 \implies \text{FPB} = 6\).
b. 10 dan 45:
\(45 = 10(4) + 5\)
\(10 = 5(2) + 0 \implies \text{FPB} = 5\).
c. 105, 140, dan 350:
Cari \(\text{FPB}(105, 140)\):
\(140 = 105(1) + 35\)
\(105 = 35(3) + 0 \implies \text{FPB}(105, 140) = 35\).
Selanjutnya cari \(\text{FPB}(35, 350)\):
\(350 = 35(10) + 0 \implies \text{FPB} = 35\).
Contoh 4:
Carilah salah satu pasangan bilangan bulat \((x, y)\) sehingga \(15x + 24y = 3\).
Penyelesaian Contoh 4:
Bagi seluruh persamaan dengan \(\text{FPB}(15, 24) = 3\):
\(5x + 8y = 1\).
Gunakan Algoritma Euclid mundur:
\(8 = 5(1) + 3 \implies 3 = 8 - 5\)
\(5 = 3(1) + 2 \implies 2 = 5 - 3 = 5 - (8 - 5) = 2(5) - 8\)
\(3 = 2(1) + 1 \implies 1 = 3 - 2 = (8 - 5) - (2(5) - 8) = 2(8) - 3(5)\).
Maka \(5(-3) + 8(2) = 1\). Kalikan 3 untuk mendapatkan persamaan awal:
\(15(-9) + 24(6) = 3\).
Jadi, salah satu pasangannya adalah \((x, y) = (-9, 6)\).
B). Kelipatan Persekutuan Terkecil (KPK)
(i). Pengertian KPK
Suatu bilangan positif \(d\) disebut kelipatan persekutuan terkecil (least common multiple / LCM) dari bilangan \(a\) dan \(b\) jika:
- \(d\) kelipatan dari \(a\) dan \(b\) (\(a|d\) dan \(b|d\)).
- Untuk setiap bilangan \(e\) kelipatan dari \(a\) dan \(b\), maka \(d|e\).
Selanjutnya dinotasikan:
\(\text{KPK}(a, b) = d\) atau \(\text{LCM}(a, b) = d\) atau \([a, b] = d\)
(ii). Cara Menentukan KPK dengan Faktorisasi Prima
Misalkan terdapat dua buah bilangan bulat yaitu \(a\) dan \(b\) yang kita ubah ke dalam bentuk faktorisasi primanya:
\(a = p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \dots \times p_n^{k_n}\)
\(b = p_1^{m_1} \times p_2^{m_2} \times p_3^{m_3} \times \dots \times p_n^{m_n}\)
Maka \(\text{KPK}(a, b) = p_1^{\text{maks}(k_1, m_1)} \times p_2^{\text{maks}(k_2, m_2)} \times p_3^{\text{maks}(k_3, m_3)} \times \dots \times p_n^{\text{maks}(k_n, m_n)}\).
Maks artinya maksimum (terbesar).
Contoh 5:
Tentukan KPK dari 18 dan 30?
Penyelesaian Contoh 5:
\(18 = 2^1 \times 3^2\)
\(30 = 2^1 \times 3^1 \times 5^1\)
\(\text{KPK}(18, 30) = 2^{\text{maks}(1,1)} \times 3^{\text{maks}(2,1)} \times 5^{\text{maks}(0,1)} = 2^1 \times 3^2 \times 5^1 = 90\).
C). Hubungan FPB dan KPK
Perhatikan bentuk berikut:
\(a = p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \dots \times p_n^{k_n}\)
\(b = p_1^{m_1} \times p_2^{m_2} \times p_3^{m_3} \times \dots \times p_n^{m_n}\)
\(\text{FPB}(a, b) = p_1^{\min(k_1, m_1)} \times p_2^{\min(k_2, m_2)} \times p_3^{\min(k_3, m_3)} \times \dots \times p_n^{\min(k_n, m_n)}\)
\(\text{KPK}(a, b) = p_1^{\text{maks}(k_1, m_1)} \times p_2^{\text{maks}(k_2, m_2)} \times p_3^{\text{maks}(k_3, m_3)} \times \dots \times p_n^{\text{maks}(k_n, m_n)}\)
Maka kita simpulkan hubungan FPB dan KPK:
\(\text{FPB}(a, b) \times \text{KPK}(a, b) = a \times b\)
Contoh 6:
Diketahui FPB dan KPK dari \((68 - a)\) dan \((a + 7)\) adalah 25 dan 50. Tentukan nilai \(a + 5\)?
Penyelesaian Contoh 6:
\(\text{FPB} \times \text{KPK} = (68 - a)(a + 7) = 25 \times 50 = 1250\).
Karena \(\text{FPB} = 25\), maka \((68 - a)\) dan \((a + 7)\) adalah kelipatan 25.
Jumlahkan kedua bilangan: \((68 - a) + (a + 7) = 75\).
Karena \(75 = 25(x + y)\), maka \(x + y = 3\). Dengan \(\text{FPB}(x, y) = 1\), pasangan \((x, y)\) yang mungkin adalah \((1, 2)\) atau \((2, 1)\).
- Jika \(68 - a = 25(1) \implies a = 43\). Cek \(43 + 7 = 50 = 25(2)\) (memenuhi).
- Jika \(68 - a = 25(2) \implies a = 18\). Cek \(18 + 7 = 25(1)\) (memenuhi).
Untuk \(a = 43\), nilai \(a + 5 = 43 + 5 = 48\).
Untuk \(a = 18\), nilai \(a + 5 = 18 + 5 = 23\).
Contoh 7:
Bila KPK dan FPB dari empat bilangan berbeda \(18, 24, 18n,\) dan \(72\) adalah \(72\) dan \(6\), tentukan nilai \(n\) bilangan asli yang memenuhi.
Penyelesaian Contoh 7:
Diketahui bilangan-bilangan tersebut adalah \(18, 24, 18n, 72\) dengan \(\text{KPK} = 72\) dan \(\text{FPB} = 6\).
Karena \(18n\) harus membagi habis \(\text{KPK}\) (yaitu 72), maka \(18n | 72 \implies n\) bisa bernilai \(1, 2, 4\).
- Jika \(n = 1\), bilangan menjadi \(18, 24, 18, 72\) (tidak memenuhi karena harus bilangan berbeda).
- Jika \(n = 2\), bilangan menjadi \(18, 24, 36, 72\). FPB \(= 6\) dan KPK \(= 72\) (memenuhi).
- Jika \(n = 4\), bilangan menjadi \(18, 24, 72, 72\) (tidak berbeda).
Jadi, nilai \(n\) yang memenuhi adalah \(2\).
Contoh 8:
Misalkan \(d = \text{FPB}(7n + 5, 5n + 4)\), dimana \(n\) adalah bilangan asli.
a. buktikan bahwa untuk setiap bilangan asli \(n\) berlaku \(d = 1\) atau \(d = 3\).
b. buktikan bahwa \(d = 3\) jika dan hanya jika \(n = 3k + 1\), untuk setiap bilangan asli \(k\).
Penyelesaian Contoh 8:
a. Berdasarkan sifat FPB, \(d\) membagi kombinasi linear:
\(d | [5(7n + 5) - 7(5n + 4)] \implies d | [35n + 25 - 35n - 28] \implies d | (-3)\).
Karena pembagi dari \(-3\) adalah \(\pm 1, \pm 3\), dan \(d\) positif, maka \(d = 1\) atau \(d = 3\). Terbukti.
b. \(d = 3 \iff 3 | (7n + 5) \iff 7n + 5 \equiv 0 \pmod 3 \iff n + 2 \equiv 0 \pmod 3 \iff n \equiv 1 \pmod 3\).
Artinya, \(n = 3k + 1\) untuk suatu bilangan asli \(k\). Terbukti.
Contoh 9:
Banyaknya anggota himpunan \(S = \{\text{FPB}(n^3 + 1, n^2 + 3n + 9) \mid n \in \mathbb{Z}\}\) adalah \(\dots\)
Penyelesaian Contoh 9:
Misalkan \(d = \text{FPB}(n^3 + 1, n^2 + 3n + 9)\). Artinya \(d\) membagi kedua bentuk aljabar tersebut:
\(d \mid (n^3 + 1)\) dan \(d \mid (n^2 + 3n + 9)\)
Perhatikan kombinasi linear berikut:
\(d \mid [(n^2 + 3n + 9) \cdot n - (n^3 + 1)] \implies d \mid (3n^2 + 9n - 1)\)
Selanjutnya eliminasi suku kuadratnya dengan mengalikan 3 pada \(n^2 + 3n + 9\):
\(d \mid [(n^2 + 3n + 9) \cdot 3 - (3n^2 + 9n - 1)] \implies d \mid 28\)
Faktor positif dari 28 adalah \(d \in \{1, 2, 4, 7, 14, 28\}\).
Sekarang uji paritas untuk \(n\):
- Jika \(n\) genap, maka \(n^3 + 1\) ganjil, sehingga \(d\) tidak mungkin genap.
- Jika \(n\) ganjil, maka \(n^2 + 3n + 9\) ganjil, sehingga \(d\) juga tidak mungkin genap.
Karena \(d\) tidak mungkin genap, maka faktor-faktor genap (\(2, 4, 14, 28\)) tidak memenuhi.
Sehingga nilai \(d\) yang mungkin adalah \(1\) dan \(7\).
Jadi, himpunan \(S = \{1, 7\}\), sehingga banyaknya anggota dari \(S\) adalah 2.
Contoh 10:
Buktikan bahwa untuk setiap bilangan bulat positif \(n\), pecahan \(\frac{21n + 4}{14n + 3}\) tidak bisa disederhanakan lagi.
Penyelesaian Contoh 10:
Misalkan \(d = \text{FPB}(21n + 4, 14n + 3)\).
Maka \(d\) harus membagi kombinasi linear:
\(d | [2(21n + 4) - 3(14n + 3)] \implies d | [(42n + 8) - (42n + 9)] \implies d | (-1)\).
Karena \(d\) adalah faktor positif dari \(-1\), maka \(d = 1\).
Karena \(\text{FPB} = 1\), pecahan tersebut tidak dapat disederhanakan lagi. Terbukti.
Soal Latihan
1. Bilangan asli terkecil lebih dari 2011 yang bersisa 1 jika dibagi 2, 3, 4, 5, 6, 7, 8, 9, 10 adalah \(\dots\)
2. Nilai dari \(\sum_{k=1}^{2009} \text{FPB}(k, 7)\) adalah \(\dots\)
3. Tiga bilangan asli \(a_1 < a_2 < a_3\) memenuhi \(\text{FPB}(a_1, a_2, a_3) = 1\), tetapi \(\text{FPB}(a_i, a_j) > 1\) jika \(i \neq j, i, j = 1, 2, 3\). Tentukan \((a_1, a_2, a_3)\) agar \(a_1 + a_2 + a_3\) minimal.
4. Ada berapa banyak nilai \(m\) sehingga \(\text{KPK}(6^6, 8^8, m) = 12^{12}\)?
5. Dari setiap bilangan satu-angka \(a\), bilangan \(N\) dibuat dengan menyandingkan ketiga bilangan \(a + 2, a + 1, a\) yaitu \(N = (a + 2)(a + 1)a\). Sebagai contoh, untuk \(a = 8, N = 1098\). Kesepuluh bilangan \(N\) semacam itu memiliki faktor persekutuan terbesar \(\dots\)?
6. Tentukan semua pasangan bilangan bulat positif \((a, b)\) yang memenuhi:
\(\text{FPB}(a, b) + \text{KPK}(a, b) = a + b + 6\).
7. Misalkan \(x, y, z\) tiga bilangan asli berbeda. FPB ketiganya adalah 12, sedangkan KPK ketiganya adalah 840. Berapakah nilai terbesar dari \(x + y + z\)?
8. Misalkan \(a\) dan \(b\) dua bilangan asli, yang satu bukan kelipatan yang lainnya. Misalkan juga \(\text{KPK}(a, b)\) adalah bilangan 2-angka, sedangkan \(\text{FPB}(a, b)\) dapat diperoleh dengan membalik urutan angka pada \(\text{KPK}(a, b)\). Tentukan \(b\) terbesar yang mungkin.
9. Tentukan nilai dari
\(\text{FPB}(2002 + 2, 2002^2 + 2, 2002^3 + 2, \dots)?\)
10. Misalkan \(a\) dan \(b\) adalah bilangan bulat positif berbeda sehingga \(ab(a + b)\) habis dibagi oleh \(a^2 + ab + b^2\). Buktikan bahwa \(|a - b| > \sqrt[3]{ab}\).
11. Tentukan FPB dari bilangan-bilangan
\(A_n = 2^{3n} + 3^{6n+2} + 5^{6n+2}\)
dengan \(n = 0, 1, 2, 3, \dots, 1999\).
12. Untuk bilangan asli \(a\) dan \(b\), \(\frac{a+1}{b} + \frac{b+1}{a}\) adalah bilangan bulat. Tunjukkan bahwa FPB dari \(a\) dan \(b\) tidak lebih besar dari \(\sqrt{a + b}\).
13. Tentukan semua FPB dari bilangan asli \(m\) dan \(n\) jika setelah \(m\) ditambahkan 6 maka FPB kedua bilangan tersebut menjadi 9 kali FPB sebelumnya.
14. Jika \(\text{FPB}(a, b) = 1\), maka buktikan bahwa \(\text{FPB}(a + b, a^2 - ab + b^2)\) bernilai 1 atau 3.
15. Diketahui \(\text{FPB}(a, 2008) = 251\). Jika \(a > 2008\) maka nilai terkecil yang mungkin bagi \(a\) adalah \(\dots\)
16. Buktikan bahwa pecahan \(\frac{n^2 + n - 1}{n^2 + 2n}\) tidak dapat disederhanakan untuk semua nilai \(n\) bilangan asli.
17. Misalkan \(d(n)\) adalah FPB dari \(100 + n^2\) dan \(100 + (n + 1)^2\) untuk setiap \(n\) bilangan asli. Tentukan nilai \(d(n)\) yang terbesar.
18. Misalkan \(n\) adalah bilangan genap dan \(\text{FPB}(a, b) = 1\). Tentukan nilai \(a\) dan \(b\) bilangan asli jika \(a + b\) membagi \(a^n + b^n\).
Kembali ke Daftar Isi Olimpiade Matik SMA
Demikian pembahasan materi FPB dan KPK Olim Matik SMA dan contoh-contohnya. Silahkan juga baca materi lain yang berkaitan dengan materi ini. Setiap artikel akan diupdate secara bertahap. Jika ada kritik dan saran, atau koreksi dari isi artikel di halaman ini, mohon bantuannya untuk menuliskannya di kolom komentar di bagian bawah setiap artikel. Ini sangat membantu untuk memperbaiki kualitas dari artikel di blog koma. Semoga bermanfaat. Terimakasih.
