Matematika Diskrit : Teorema Euclidean

📋 Daftar Isi

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 r₀ = m dan r₁ = n.

Lakukan secara berturut-turut pembagian untuk memperoleh

r₀ = r₁q₁ + r₂, 0 ≤ r₂ < r₁,

r₁ = r₂q₂ + r₃, 0 ≤ r₃ < r₂,

…

r_{n– 2} = r_n–1 q_n–1 + r_n, 0 ≤ r_n < r_n–1,

r_n–1 = r_nq_n + 0

Menurut Teorema 2,

PBB(m, n) = PBB(r₀, r₁) = PBB(r₁, r₂) = … =

PBB(r_{n– 2,} r_{n– 1}) = PBB(r_{n– 1}, r_n) = PBB(r_n, 0) = r_n

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

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