Skip to main content

🔍 Pembagi Bersama Terbesar

Dua bilangan bulat dapat memiliki beberapa faktor pembagi yang sama. Di antara semua faktor pembagi bersama itu, yang paling penting adalah pembagi bersama terbesar (Greatest Common Divisor atau disingkat PBB).

Sebagai contoh:

  • Faktor dari 45 adalah: 1, 3, 5, 9, 15, dan 45
  • Faktor dari 36 adalah: 1, 2, 3, 4, 6, 9, 12, 18, dan 36
  • Faktor pembagi bersama: 1, 3, dan 9
  • Maka: PBB(45, 36) = 9

📘 Definisi​

Misalkan a dan b adalah dua bilangan bulat tidak nol. Maka pembagi bersama terbesar dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga:

  • d membagi a (d | a), dan
  • d membagi b (d | b)

Notasi:

PBB(a, b) = d

🧠 Sifat-Sifat Pembagi Bersama Terbesar​

Beberapa sifat penting dari PBB yang akan sering digunakan dalam pembuktian dan perhitungan:

📌 Teorema​

Misalkan a, b, dan c adalah bilangan bulat. Maka:

  1. Jika c adalah PBB dari a dan b, maka
    c | (a + b)
  2. Jika c adalah PBB dari a dan b, maka
    c | (a − b)
  3. Jika c | a, maka
    c | (a × b)

Pemahaman terhadap konsep PBB ini sangat penting, terutama sebagai fondasi dalam algoritma Euclidean, faktorisasi prima, serta aplikasi dalam kriptografi dan pemrograman kompetitif. 🚀