GCF & LCM Calculator

Kalkulator FPB dan KPK untuk hingga 10 angka dengan langkah

Kalkulator FPB dan KPK ini mencari Faktor Persekutuan Terbesar (FPB/GCD/HCF) dan Kelipatan Persekutuan Terkecil (KPK) untuk hingga 10 bilangan bulat positif sekaligus. Masukkan angka Anda, dan hasilnya langsung muncul beserta proses langkah demi langkahnya — faktorisasi prima untuk KPK, langkah algoritma Euclid untuk FPB. Tambahkan lebih banyak kolom angka dengan tombol '+ Tambah angka'.

Semuanya berjalan di browser Anda. Tidak ada yang dikirim ke server. Tidak ada pendaftaran, tidak ada unggahan, dan tidak ada batas ukuran angka yang bisa Anda masukkan (meski angka yang sangat besar mungkin melebihi rentang integer aman JavaScript — untuk angka di atas 2^53, gunakan pustaka bignum).

Algoritma Euclid — cara FPB dihitung

Algoritma Euclid adalah metode standar untuk mencari FPB(a,b): berulang kali ganti angka yang lebih besar dengan sisa hasil bagi angka yang lebih besar oleh yang lebih kecil, sampai sisanya nol. Angka bukan-nol terakhir adalah FPB-nya. Ini berjalan dalam waktu O(log min(a,b)) — sangat cepat bahkan untuk angka yang sangat besar.

Contoh: FPB(252, 105). Langkah 1: 252 ÷ 105 = 2 sisa 42. Langkah 2: 105 ÷ 42 = 2 sisa 21. Langkah 3: 42 ÷ 21 = 2 sisa 0. FPB = 21. Kalkulator ini menampilkan langkah-langkah ini agar siswa bisa memverifikasi pengerjaan manual mereka atau mempelajari algoritmanya.

Faktorisasi prima — cara KPK dihitung

KPK paling jelas ditemukan lewat faktorisasi prima: faktorkan setiap angka menjadi bilangan prima, ambil pangkat tertinggi dari setiap prima yang muncul di faktorisasi mana pun, lalu kalikan. KPK(36, 48, 60): 36 = 2² × 3², 48 = 2⁴ × 3, 60 = 2² × 3 × 5. Pangkat tertinggi: 2⁴, 3², 5¹. KPK = 16 × 9 × 5 = 720.

Untuk dua angka, jalan pintasnya adalah KPK(a,b) = (a × b) ÷ FPB(a,b). Ini yang dipakai banyak kalkulator secara internal karena mencari FPB cepat lewat algoritma Euclid. Untuk tiga angka atau lebih, kalkulator ini merangkai: KPK(a,b,c) = KPK(KPK(a,b), c).

Kegunaan nyata: pecahan, penjadwalan, dan pemrograman

Kegunaan kelas paling umum dari FPB adalah menyederhanakan pecahan: bagi pembilang dan penyebut dengan FPB-nya untuk mencapai bentuk paling sederhana. Kegunaan utama KPK adalah mencari penyebut sama untuk menjumlahkan dan mengurangkan pecahan.

Dalam penjadwalan dunia nyata, KPK menjawab: 'Jika peristiwa A berulang setiap 12 hari dan peristiwa B berulang setiap 8 hari, kapan keduanya akan bertepatan lagi?' KPK(12,8) = 24 hari. Dalam pemrograman, FPB dan KPK muncul dalam aritmetika bilangan rasional, perhitungan rasio gigi, dan masalah tiling. Algoritma Euclid untuk FPB adalah salah satu algoritma tertua yang masih aktif dipakai dalam software modern.

Perbandingan dengan Wolfram Alpha, Mathway, dan symbolab.com

Wolfram Alpha menghitung FPB dan KPK dengan detail faktorisasi lengkap dan menangani angka yang sangat besar serta input simbolik. Ini alat paling andal untuk kasus kompleks. Mathway dan Symbolab menawarkan solusi langkah demi langkah serupa tapi mewajibkan akun gratis atau langganan berbayar untuk melihat langkahnya secara penuh — tampilan langkah Mathway berbiaya $9,99/bulan.

