KPK dan FPB

Kelipatan Persekutuan Terkecil

Dalam aritmetika dan teori bilangan, kelipatan persekutuan terkecil (KPK) dari dua bilangan adalah bilangan bulat positif terkecil yang dapat dibagi habis oleh kedua bilangan itu.

Dalam bahasa Inggris KPK dikenal dengan Least Common Multiple (LCM), sering juga disebut sebagai Lowest Common Multiple (LCM) atau Smallest Common Multiple (SCM),

Cara sederhana dapat digunakan untuk mencari KPK dari 2 atau 3 bilangan yang tidak terlalu besar, namun untuk bilangan yang lebih besar sebaiknya menggunakan cara faktorial.

Cara sederhana

Mencari KPK dari 12 dan 20:

• Kelipatan dari 12 = 12, 24, 36, 48, 60, 71, 84, ...
• Kelipatan dari 20 = 20, 40, 60, 80, 100, 120, 140, ...
• KPK dari 12 dan 20 adalah kelipatan sekutu (sama) yang terkecil, yaitu 60.

Cara faktorial

Mencari KPK dari bilangan 147, 189 dan 231:

• Buat pohon faktor dari masing-masing bilangan:

             147         189             231

              /\          /\              /\

             3 49        3  63           3  77

               /\           /\              /\

              7  7         7  9            7  11

                              /\

                             3  3

• Susun bilangan dari pohon faktor utk mendapatkan faktorialnya:

Faktorial 147 = 3¹ x 7²

Faktorial 189 = 3³ x 7¹

Faktorial 231 = 3¹ x 7¹ x 11¹

• Ambil faktor-faktor yang memiliki pangkat terbesar, dalam hal ini 3³, 7² dan 11¹.

• Kalikan faktor-faktor tesebut: 3³ x 7² x 11¹ = 14553.

• Maka KPK dari bilangan 147, 189 dan 231 adalah 14553. Dengan kata lain, tidak ada bilangan yang lebih kecil dari 14553 yang dapat dibagi habis oleh bilangan 147, 189 dan 231.

Faktor persekutuan terbesar

Dalam matematika, Faktor Persekutuan Terbesar (FPB) dari dua bilangan adalah bilangan bulat positif terbesar yang dapat membagi habis kedua bilangan itu.

Dalam bahasa Inggris FPB dikenal dengan Greatest Common Divisor (GCD), sering djiuga disebut sebagai Greatest Common Factor (GCF) atau Highest Common Factor (HCF),

Cara sederhana dapat digunakan untuk mencari FPB dari 2 atau 3 bilangan yang tidak terlalu besar, namun untuk bilangan yang lebih besar sebaiknya menggunakan cara faktorial.

Cara sederhana

Mencari FPB dari 12 dan 20:

• Faktor dari 12 = 1, 2, 3, 4, 6 dan 12
• Faktor dari 20 = 1, 2, 4, 5, 10 dan 20
• FPB dari 12 dan 20 adalah faktor sekutu (sama) yang terbesar, yaitu 4.

Cara faktorial

Mencari FPB dari bilangan 147, 189 dan 231:

• Buat pohon faktor dari masing-masing bilangan:

             147         189             231

              /\          /\              /\

             3 49        3  63           3  77

               /\           /\              /\

              7  7         7  9            7  11

                              /\

                             3  3

• Susun bilangan dari pohon faktor utk mendapatkan faktorialnya:

Faktorial 147 = 3¹ x 7²

Faktorial 189 = 3³ x 7¹

Faktorial 231 = 3¹ x 7¹ x 11¹

• Ambil faktor-faktor yang sekutu (sama) dari ketiga faktorial tersebut, dalam hal ini 3 dan 7.

• Kalikan faktor-faktor sekutu yang memiliki pangkat terkecil, dalam hal ini 3¹ x 7¹ = 21.

• Maka FPB dari bilangan 147, 189 dan 231 adalah 21. Dengan kata lain, tidak ada bilangan yang lebih besar dari 21 yang dapat membagi habis bilangan 147, 189 dan 231.

Algoritma Euklidean

Cara lain untuk mencari FPB adalah dengan menggunakan algoritma Euklidean. Misalkan a dan b adalah 2 bilangan bulat yang tidak sama, maka algoritma Eucliden adalah sebagai berikut:

