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$ masih lebih besar dari nol. Algoritma baru akan berhenti ketika $r$ bernilai nol.

Jika $r$ sudah nol, maka nilai GCD dapat ditentukan dengan menggunakan rumus:

$\gcd (b, 0) = |b|$

Rumus ini sudah dibuktikan di sifat GCD ini.

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

Agar lebih jelas, perhatikan contoh-contoh di bawah.

Contoh

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 $\gcd (4, 2) = \gcd (2, 0)$

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

Dengan demikian, GCD dari $4$ dan $6$ adalah $2$ .

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 $\gcd (42, 21) = \gcd (21, 0)$

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

Dengan demikian, GCD dari $252$ dan $105$ adalah $21$ .

Contoh 3

Carilah GCD dari $110$ dan $490$ dengan menggunakan Algoritma Euclid.

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

$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 $\gcd (50, 10) = \gcd (10, 0)$

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

Dengan demikian, GCD dari $110$ dan $490$ adalah $10$ .

Contoh 4

Carilah GCD dari $−35$ dan $120$ dengan menggunakan Algoritma Euclid.

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

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

$85 = 35 \cdot 2 + 15$
Sisa bagi (remainder) $r = 15$
Karena $15 > 0$ maka algoritma dilanjutkan dan $\gcd (85, 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 $\gcd (15, 5) = \gcd (5, 0)$

Dari rentetan algoritma ini diperoleh:
$\gcd (−35, 120)$
$= \gcd (120, 85)$
$= \gcd (85, 35)$
$= \gcd (35, 15)$
$= \gcd (15, 5)$
$= \gcd (5, 0)$
$= 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 (−4) + 5$
Sisa bagi (remainder) $r = 5$
Karena $5 > 0$ maka algoritma dilanjutkan dan $\gcd (−39, 11) = \gcd (11, 5)$

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

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

Dari rentetan algoritma ini diperoleh:
$\gcd (50, −39)$
$= \gcd (−39, 11)$
$= \gcd (11, 5)$
$= \gcd (5, 1)$
$= \gcd (1, 0)$
$= 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.

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

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

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

$12 = 1 \cdot 12 + 0$
Sisa bagi (remainder) $r = 0$
Karena $r = 0$ maka algoritma berhenti dan $\gcd (12, 1) = \gcd (1, 0)$

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

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

Contoh 7

Carilah GCD dari $123456$ dan $60$ dengan menggunakan Algoritma Euclid.

$123456 = 60 \cdot 2057 + 36$
Sisa bagi (remainder) $r = 36$
Karena $36 > 0$ maka algoritma dilanjutkan dan $\gcd (123456, 60) = \gcd (60, 36)$

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

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

$24 = 12 \cdot 2 + 0$
Sisa bagi (remainder) $r = 0$
Karena $r = 0$ maka algoritma berhenti dan $\gcd (24, 12) = \gcd (12, 0)$

Dari rentetan algoritma ini diperoleh:
$\gcd (123456, 60)$
$= \gcd (60, 36)$
$= \gcd (36, 24)$
$= \gcd (24, 12)$
$= \gcd (12, 0)$
$= 12$

Dengan demikian, GCD dari $123456$ dan $60$ adalah $12$ .

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$

Tambahan

Apakah algoritma ini pasti berhenti?

Pasti. Perhatikan bahwa di dalam setiap operasi, nilai $r$ semakin lama semakin mengecil. Nilai yang semakin mengecil ini terjadi karena batasan $0 \leq r < |b|$

Misalkan $r_{1}$ adalah nilai $r$ pada operasi pertama.

Pada operasi kedua, $r_{1}$ akan bertindak sebagai pembagi. Akibatnya, $0 \leq r_{2} < r_{1}$

Pada operasi ketiga, $r_{2}$ akan bertindak sebagai pembagi. Akibatnya, $0 \leq r_{3} < r_{2} < r_{1}$

Dan seterusnya.. sampai $r_{k} = 0$ dan algoritma berhenti.