Alat ini menampilkan langkah tanpa mewajibkan akun apa pun. Ia menangani hingga 10 angka sekaligus (kebanyakan alat hanya 2–3). Ia dimuat tanpa beban jaringan iklan di halaman alatnya. Bagi siswa yang memeriksa PR atau developer yang butuh referensi cepat, ini lebih cepat daripada menavigasi antarmuka pencarian umum Wolfram Alpha atau membayar langganan Mathway.

Identitas FPB × KPK: mengapa berlaku dan cara memakainya

Untuk dua bilangan bulat positif a dan b, identitas FPB(a,b) × KPK(a,b) = a × b selalu berlaku. Untuk memahami mengapa, perhatikan faktorisasi prima setiap angka. Untuk setiap prima p, FPB mengambil eksponen minimum antara a dan b, sementara KPK mengambil eksponen maksimum. Karena min(x,y) + max(x,y) = x + y untuk dua eksponen mana pun, mengalikan FPB dan KPK merekonstruksi persis a × b dalam bentuk prima. Contoh: FPB(12,18) = 6 dan KPK(12,18) = 36; periksa: 6 × 36 = 216 = 12 × 18. ✓

Identitas ini berguna secara praktis ketika Anda sudah tahu satu nilai dan butuh yang lain. Misalkan Anda tahu FPB(a,b) = d dan butuh KPK-nya — cukup hitung KPK = (a × b) ÷ d. Ini menghindari faktorisasi dari awal. Identitas ini juga mengungkap kasus khusus: jika dua angka tidak berbagi faktor persekutuan lebih besar dari 1 (mereka koprima, disebut juga relatif prima), maka FPB = 1, jadi KPK = a × b. Contohnya, FPB(8,9) = 1, jadi KPK(8,9) = 72. Bilangan bulat berurutan selalu koprima, itulah mengapa KPK(n, n+1) = n(n+1) untuk n berapa pun.

Identitas ini tidak langsung berlaku untuk tiga angka atau lebih. FPB(a,b,c) × KPK(a,b,c) ≠ a × b × c secara umum. Contohnya, FPB(6,10,15) = 1 dan KPK(6,10,15) = 30, tapi 6 × 10 × 15 = 900 ≠ 30. Untuk tiga angka atau lebih, pendekatan yang benar adalah merangkai: hitung FPB atau KPK dari sepasang pertama, lalu terapkan operasi itu lagi dengan angka berikutnya.

Memperluas FPB dan KPK ke tiga angka atau lebih

Algoritma Euclid bersifat asosiatif dalam arti FPB(a,b,c) = FPB(FPB(a,b), c). Ini membuatnya mudah diperluas ke jumlah angka berapa pun: hitung FPB dari dua angka pertama, lalu hitung FPB hasil itu dengan angka ketiga, dan seterusnya. Hasil akhirnya tidak bergantung pada urutan angka diproses — Anda bisa mulai dengan pasangan mana pun. Untuk KPK, perangkaian yang sama berlaku: KPK(a,b,c) = KPK(KPK(a,b), c). Contoh: KPK(4, 6, 9) = KPK(KPK(4,6), 9) = KPK(12, 9) = 36.

Mencari FPB dari n angka lewat perangkaian membutuhkan n−1 penerapan algoritma Euclid. Karena setiap langkah mereduksi masalah menjadi pasangan yang lebih kecil, total kompleksitas waktunya tetap O(n · log M) di mana M adalah nilai input maksimum — tetap sangat cepat. Secara praktis, begini cara kalkulator dan pustaka standar bahasa pemrograman mengimplementasikan FPB multi-argumen: math.gcd Python menerima banyak argumen sejak Python 3.9, secara internal merangkai versi dua-argumen. JavaScript tidak punya FPB bawaan, tapi polanya sama.

Untuk pendekatan faktorisasi prima di banyak angka, kumpulkan semua faktor prima dari setiap angka, lalu ambil pangkat terendah dari setiap prima yang muncul di semua angka untuk FPB, atau pangkat tertinggi dari setiap prima yang muncul di angka mana pun untuk KPK. Contoh: FPB(12, 18, 24) di mana 12 = 2² × 3, 18 = 2 × 3², 24 = 2³ × 3. Prima yang sama: 2 (pangkat minimum 2¹ = 1) dan 3 (pangkat minimum 3¹ = 1). FPB = 2 × 3 = 6. KPK: pangkat maksimum adalah 2³ dan 3², jadi KPK = 8 × 9 = 72.

