Hendra Jaya Napitupulu | Algoritma Euclid

Algoritma Euclid

Pada setiap bilangan bulat $a$ dan $b$ dimana $b \neq 0$ yang memenuhi $a = b q + r$ dan $0 \leq r < |b|$ , dimana bilangan bulat $q$ adalah hasil bagi (quotient) dan bilangan bulat $r$ adalah sisa bagi (remainder), berlaku $gcd (a, b) = gcd (b, r)$

GCD adalah singkatan dari Greatest Common Divisor. Dalam bahasa Indonesia, GCD dikenal sebagai FPB: Faktor Persekutuan Terbesar.

Teorema di atas bisa dipakai secara beruntun untuk mencari GCD secara cepat. Pemakaian secara beruntun ini dikenal sebagai Algoritma Euclid. Algoritma Euclid akan terus berlangsung selama $r > 0$ dan baru akan berhenti ketika $r = 0$ yaitu ketika $a$ habis dibagi oleh $b$ yang artinya $gcd (a, b) = b$

Dalam pencarian GCD, hanya faktor positif yang diperhitungkan. Hal ini disebabkan karena faktor negatif selalu lebih kecil dari faktor positif. Sebagai contoh, $gcd (6, 4) = 2$ . Secara teknis, memang betul bahwa $−2$ adalah faktor dari $6$ dan $4$ . Tetapi karena $−2 < 2$ maka $−2$ tidak akan pernah menjadi GCD dari $6$ dan $4$ .

Lebih jauh lagi. Jika salah satu atau kedua bilangan yang diberikan adalah bilangan negatif, maka tanda negatif bisa diabaikan dan pencarian GCD hanya menggunakan bilangan positif atau nilai mutlak saja. Sebagai contoh, $gcd (−6, −9) = 3$ . Hal ini diperbolehkan karena $−3$ dan $3$ keduanya adalah faktor persekutuan dari $−6$ dan $−9$ . Dari kedua faktor ini persekutuan ini, tentu saja $3$ lebih besar dari $−3$ .

Secara formal, $gcd (a, b) = gcd (|a|, |b|)$

Kemudian, dalam notasi penulisan GCD, usahakan agar bilangan bulat yang lebih besar ditulis terlebih dahulu. Walaupun tidak ada aturan yang mengharuskan hal ini, tetapi penulisan ini lebih "hemat langkah" dalam Algoritma Euclid. Contoh 1 diberikan khusus untuk menjelaskan kenapa notasi penulisan ini hemat langkah.

Di dalam teori bilangan, ada satu GCD yang sangat khusus, yaitu GCD yang nilainya 1.
Jika $gcd (a, b) = 1$ maka dikatakan $a$ dan $b$ adalah bilangan yang relatif prima (relatively prime) atau koprima (coprime).

Relatif prima maksudnya adalah kedua bilangan bulat $a$ dan $b$ tidak mempunyai faktor persekutuan. Satu-satunya faktor persekutuan dari $a$ dan $b$ adalah 1. Contoh bilangan yang relatif prima adalah 50 dan 39.

Selanjutnya, sebelum mempelajari Algoritma Euclid, pembaca sangat disarankan untuk memahami Pembagian Euclid terlebih dahulu.

Agar lebih jelas, perhatikan contoh-contoh di bawah.

Contoh 1

Carilah GCD dari 4 dan 6 dengan menggunakan Algoritma Euclid.

$4 = 6 \cdot 0 + 4$
Sisa bagi (remainder) $r = 4$
Karena $4 > 0$ maka algoritma dilanjutkan dan $gcd (4, 6) = gcd (6, 4)$

$6 = 4 \cdot 1 + 2$
Sisa bagi (remainder) $r = 2$
Karena $2 > 0$ maka algoritma dilanjutkan dan $gcd (6, 4) = gcd (4, 2)$

$4 = 2 \cdot 2 + 0$
Sisa bagi (remainder) $r = 0$
Karena $r = 0$ maka algoritma berhenti dan karena 4 habis dibagi oleh 2 maka $gcd (4, 2) = 2$

Dari rentetan algoritma ini diperoleh:
$gcd (4, 6) = gcd (6, 4) = gcd (4, 2) = 2$

Dengan demikian, GCD dari 4 dan 6 adalah 2.

Dalam contoh ini, pencarian $gcd (4, 6)$ berubah menjadi pencarian $gcd (6, 4)$ . Walaupun tidak salah, tetapi operasi ini tidak hemat langkah. Agar lebih hemat langkah, usahakan untuk menulis bilangan yang lebih besar terlebih dahulu. Dalam contoh ini, lebih baik untuk langsung memulai pencarian dari $gcd (6, 4)$ .