· a₁ = maximum(a,b)-minimum(a,b)

b₁ = minimum(a,b)

· a₂ = maximum(a₁,b₁)-minimum(a₁,b₁)

b₂ = minimum(a₁,b₁)

· a_i = maximum(a_i-1,b_i-1)-minimum(a_i-1,b_i-1)

b_i = minimum(a_i-1,b_i-1)

Algoritma tersebut berhenti hingga diperoleh a_i = b_i

FPB dari a dan b adalah a_i = b_i

Algoritma Euklidean (juga disebut Algoritma Euklid) adalah suatu algoritma untuk menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritma ini adalah salah satu algoritma yang tertua, dan muncul dalam buku Elemen Euklid sekitar 300 SM. Algoritma ini tidak memerlukan faktorisasi.

Algoritma dan implementasi

Diberikan dua bilangan asli a dan b, periksa apakah b adalah nol. Jika ya, a adalah FPB. Jika tidak, ulangi proses tadi menggunakan b dan sisa setelah a dibagi oleh b (ditulis sebagai a modulus b). Algoritma ini dapat dinyatakan dengan menggunakan rekursi kanan:

function fpb(a, b)

     if b = 0

         return a

     else

         return fpb(b, a modulus b);

Secara iteratif, fungsi ini dapat ditulis sebagai:

 function fpb(a, b)

     while b ≠ 0

         var t := b

         b := a modulus b

         a := t

     return a

Sebagai contoh, FPB dari 1071 dan 1029 yang dihitung dengan menggunakan algoritma ini adalah 21, dengan langkah-langkah sebagai berikut:

a	b	t
1071	1029	42
1029	42	21
42	21	0
21	0

Dengan mencatat hasil bagi (yang merupakan bilangan bulat) selama menjalankan algoritma, kita juga dapat menentukan bilangan bulat p dan q di mana ap + bq = fpb(a, b). Hal ini dikenal sebagai Ekstensi Algoritma Euklidean.

Algoritma ini dapat digunakan dalam konteks di mana pembagian bersisa memungkinkan. Ini termasuk polinomial cincin dalam suatu medan, juga cincin dari bilangan bulat Gaussian, dan dalam domain Euklidean umum.

Euklid pada mulanya merumuskan masalah ini secara geometri, sebagai masalah untuk mencari "satuan" yang dapat dipakai untuk panjang dari dua buah garis, dan algoritmanya berlangsung dengan mengulangi pengurangan dari sisi yang lebih pendek dari sisi yang lebih panjang. Implementasi ini sama dengan implementasi berikut ini, yang cukup tidak efisien dibandingkan dengan cara yang telah dijelaskan di atas:

 function fpb(a, b)

     while a ≠ b

         if a > b

             a := a - b

         else

             b := b - a

     return a

Bukti kebenaran

Tidaklah sulit untuk membuktikan bahwa algoritma itu benar. Misalkan a dan b adalah bilangan yang FPB-nya akan ditentukan. Dan misalkan sisa dari pembagian dari a oleh b adalah t. Maka a = qb + t di mana q adalah hasil bagi (yang merupakan bilangan bulat) dari pembagian tersebut. Sekarang, setiap pembagi dari a dan b juga dapat habis membagi t (karena t dapat ditulis sebagai t = a − qb); Dengan cara yang sama, setiap pembagi dari b dan t juga akan habis membagi a. Maka faktor persekutuan terbesar dari a dan b adalah sama dengan FPB dari b dan t. Oleh karena itu, kita cukup meneruskan proses tadi dengan b dan t saja. Karena t lebih kecil dalam nilai mutlak dari b, kita akan mencapai t = 0 setelah sejumlah langkah

KPK dan FPB

a. KPK dari 2 atau 3 Bilangan

Untuk menentukan KPK dari 2 atau 3 bilangan, harus diingat bahwa setiap bilangan adalah hasil kali faktor-faktor primanya. Oleh karena itu, 2 atau 3 bilangan yang akan dicari KPK-nya, harus ditentukan lebih dulu faktor-faktor primanya, kemudian menuliskannya ke dalam bentuk perkalian faktor prima (faktorisasi). Cara mencari faktor-faktor prima suatu bilangan adalah dengan pohon faktor. Untuk jelasnya, perhatikan contoh di bawah ini baik-baik!

1. Carilah KPK dari 12 dan 18!