Konteks sejarah: algoritma Euclid dan warisannya

Algoritma untuk mencari pembagi persekutuan terbesar dicatat oleh matematikawan Yunani Euclid sekitar 300 SM dalam karya fundamentalnya Elements, khususnya di Buku VII, Proposisi 1 dan 2. Euclid mendeskripsikannya secara geometris — sebagai mengukur dua ruas garis dengan berulang kali mengurangkan yang lebih pendek dari yang lebih panjang — tapi interpretasi komputasionalnya (memakai pembagian bilangan bulat dengan sisa) setara. Ini menjadikannya salah satu algoritma numerik tertua dalam sejarah tercatat, mendahului konsep nol dalam matematika Barat selama berabad-abad.

Meski usianya tua, algoritma Euclid tetap sangat relevan. Ia mencapai O(log min(a,b)) langkah, yang optimal untuk algoritma FPB berbasis perbandingan pada bilangan bulat. Gabriel Lamé membuktikan pada 1844 bahwa jumlah langkah tidak pernah melebihi lima kali jumlah digit desimal pada angka yang lebih kecil — hasil pertama dalam teori kompleksitas komputasi. Algoritma ini mendasari kriptografi modern: Algoritma Euclid yang Diperluas, varian yang juga menghitung koefisien s dan t sehingga FPB(a,b) = s·a + t·b (identitas Bézout), sangat penting dalam enkripsi RSA untuk menghitung invers modular.

Algoritma ini juga terhubung dengan barisan Fibonacci dengan cara yang tak terduga: bilangan Fibonacci berurutan adalah input skenario terburuk untuk algoritma Euclid, membutuhkan jumlah langkah maksimum relatif terhadap ukuran angkanya. FPB(F(n+1), F(n)) selalu sama dengan 1, tapi algoritma ini membutuhkan tepat n langkah untuk membuktikannya. Itulah mengapa bilangan Fibonacci muncul dalam analisis algoritma untuk FPB dan menjadi dasar teorema Lamé.

Tiling, gigi, dan penjadwalan: soal FPB dan KPK terapan

Masalah tiling adalah aplikasi FPB klasik: diberikan lantai persegi panjang berdimensi a × b (dalam satuan bilangan bulat), berapa ubin persegi terbesar yang pas dengan lantai tersebut sempurna tanpa memotong? Jawabannya adalah FPB(a,b). Untuk lantai 24 × 36: FPB(24,36) = 12, jadi ubin 12 × 12 pas persis, dengan 2 kolom dan 3 baris ubin (24 ÷ 12 = 2, 36 ÷ 12 = 3). Mengganti FPB dengan faktor persekutuan yang lebih kecil mana pun juga akan menutupi lantai tapi memakai lebih banyak ubin dari yang diperlukan.

Masalah penjadwalan dan penyelarasan siklus diselesaikan dengan KPK. Jika lampu lalu lintas di persimpangan A bersiklus setiap 45 detik dan di persimpangan B setiap 60 detik, dan keduanya menyala hijau bersamaan pada waktu nol, waktu berikutnya keduanya hijau bersamaan adalah KPK(45,60) = 180 detik (3 menit). Masalah rasio gigi mengikuti logika yang sama: jika gigi A punya 12 gigi dan gigi B punya 18 gigi, setelah KPK(12,18) ÷ 12 = 3 putaran penuh A dan KPK(12,18) ÷ 18 = 2 putaran penuh B, kedua gigi kembali bersamaan ke orientasi awalnya. Insinyur memakai ini untuk mengidentifikasi kapan pola keausan berulang pada gigi yang saling bertautan.

Dalam teori musik, KPK menjelaskan penyelarasan polyrhythm. Polyrhythm 3-lawan-4 (triplet melawan not seperempat) bersiklus penuh setiap KPK(3,4) = 12 subdivisi. FPB memberi tahu Anda unit ritmis persekutuan terbesar. Dalam ilmu komputer, penyelarasan memori membutuhkan pencarian alamat yang merupakan kelipatan ukuran word; menentukan alamat terkecil semacam itu untuk dua persyaratan penyelarasan berbeda memakai KPK. Kriptografi memakai FPB langsung dalam langkah pembuatan kunci RSA, di mana pasangan kunci hanya valid ketika FPB(e, φ(n)) = 1, yaitu eksponen publik e harus koprima terhadap totient dari n.