Matematika Diskrit : Teorema Euclidean

Teorema Euclidean

Misalkan m dan n bilangan bulat, n > 0. Jika m dibagi dengan n maka hasil pembagiannya adalah q (quotient) dan sisanya r (remainder), sedemikian sehingga m = nq + r dengan 0 โ‰ค r < n

Contoh :

1. 1987/97 = 20, sisa 47

1987 = 20 ยท 97 + 47

2. โ€“22/3 = โ€“8, sisa 2

โ€“22 = (โ€“8) ยท 3 + 2

Tetapi jika pembagiannya sebagai berikut:

โ€“22/3 = โ€“7 sisa โ€“1

โ€“22 = (โ€“7) ยท 3 โ€“ 1 โ†’ (salah) karena r = โ€“1 (syarat 0 โ‰ค r < n)


Pembagi Bersama Terbesar (PBB)

Teorema 1.

Misalkan a dan b bilangan bulat tidak nol. Pembagi bersama terbesar (PBB โ€“ greatest common divisor atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian hingga d | a dan d | b.

Dalam hal ini kita nyatakan bahwa PBB(a, b) = d.

Contoh :

PBB(45, 36) = ?

Faktor pembagi 45: 1, 3, 5, 9, 15, 45;

Faktor pembagi 36: 1, 2, 3, 4, 9, 12, 18, 36;

Faktor pembagi bersama 45 dan 36: 1, 3, 9 โ†’ terbesar = 9

PBB(45, 36) = 9


Teorema 2.

Misalkan m dan n bilangan bulat, dengan syarat n > 0

sedemikian sehingga m = nq + r , 0 โ‰ค r < n โ†’ maka PBB(m, n) = PBB(n, r)

Contoh :

m = 60, n = 18

60 = 3 ยท 18 + 6

maka PBB(60, 18) = PBB(18, 6) = 6


Algoritma Euclidean

Tujuan: algoritma untuk mencari PBB dari dua buah bilangan bulat.

Penemu: Euclides, seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam buku, Element.

Misalkan m dan n adalah bilangan bulat tak negatif dengan m โ‰ฅ n. Misalkan r0 = m dan r1 = n.

Lakukan secara berturut-turut pembagian untuk memperoleh

r0 = r1q1 + r2, 0 โ‰ค r2 < r1,

r1 = r2q2 + r3, 0 โ‰ค r3 < r2,

rnโ€“ 2 = rnโ€“1 qnโ€“1 + rn, 0 โ‰ค rn < rnโ€“1,

rnโ€“1 = rnqn + 0

Menurut Teorema 2,

PBB(m, n) = PBB(r0, r1) = PBB(r1, r2) = โ€ฆ =

PBB(rnโ€“ 2, rnโ€“ 1) = PBB(rnโ€“ 1, rn) = PBB(rn, 0) = rn

Jadi, PBB dari m dan n adalah sisa terakhir yang tidak nol dari runtunan pembagian tersebut.


Diberikan dua buah bilangan bulat tak-negatif m dan n (m โ‰ฅ n). Algoritma Euclidean berikut mencari pembagi bersama terbesar dari m dan n.

Algoritma Euclidean

  1. Jika n = 0 maka m adalah PBB(m, n);
    stop.
    tetapi jika n โ‰  0, lanjutkan ke langkah 2.
  2. Bagilah m dengan n dan misalkan r adalah sisanya.
  3. Ganti nilai m dengan nilai n dan nilai n dengan nilai r, lalu ulang kembali ke langkah 1.

Contoh :

m = 80, n = 12 dan dipenuhi syarat m โ‰ฅ n

Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB(80, 12) = 4


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Teori Bilangan, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up