Untuk contoh-contoh selanjutnya, semua akan menulis bilangan yang lebih besar terlebih dahulu.

Contoh 2

Carilah GCD dari 252 dan 105 dengan menggunakan Algoritma Euclid.

$252 = 105 \cdot 2 + 42$
Sisa bagi (remainder) $r = 42$
Karena $42 > 0$ maka algoritma dilanjutkan dan $gcd (252, 105) = gcd (105, 42)$

$105 = 42 \cdot 2 + 21$
Sisa bagi (remainder) $r = 21$
Karena $21 > 0$ maka algoritma dilanjutkan dan $gcd (105, 42) = gcd (42, 21)$

$42 = 21 \cdot 2 + 0$
Sisa bagi (remainder) $r = 0$
Karena $r = 0$ maka algoritma berhenti dan karena 42 habis dibagi oleh 21 maka $gcd (42, 21) = 21$

Dari rentetan algoritma ini diperoleh:
$gcd (252, 105) = gcd (105, 42) = gcd (42, 21) = 21$

Dengan demikian, GCD dari 252 dan 105 adalah 21.

Contoh 3

Carilah GCD dari 110 dan 490 dengan menggunakan Algoritma Euclid.

$490 = 110 \cdot 4 + 50$
Sisa bagi (remainder) $r = 50$
Karena $50 > 0$ maka algoritma dilanjutkan dan $gcd (490, 110) = gcd (110, 50)$

$110 = 50 \cdot 2 + 10$
Sisa bagi (remainder) $r = 10$
Karena $10 > 0$ maka algoritma dilanjutkan dan $gcd (110, 50) = gcd (50, 10)$

$50 = 10 \cdot 5 + 0$
Sisa bagi (remainder) $r = 0$
Karena $r = 0$ maka algoritma berhenti dan karena 10 membagi habis 50 maka $gcd (50, 10) = 10$

Dari rentetan algoritma ini diperoleh:
$gcd (490, 110) = gcd (110, 50) = gcd (50, 10) = 10$

Dengan demikian, GCD dari 110 dan 490 adalah 10.

Contoh 4

Carilah GCD dari -35 dan 120 dengan menggunakan Algoritma Euclid.

$120 = 35 \cdot 3 + 15$
Sisa bagi (remainder) $r = 15$
Karena $15 > 0$ maka algoritma dilanjutkan dan $gcd (120, 35) = gcd (35, 15)$

$35 = 15 \cdot 2 + 5$
Sisa bagi (remainder) $r = 5$
Karena $5 > 0$ maka algoritma dilanjutkan dan $gcd (35, 15) = gcd (15, 5)$

$15 = 5 \cdot 3 + 0$
Sisa bagi (remainder) $r = 0$
Karena $r = 0$ maka algoritma berhenti dan karena 15 habis dibagi oleh 5 maka $gcd (15, 5) = 5$

Dari rentetan algoritma ini diperoleh:
$gcd (120, 35) = gcd (35, 15) = gcd (15, 5) = 5$

Dengan demikian, GCD dari -35 dan 120 adalah 5.

Contoh 5

Carilah GCD dari 50 dan -39 dengan menggunakan Algoritma Euclid.

$50 = 39 \cdot 1 + 11$
Sisa bagi (remainder) $r = 11$
Karena $11 > 0$ maka algoritma dilanjutkan dan $gcd (50, 39) = gcd (39, 11)$

$39 = 11 \cdot 3 + 6$
Sisa bagi (remainder) $r = 6$
Karena $6 > 0$ maka algoritma dilanjutkan dan $gcd (39, 11) = gcd (11, 6)$

$11 = 6 \cdot 1 + 5$
Sisa bagi (remainder) $r = 5$
Karena $5 > 0$ maka algoritma dilanjutkan dan $gcd (11, 6) = gcd (6, 5)$

$6 = 5 \cdot 1 + 1$
Sisa bagi (remainder) $r = 1$
Karena $1 > 0$ maka algoritma dilanjutkan dan $gcd (6, 5) = gcd (5, 1)$

$5 = 1 \cdot 5 + 0$
Sisa bagi (remainder) $r = 0$
Karena $r = 0$ maka algoritma berhenti dan karena 5 habis dibagi oleh 1 maka $gcd (5, 1) = 1$

Dari rentetan algoritma ini diperoleh:
$gcd (50, 39) = gcd (39, 11) = gcd (11, 6) = gcd (6, 5) = gcd (5, 1) = 1$

Dengan demikian, GCD dari 50 dan -39 adalah 1. Berarti 50 dan -39 adalah dua bilangan yang relatif prima.

Contoh 6

Carilah GCD dari -14 dan -27 dengan menggunakan Algoritma Euclid.