Jawab:

12 = 2 x 2 x 3 = 2²x 3 (faktorisasi)

18 = 2 x 3 x 3 = 2 x 3² (faktorisasi)

KPK dari 12 dan 18 = 2 x 2 x 3 x 3 = 2² x 3³ = 4 x 9 = 36

2. Carilah KPK dari 15, 20, dan 30.

Jawab:

15 = 3 x 5 = 3 x 5 (faktorisasi)

20 = 2 x 2 x 5 = 2² x 5 (faktorisasi)

30 = 2 x 3 x 5 = 2 x 3 x 5 (faktorisasi)

KPK dari 15, 20, dan 30 = 2² x 3 x 5 = 4 x 3 x 5 = 60

Cara menentukan KPK.

1. Tulislah bilangan-bilangan itu dalam bentuk perkalian faktor prima (faktorisasi).

2. Ambil semua faktor, yang sama atau tidak sama, dari bilangan-bilangan itu.

3. Jika faktor yang sama dari setiap bilangan, tetapi banyaknya berbeda,

ambillah faktor yang paling banyak atau dari pangkat yang terbesar.

b. FPB dari 2 atau 3 Bilangan

Sama halnya mencari KPK, maka untuk menentukan FPB dari 2 atau 3 bilangan, harus ditentukan lebih dulu faktor-faktor primanya, kemudian menuliskannya dalam bentuk perkalian faktor prima (faktorisasi). Untuk jelasnya, perhatikan contoh di bawah ini baik-baik!

1. Carilah FPB dari 18 dan 24.

Jawab:

18 = 2 x 3 x 3. (faktorisasi)

24 = 2 x 2 x 2 x 3 (faktorisasi)

FPB dari 18 dan 24 = 2 x 3 = 6.

2. Carilah FPB dari 24, 36, dan 40.

Jawab:

24 = 2 x 2 x 2 x 3. (faktorisasi)

36 = 2 x 2 x 3 x 3. (faktorisasi)

40 = 2 x 2 x 2 x 5. (faktorisasi)

FPB dari 24, 36, dan 40 = 2 x 2 = 4.

Cara menentukan FPB:

1. Tuliskan bilangan itu dalam bentuk perkalian faktor prima (faktorisasi).

2. Ambil faktor yang sama dari bilangan-bilangan itu.

3. Jika faktor yang sama dari setiap bilangan, tetapi banyaknya berbeda, ambil faktor yang sedikit.

Menentukan KPK dan FPB dari 2 Bilangan atau lebih secara Bersamaan

Perhatikan contoh di bawah ini!

Tentukan KPK dan FPB dari 36 dan 48!

Cara I :

36 = 2 x 2 x 3 x 3 (faktorisasi)

48 = 2 x 2 x 2 x 2 x 3 (faktorisasi)

KPK dari 36 dan 48 = 2 x 2 x 2 x 2 x 3 x 3

= 16 x 9 = 144

FPB dari 36 dan 48 = 2 x 2 x 3

= 4 x 3

= 12

Contoh dalam Kehidupan :

A dan B pada suatu hari pergi bersama-sama ke perpustakaan. Kebiasaan A pergi ke perpustakaan setiap 6 hari, sedangkan B setiap 8 hari. Setelah berapa hari A dan B akan bersama-sama ke perpustakaan?

Jawab:

Diketahui : A pergi setiap 6 hari dan B pergi setiap 8 hari.

Ditanyakan : Tiap berapa hari A dan B datang bersama.

Penyelesaian : 6 = 2 x 3

8 = 2³

A dan B akan datang bersama setelah 2³ x 3 = 8 x 3 = 24

Jadi, A dan B datang bersama setelah 24 hari.

latihan KPK dan FPB

1. Tentukan KPK dari :
a. 60 dan 126
b. 36, 42 dan 48
c. 40, 50 dan 65
d. 75, 80 dan 95

2. Tentukan FPB dari
a. 150 dan 105
b. 70, 105 dan 175
c. 60, 75 dan 105
d. 80, 110 dan 125

3. Tias bermain tenis tiap 3 hari, dina tiap 4 hari dan kiki setiap 5 hari sekali. Bila mereka bertiga pada tanggal 20 Februari 1996 bermain bersama untuk yang pertama kali, pada tanggal berapa mereka akan main bersama lagi untuk ke-2 dan ke-3 kalinya.

