FPB dan KPK dengan Algoritma Euclid

Oleh Daniel Wirajaya (website)

Co-founder, Acutis Academy; Director, QuBisa. Pakar e-learning dengan pengalaman industri lebih dari 20 tahun.

Memahami FPB dan KPK

Sebelum kita membahas lebih jauh tentang FPB dan KPK, mari kita pastikan kita memahami apa artinya:

• FPB (Faktor Persekutuan Terbesar): Bilangan bulat positif terbesar yang dapat membagi habis dua bilangan bulat atau lebih.
• KPK (Kelipatan Persekutuan Terkecil): Bilangan bulat positif terkecil yang merupakan kelipatan persekutuan dari dua bilangan bulat atau lebih.

Sebagai contoh, tentukanlah FPB dan KPK dari 12 dan 40.

Kita mengetahui bahwa faktor dari 12 adalah 1, 2, 3, 4, 6, 12 dan faktor dari 40 adalah 1, 2, 4, 5, 8, 10, 20, 40.

Faktor yang sama dari kedua bilangan itu (yang disebut Faktor Persekutuan) adalah 1, 2, dan 4. Faktor persekutuan yang terbesar adalah 4, yang disebut sebagai FPB.

Lalu kita mengetahui pula bahwa kelipatan dari 12 adalah 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, ... 240, ... 360, dst. dan kelipatan dari 40 adalah 40, 80, 120, ... 240, ... 360, dst.

Kelipatan yang sama dari kedua bilangan itu (yang disebut Kelipatan Persekutuan) adalah 120, 240, 360, dst.. Yang terkecil dari Kelipatan Persekutuan ini (yang disebut KPK) adalah 120.

Prinsip Dasar Algoritma Euclid

Algoritma Euclid adalah salah satu algoritma yang tertua yang masih digunakan sampai saat ini. Algoritma ini dijabarkan oleh Euclid dalam bukunya Elements yang ditulis sekitar 300 SM.¹

Algoritma ini didasari oleh prinsip dasar yang cerdik, yaitu FPB dari dua buah bilangan, yang misalkan saja kita sebut bilangan a dan b (di mana b > a) adalah sama dengan FPB untuk bilangan a dan c jika c = b - a.

Mari kita ambil contoh di atas untuk menjelaskan hal ini. Kita sudah melihat bahwa FPB dari 12 dan 40 adalah 4. Jika kita menghitung FPB dari 12 dan 28 (yaitu 40 - 12) maka hasilnya adalah 4 pula.

Lalu jika kita menghitung FPB antara 12 dan 16 (yaitu 28 - 12) maka hasilnya juga tetap 4.

Kemudian FPB antara 12 dan 4 (yaitu 16 - 12) tentunya tetap adalah 4.

Lalu kita juga bisa membuat perhitungan ini menjadi lebih efisien. Misalkan kita sedang mencari FPB antara 12 dan 136. Maka dari angka 136 tersebut kita bisa mengurangi 12 secara berulang-ulang hingga hasilnya lebih kecil dari 12: 136, 124, 112, ..., 40, 28, 16, 4. Namun kita juga bisa mengambil jalan pintas dengan membagi 136 dengan 12 dan mengambil sisa pembagiannya, yaitu 4.

Dengan memanfaatkan prinsip-prinsip tersebut, kita dapat menemukan FPB dari dua bilangan a dan b (di mana b > a) dengan melakukan langkah-langkah ini secara berulang-ulang:

• Hitung sisa pembagian b dibagi dengan a. Misalkan sisanya adalah r.
• Jika r = 0, maka a adalah FPB dari a dan b.
• Jika r ≠ 0, maka ganti b dengan a dan ganti a dengan r, lalu ulangi lagi prosesnya.

Berikut adalah contoh melakukan iterasi (pengulangan) ini dengan menggunakan angka 12 dan 40.

Iterasi 1:

b = 40
a = 12
r = sisa pembagian 40 / 12 = 4

Iterasi 2:

b = 12
a = 4
r = sisa pembagian 12 / 4 = 0

Maka 4 (yaitu nilai a dalam iterasi terakhir) adalah FPB dari 12 dan 40.

Metode perhitungan FPB dengan menggunakan iterasi inilah yang disebut sebagai Algoritma Euclid.

Menghitung KPK

Setelah kita mendapatkan FPB, maka KPK dapat dihitung secara mudah dengan menggunakan rumus berikut ini:

KPK(a, b) = (a * b) / FPB(a, b)

Dengan menggunakan contoh sebelumnya:

KPK(12, 40) = (12 * 40) / 4 = 480 / 4 = 120

Implementasi Algoritma Euclid

Algoritma Euclid dapat diimplementasikan dalam bahasa C++ sebagai berikut:

    int FPB(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    int KPK(int a, int b) {
        return (a * b / FPB(a, b));
    }

di mana % adalah operator modulo atau sisa pembagian.

Selain dari cara di atas, sesuai dengan iterasi yang sudah dijelaskan, algoritma ini juga dapat ditulis secara elegan dalam bentuk rekursi sebagai berikut:

    int FPBRekursi(int a, int b) {
      if (b == 0) {
        return a;
      }
      return FPBRekursi(b, a % b);
    }

Aplikasi Algoritma Euclid

Algoritma Euclid terlihat sederhana, dan implementasinya hanya memerlukan beberapa baris kode program. Walaupun demikian, ternyata algoritma ini memiliki aplikasi yang sangat luas, terutama dalam bidang kriptografi.

Contohnya, dalam sistem RSA, yang merupakan salah satu kriptosistem (sistem persandian) asimetris yang paling populer. Kriptosistem RSA ini sudah lazim digunakan dalam pengamanan komunikasi melalui Internet, pengamanan transaksi online banking, dan sebagainya. Kriptosistem RSA memanfaatkan dua bilangan prima sebagai kunci publik dan privat, dan algoritma Euclid digunakan untuk memastikan bahwa kedua bilangan tersebut tidak memiliki faktor persekutuan selain 1.

Algoritma Euclid dipilih di dalam dunia kriptografi di antaranya karena memiliki kedua karakteristik berikut ini:

• Efisiensi: Algoritma Euclid sangat efisien dalam menghitung FPB, bahkan untuk bilangan yang sangat besar. Efisiensi ini sangat penting dalam kriptografi, di mana perhitungan harus dilakukan dengan cepat.
• Keandalan: Algoritma Euclid memberikan hasil yang akurat dan terjamin. Hal ini penting untuk menjaga keamanan sistem kriptografi.

Kesimpulan

Algoritma Euclid adalah alat yang sangat berguna untuk mencari FPB dan KPK dari dua bilangan bulat positif. Algoritma ini efisien dan mudah diimplementasikan. Pemahaman yang baik tentang algoritma Euclid akan sangat bermanfaat dalam mempelajari Matematika lebih lanjut, terutama dalam bidang teori bilangan dan aplikasinya. Selain itu, sering pula terdapat soal dalam olimpiade informatika yang perlu dijawab dengan memanfaatkan algoritma ini.