$27 = 14 \cdot 1 + 13$
Sisa bagi (remainder) $r = 13$
Karena $13 > 0$ maka algoritma dilanjutkan dan $gcd (27, 14) = gcd (14, 13)$

$14 = 13 \cdot 1 + 1$
Sisa bagi (remainder) $r = 1$
Karena $1 > 0$ maka algoritma dilanjutkan dan $gcd (14, 13) = gcd (13, 1)$

$13 = 1 \cdot 13 + 0$
Sisa bagi (remainder) $r = 0$
Karena $r = 0$ maka algoritma berhenti dan karena 13 habis dibagi oleh 1 maka $gcd (13, 1) = 1$

Dari rentetan algoritma ini diperoleh:
$gcd (27, 14) = gcd (14, 13) = gcd (13, 1) = 1$

Dengan demikian, GCD dari -14 dan 27 adalah 1. Berarti -14 dan 27 adalah dua bilangan yang koprima.

Bukti

Rentetan Algoritma Euclid hanya mungkin dilakukan karena teorema di bawah ini:

Berikut disajikan pembuktian teorema di atas.

Misalkan D adalah himpunan semua faktor-faktor persekutuan dari $a$ dan $b$ .
$D = {d_{1}, d_{2}, d_{3}, \dots, d_{j}}$
Tentu saja faktor persekutuan terbesar (GCD) dari $a$ dan $b$ ada di dalam D.

Misalkan pula E adalah himpunan semua faktor-faktor persekutuan dari $b$ dan $r$ .
$E = {e_{1}, e_{2}, e_{3}, \dots, e_{k}}$
Tentu saja faktor persekutuan terbesar (GCD) dari $b$ dan $r$ ada di dalam E.

Kalau bisa dibuktikan bahwa semua anggota himpunan D ada di dalam E dan semua anggota himpunan E ada di dalam D, berarti D = E.
Kalau D = E, berarti anggota himpunan terbesar D sama dengan anggota himpunan terbesar E.
Kalau anggota himpunan terbesar D sama dengan anggota himpunan terbesar E, berarti faktor persekutuan terbesar $a$ dan $b$ sama dengan faktor persekutuan terbesar $b$ dan $r$ .

Berarti, untuk membuktikan $gcd (a, b) = gcd (b, r)$ cukup dengan membuktikan bahwa semua anggota himpunan D ada di dalam E dan semua anggota himpunan E ada di dalam D.

Bagian 1: semua anggota himpunan D ada di dalam E

Ambil salah satu anggota himpunan D. Katakanlah $d_{1}$

Karena $d_{1}$ adalah faktor dari $a$ dan $b$ , maka $a = d_{1} m$ dan $b = d_{1} n$

$a = b q + r$
$d_{1} m = d_{1} n \cdot q + r$
$r = d_{1} (m - n q)$

Terlihat jelas bahwa $d_{1}$ adalah salah satu faktor dari $r$ .
Karena $d_{1}$ adalah faktor dari $b$ dan $r$ , maka $d_{1}$ adalah salah satu faktor persekutuan dari $b$ dan $r$ .
Artinya $d_{1}$ pasti ada di dalam himpunan E.

Dengan cara yang sama, semua anggota himpunan D pasti juga anggota himpunan E.

Bagian 2: semua anggota himpunan E ada di dalam D

Ambil salah satu anggota himpunan E. Katakanlah $e_{1}$

Karena $e_{1}$ adalah faktor dari $b$ dan $r$ , maka $b = e_{1} m$ dan $r = e_{1} n$

$a = b q + r$
$a = e_{1} m \cdot q + e_{1} n$
$a = e_{1} (m q + n)$

Terlihat jelas bahwa $e_{1}$ adalah salah satu faktor dari $a$ .
Karena $e_{1}$ adalah faktor dari $a$ dan $b$ , maka $e_{1}$ adalah salah satu faktor persekutuan dari $a$ dan $b$ .
Artinya $e_{1}$ pasti ada di dalam himpunan D.

Dengan cara yang sama, semua anggota himpunan E pasti juga anggota himpunan D.

Kesimpulan

Dengan demikian, karena sudah ditunjukkan bahwa semua himpunan D pasti juga anggota himpunan E dan sebaliknya semua anggota himpunan E pasti juga anggota himpunan D, maka dapat disimpulkan D = E. Selanjutnya, karena D = E, maka anggota himpunan terbesar D pasti sama dengan anggota himpunan terbesar E. Karena anggota himpunan terbesar D sama dengan anggota himpunan terbesar E, maka faktor persekutuan terbesar dari $a$ dan $b$ sama dengan faktor persekutuan terbesar dari $b$ dan $r$