4. Tiga orang A, B dan C mendapat tugas ronda. A bertugas setiap 4 hari sekali, B tiap 5 hari dan C tiap 6 hari sekali. Pada tanggal 27 Juli 1999 ketiga orang itu bertugas bersama untuk yang ke-2 kalinya. Pada tanggal berapa mereka bertugas bersama untuk yang ke-4 dan ke-5 kalinya?

5. Dari 88 putra dan 64 putri, seluruhnya akan dikelompokkan sehingga banyak anggota dari tiap-tiap kelompok putra dan putrid sama banyaknya. Hitunglah kelompok putra dan putrid dengan banyak anak tiap kelompok maksimal.

Menentukan FPB dan KPK

B. Menentukan FPB dan KPK

1. Menentukan FPB

Faktor persekutuan terbesar (FPB) dari dua bilangan telah kalian pelajari di Kelas V. Kalian juga telah mempelajari cara menentukan faktorisasi prima dari suatu bilangan. Marilah kita terapkan untuk menyelesaikan masalah berikut. Pak Yudi memiliki 12 apel dan 18 jeruk. Apel dan jeruk tersebut akan dimasukkan ke dalam kantong plastik. Berapa kantong plastik yang dibutuhkan, jika setiap kantong berisi apel dan jeruk dengan jumlah yang sama? Untuk menjawab soal tersebut, kamu harus mencari FPB dari 12 dan 18.

Langkah-langkah pengerjaan FPB.
1. Menentukan faktorisasi prima dari bilangan-bilangan itu.
2. Mengambil faktor yang sama dari bilangan-bilangan itu.
3. Jika faktor yang sama pangkatnya berbeda, ambillah faktor yang pangkatnya terkecil.

Perhatikan diagram berikut ini.

Faktorisasi prima dari 12 adalah 12 = 2 × 2 × 3 = 2² × 3.
Faktorisasi prima dari 18 adalah 18 = 2 × 3 × 3 = 2 × 3².
FPB dari 12 dan 18 adalah 2 × 3 = 6.
Jadi, kantong plastik yang diperlukan adalah 6 buah. Setiap kantong plastik
memuat 2 apel dan 3 jeruk, seperti terlihat pada gambar berikut.

Sekarang, kalian akan mempelajari cara menentukan FPB dari tiga bilangan.
Perhatikan contoh berikut.
Contoh 1
Tentukan FPB dari 12, 24, dan 42.
Jawab:

Faktorisasi prima dari 12 adalah 12 = 2 × 2 × 3 = 2² × 3.
Faktorisasi prima dari 24 adalah 24 = 2 × 2 × 2 × 3 = 2³ × 3.
Faktorisasi prima dari 42 adalah 42 = 2 × 3 × 7.
Jadi, FPB dari 12, 24, 24, dan adalah 2 × 3 = 6.
Contoh 2
Tentukan FPB dari 15, 25, dan 60.
Jawab:

Faktorisasi prima dari 15 adalah 15 = 3 × 5.
Faktorisasi prima dari 25 adalah 25 = 5 × 5.
Faktorisasi prima dari 60 adalah 60 = 2 × 2 ×3 × 5 = 2² × 3 × 5.
Jadi, FPB dari 15, 25, dan 60 adalah 5.

Ayo Berlatih

B. Ayo, kerjakanlah soal-soal cerita berikut di buku latihanmu.
1. Ibu memiliki 28 kue keju dan 40 kue donat. Kue-kue tersebut akan dimasukkan
ke dalam kotak-kotak. Jika setiap kotak memuat jumlah kue keju dan kue donat
dalam jumlah yang sama, berapa banyak kotak yang diperlukan ?
2. Ibu Siska akan membagikan 27 kemeja dan 45 celana pendek kepada anakanak
yang membutuhkan. Setiap anak memperoleh jumlah kemeja dan celana
pendek dalam jumlah yang sama.
a. Berapa banyak anak yang memperoleh kemeja dan celana pendek tersebut?
b. Berapa banyak kemeja dan celana pendek yang diperoleh setiap anak?
3. Seorang pedagang memiliki 42 permen rasa cokelat, 48 permen rasa jeruk, dan
60 permen rasa mangga. Ia menginginkan setiap stoples memuat ketiga jenis
permen tersebut dalam jumlah yang sama.
a. Berapa banyak stoples yang harus disediakan?
b. Berapa banyak permen rasa cokelat, rasa jeruk, dan rasa mangga dalam
setiap stoplesnya?

