Algoritma Euclid mencari faktor persekutuan terbesar (FPB) dua bilangan lewat pembagian bersisa berulang, tanpa memfaktorkan. Untuk 462/1071 cukup tiga pembagian: FPB-nya 21 dan pecahannya menjadi 22/51. Kalau kamu hanya butuh hasilnya, kalkulator FPB memberikannya seketika; panduan ini menjelaskan cara menghitung dengan tangan dan alasan metodenya selalu berakhir di FPB.
Intinya satu kalimat: FPB dua bilangan tidak berubah kalau bilangan yang lebih besar diganti dengan sisa pembagiannya oleh bilangan yang lebih kecil. Ulangi sampai sisanya 0, dan pembagi terakhir yang dipakai adalah FPB.
Setiap baris memenuhi yang dibagi = hasil bagi × pembagi + sisa, dengan sisa lebih kecil dari pembagi. Yang dibawa ke baris berikutnya hanya pembagi dan sisa, bukan hasil bagi. Perkalian silang pada pemeriksaan sama dengan yang dipakai untuk membandingkan pecahan, dan membagi kedua suku dengan bilangan yang sama adalah pembeda antara menyederhanakan dan memperbesar pecahan, seperti dijelaskan di pecahan senilai.
Mengapa sisa saja sudah cukup
Jika a = q × b + r, setiap bilangan yang membagi a dan b juga membagi r, karena r = a − q × b. Sebaliknya, bilangan yang membagi b dan r juga membagi a. Jadi pasangan (a, b) dan (b, r) punya pembagi persekutuan yang sama, dan yang terbesar pun sama. Itulah sebabnya FPB(a, b) = FPB(b, r). Karena setiap sisa lebih kecil dari sisa sebelumnya, rangkaian itu turun terus sampai mencapai 0.
Gagasan yang sama bisa dilihat dengan persegi. Persegi panjang 1071 kali 462 ditutup dengan dua persegi bersisi 462; pada lajur yang tersisa muat tiga persegi bersisi 147, dan pada jalur terakhir muat tujuh persegi bersisi 21. Persegi terkecil yang mengisi semuanya tanpa celah bersisi 21, yaitu FPB.
Contoh soal: menyederhanakan 462/1071
Kamu ingin mengubah 462/1071 ke bentuk paling sederhana, tetapi tidak langsung melihat pembagi persekutuan.
- Bagi bilangan yang lebih besar dengan yang lebih kecil. 1071 = 2 × 462 + 147.
- Pindah ke pasangan pembagi dan sisa. Sekarang 462 dan 147: 462 = 3 × 147 + 21.
- Ulangi dengan pasangan baru. Sekarang 147 dan 21: 147 = 7 × 21 + 0. Sisanya 0, jadi rangkaian berhenti.
- Ambil pembagi terakhir. FPB-nya 21.
- Bagi pembilang dan penyebut dengan 21. 462 ÷ 21 = 22 dan 1071 ÷ 21 = 51.
Hasil: 462/1071 = 22/51.
Pemeriksaan: dengan perkalian silang, 462 × 51 = 23.562 dan 1071 × 22 = 23.562, jadi nilainya sama. Selain itu, 22 = 2 × 11 dan 51 = 3 × 17 tidak punya faktor persekutuan.
Contoh kedua, dengan lima pembagian
Untuk 3600/4284, mulailah dari bilangan yang lebih besar, 4284. Rangkaiannya:
- 4284 = 1 × 3600 + 684
- 3600 = 5 × 684 + 180
- 684 = 3 × 180 + 144
- 180 = 1 × 144 + 36
- 144 = 4 × 36 + 0
FPB-nya 36, dan 3600 ÷ 36 = 100 serta 4284 ÷ 36 = 119, jadi pecahannya menjadi 100/119. Kalau kamu mulai dari bilangan yang lebih kecil, pembagian pertama menghasilkan hasil bagi 0 dan hanya menukar pasangan; hasilnya sama, dengan satu langkah tambahan.
Euclid atau faktorisasi prima
Untuk mencari FPB ada dua jalan, dan masing-masing unggul di bidang yang berbeda.
| Metode | Yang dilakukan | Hasil | Kapan cocok |
|---|---|---|---|
| Euclid | Membagi bersisa sampai mencapai 0 | 5 pembagian, FPB 36 | Bilangan besar, atau saat hanya FPB yang dibutuhkan |
| Faktorisasi prima | Memfaktorkan lalu mengambil faktor persekutuan berpangkat terkecil | 2² × 3² = 36 | Bilangan kecil, atau saat KPK juga dibutuhkan |
Dengan 4284 = 2² × 3² × 7 × 17 dan 3600 = 2⁴ × 3² × 5², faktorisasi menuntut kita menemukan semua faktor prima, dan satu faktor besar memperpanjang pencarian. Algoritma Euclid tidak perlu mencarinya sama sekali. Kalau kamu juga butuh KPK, faktorisasi prima langsung memberikannya, dan panduan perbedaan FPB dan KPK menjelaskan kapan memakai masing-masing. Ciri bilangan habis dibagi menghemat langkah saat pembagi persekutuannya sudah jelas.
Kesalahan yang terlihat seperti jawaban benar
Kesalahan paling umum adalah membawa hasil bagi, bukan sisa, sehingga menghasilkan FPB yang tampak masuk akal.
Kesalahan serupa lainnya adalah berhenti di sisa yang kecil sebelum mencapai 0: FPB adalah pembagi terakhir, bukan sisa pertama yang tampak mudah dipakai. Dan untuk menyederhanakan, kedua suku harus dibagi dengan FPB, bukan salah satunya saja, kalau tidak nilainya berubah.
Kapan dipakai dan ke mana setelah ini
Euclid bekerja dengan dua bilangan bulat sekaligus dan hanya mengembalikan FPB. Untuk pecahan kecil seperti 6/8, mengenali angka 2 sekilas lebih cepat. Untuk berlatih dengan pecahan apa pun, alat menyederhanakan pecahan memakai FPB dan menampilkan bentuk paling sederhana. Kalau kamu tertarik pada cara lain menuliskan pecahan, panduan pecahan berlanjut dan pecahan Mesir memakai pembagian yang sama: hasil bagi pada rangkaian itu adalah suku-suku pecahan berlanjut.