2. Menentukan KPK

Cara menentukan Kelipatan Persekutuan Terkecil (KPK) dari dua bilangan dengan menggunakan faktorisasi prima telah kamu pelajari di Kelas V. Ingatlah kembali materi tentang KPK tersebut karena kamu akan mempelajarinya lebih dalam di bab ini.

Pak Teguh mendapat tugas piket di sekolah setiap 12 hari sekali. Pak Didi mendapat tugas piket setiap 18 hari sekali. Tanggal 1 Juli 2007 mereka mendapat tugas piket secara bersamaan. Kapan mereka akan mendapat tugas piket secara bersamaan untuk yang kedua?

Untuk menjawab soal tersebut, kamu harus mencari KPK dari 12 dan 18.
Langkah-langkah menentukan KPK.
1. Tentukan faktorisasi prima dari bilangan-bilangan tersebut.
2. Ambil semua faktor yang sama atau tidak sama dari bilangan-bilangan tersebut.
3. Jika faktor yang sama memiliki pangkat berbeda, ambillah faktor yang pangkatnya terbesar.

Faktorisasi prima dari 12 adalah 12 = 2 × 2 × 3 = 2² ×3.
Faktorisasi prima dari 18 adalah 18 = 2 × 3 × 3 = 2 × 3².
KPK dari 12 dan 18 adalah 22 × 32 = 4 × 9 = 36.
Jadi, Pak Teguh dan Pak Didi akan mendapat tugas piket secara bersamaan
setiap 36 hari sekali. Coba kamu tentukan tanggal berapakah itu?
Kalian akan mempelajari cara mencari KPK dari tiga bilangan. Cara
menentukan KPK dari tiga bilangan sama seperti dalam mencari KPK dari dua
bilangan. Perhatikan contoh berikut.
Contoh
Tentukanlah KPK dari 8, 16, dan 40.
Jawab:

Faktorisasi prima dari 8 = 2 × 2 × 2 = 2³.
Faktorisasi prima dari 16 = 2 × 2 × 2 × 2 = 2⁴.
Faktorisasi prima dari 40 = 2 × 2 × 2 × 5 = 2³ × 5.
KPK dari 8, 16, dan 40 adalah 24 × 5 = 16 × 5 = 80.
Jadi, KPK dari 8, 16, dan 40 adalah 80.

Ayo Berlatih

A. Ayo, tentukanlah KPK dari bilangan-bilangan berikut di buku latihanmu.
1. 10 dan 12 5. 25 dan 45 9. 18, 32, dan 36
2. 15 dan 20 6. 32 dan 48 10. 9, 18, dan 54
3. 16 dan 24 7. 60 dan 80 11. 25, 45, dan 70
4. 18 dan 30 8. 45 dan 50 12. 50, 60, dan 70

B. Ayo, kerjakanlah soal-soal cerita berikut di buku latihanmu.
1. Lampu A menyala setiap 6 detik sekali, sedangkan
lampu B setiap 8 detik sekali. Setiap berapa
detik kedua lampu tersebut akan menyala secara bersamaan?
2. Frida berenang setiap 10 hari sekali. Tomi berenang
setiap 15 hari sekali. Tanggal 5 Maret 2008 mereka berenang bersama untuk
pertama kali. Kapan mereka akan berenang bersama untuk kedua kalinya dan
ketiga kalinya?
3. Pak Made mendapat tugas ronda setiap 6 hari sekali, sedangkan Pak Janu setiap
8 hari sekali. Adapun Pak Tono setiap 12 hari sekali. Tanggal 1 Juni 2008
mereka bertiga tugas ronda bersama untuk kali pertama. Kapan mereka akan
tugas ronda secara bersama untuk ketiga kalinya?

kalau kpk biasanya ada kata 'setiap'
misalnya: pintu a terbuka setiap 3 menit. pintu b terbuka setiap 5 menit. maka keduanya terbuka bersamaan setiap?

kalau fpb tiap bilangan yang muncul bukan bilangan prima.
misalnya: ada 144 kue dan 84 kado dibagi ke beberapa orang sama rata. berapa yang bakal kebagian?