Materi, Soal, dan Pembahasan – Algoritma Euclid

           Setiap bilangan bulat positif memiliki faktor (pembagi). Misalnya, $8$ memiliki faktor $1, 2, 4$, dan dirinya sendiri, yaitu $8$. Keempat bilangan ini disebut faktor dari $8$ karena membagi habis $8$ tanpa sisa. Setelah itu, kita telah dikenalkan dengan Faktor Persekutuan Terbesar (FPB), atau dalam bahasa Inggris, Greatest Common Divisor (GCD), yaitu bilangan terbesar yang menjadi faktor bersama dari dua atau lebih bilangan yang lain. Sebagai contoh, FPB $12$ dan $16$, ditulis $\text{FPB}(12, 16)$ adalah $4$. Kita tentu sudah diajarkan cara mencari FPB saat masih berada di sekolah dasar. Ada yang menggunakan pohon faktor, ada juga yang menggunakan cara pagar (tabel), dan lain-lain.

Metode Pagar
Metode Pagar

 

Metode Pohon Faktor
Metode Pohon Faktor

      Sayangnya, cara-cara ini akan kurang efisien bila kita mencari FPB yang melibatkan bilangan-bilangan besar, mengingat sekolah dasar masih menitikberatkan pada pengenalan dan manipulasi bilangan yang nilainya kecil.

      Ada satu teorema dalam ranah teori bilangan yang cukup efisien digunakan untuk mencari FPB bilangan-bilangan besar. Namanya Algoritma Euclid. Pencetusnya jelas, Euclid, matematikawan legendaris berkebangsaan Yunani. Ia menuliskan teorema ini di buku maha karyanya, Elements. Algoritma (atau algoritme) diartikan sebagai langkah/prosedur sistematis untuk menyelesaikan suatu permasalahan.

Euclid
Euclid

Quote by Jean Piaget

Tujuan utama pendidikan di sekolah haruslah menciptakan anak yang mampu melahirkan hal-hal positif yang baru, tidak sekadar mengulangi apa yang telah dilakukan oleh generasi sebelumnya.

      Algoritma Euclid mungkin tidak ditemui pada pembelajaran di kelas sekolah menengah, namun sering dimunculkan sebagai solusi untuk menyelesaikan soal-soal olimpiade matematika. Selain itu, mahasiswa yang berkecimpung dalam program studi matematika juga akan menemuinya saat mata kuliah Teori Bilangan (atau mungkin mata kuliah lainnya).

Teorema: Algoritma Euclid

Diberikan dua bilangan bulat positif $a$ dan $b$ dengan $a>b$. $\text{FPB}(a,b)$ dapat ditentukan dengan melakukan iterasi (looping) algoritma pembagian seperti berikut.
$$\begin{aligned} a & = q_1b+r_1, && 0 < r_1 < b \\ b & = q_2r_1+r_2, && 0 < r_2 < r_1 \\ r_1 & = q_3r_2+r_3, && 0 < r_3 < r_2 \\ & \hspace{0.8em} \vdots &&  \hspace{0.8em} \vdots \\ r_{n-3} & = q_{n-1}r_{n-2} + r_{n-1}, && 0 < r_{n-1} < r_{n-2} \\ r_{n-2} & = q_{n}r_{n-1} + r_{n}, && 0 < r_{n} < r_{n-1} \\ r_{n-1} & = q_{n+1}r_{n} + r_{n+1}, && r_{n+1} = 0 \end{aligned}$$Proses dilakukan sampai sisa hasil baginya $0$ dan algoritma dihentikan. Nilai $r_n$, yaitu sisa terakhir dari pembagian di atas yang bukan nol merupakan $\text{FPB}(a, b)$.


Sebelum membuktikan Algoritma Euclid, perlu kita buktikan lema berikut terlebih dahulu.

Lema: Jika $a, b, q, r \in \mathbb{Z}$ dengan $a = bq + r$, maka $\text{FPB}(a, b) = \text{FPB}(b, r)$.

Bukti

Misalkan $\text{FPB}(a,b) = M$. Akan dibuktikan bahwa $\text{FPB}(c, d) = M$.
Karena $\text{FPB}(a, b) = M$, maka $M$ membagi habis $a$ dan $b$. Diketahui $a = bq + r$, ekuivalen dengan $r = a-bq$. Dua suku itu memuat faktor yang habis dibagi $M$, sehingga $M$ juga habis membagi $r$.
Selanjutnya, misalkan ada bilangan bulat $N$ sehingga $N$ membagi habis $b$ dan $r$.
Di sini, $N$ belum tentu merupakan $\text{FPB}(b, r)$ (Sebagai ilustrasi, $2$ habis membagi $8$ dan $12$, tetapi $2$ bukan $\text{FPB}(8, 12))$.
Selanjutnya dapat ditulis $b = kN$ dan $r = \ell N$ untuk suatu $k, \ell \in \mathbb{Z}$. Kita peroleh,
$\begin{aligned} a & = bq+r \\ & = (kN)q + \ell N \\ & = N(kq + \ell) \end{aligned}$
sehingga $N$ membagi habis $a$.
Karena $\text{FPB}(a, b) = M$, $N$ membagi habis $a$ dan $b$, maka disimpulkan bahwa $N$ juga membagi habis $M$. Dengan kata lain, $M$ menjadi faktor sekutu terbesar dengan $M \geq N$. Jadi, terbukti bahwa $\text{FPB}(b, r) = M$.

[collapse]

Bukti Algoritma Euclid
Algoritma berhenti ketika diperoleh suatu $r_{n+1}=0$. Hal ini dikarenakan sisa suatu pembagian terkecil yang mungkin adalah $0$, serta fakta bahwa
$$r_1 > r_2 > \cdots > r_{n-1} > r_n > r_{n+1} = 0$$Menggunakan lema yang telah dibuktikan di atas bahwa
$$\text{FPB}(a, b) = \text{FPB}(r_0, r_1) = \text{FPB}(r_1, r_2) = \cdots = \text{FPB}(r_{n-1}, r_n) = \text{FPB}(r_n, 0) = r_n$$maka Algoritma Euclid telah terbukti kebenarannya. $\blacksquare$

      Pada awalnya, pendekatan geometris dipakai Euclid untuk mencari FPB dua buah bilangan seperti tampak pada gambar berikut.

Algoritme Euclid Secara Geometris
Algoritma Euclid Secara Geometris

      Jarak satu titik ke titik lain mewakili bilangan yang dimaksud. Misalkan akan dicari FPB dari panjang $AB$ dan $CD$. Karena $DC$ lebih pendek dari $AB$, maka $CD$ dipakai untuk mengukur $AB$, tetapi cukup sekali saja karena sisanya, $EA$ lebih pendek dari $DC$. Selanjutnya, $AE$ dipakai untuk mengukur $DC$, ternyata butuh dua kali (ditandai dengan warna merah), dengan sisa $FC$. Terakhir, $FC$ dipakai untuk mengukur $EA$ dan tepat $4$ kali pengukuran tanpa menghasilkan sisa panjang (ditandai dengan warna biru). Dengan kata lain, $EA = 4FC$. Disimpulkan bahwa $FC$ merupakan FPB yang kita cari.

Baca: Materi, Soal, dan Pembahasan – Teorema Sisa Cina

        FPB dari tiga bilangan atau lebih dapat dicari dengan mengalikan faktor-faktor prima bersama dengan pangkat terkecil dari bilangan-bilangan itu. Misalnya, karena
$\begin{aligned} 18 & = \color{blue}{2} \times 3^2 \\ 24 & = 2^3 \times \color{blue}{3} \\ 36 & = 2^2 \times 3^2 \end{aligned}$
maka $\text{FPB}(18, 24, 36) = 2 \times 3 = 6$.
Selain itu, FPB dari tiga atau lebih bilangan bisa dicari dengan mencari FPB masing-masing pasangan dua bilangan yang ada, yaitu
$\begin{aligned} \text{FPB}(18, 24, 36) & = \text{FPB}(18, \text{FPB}(24, 36)) \\ & = \text{FPB}(\text{FPB}(18, 24), 36) \\ & = \text{FPB}(\text{FPB}(18, 36), 24) \end{aligned}$
Ini menunjukkan bahwa Algoritma Euclid tetap dapat dipakai untuk mencari FPB dari tiga atau lebih bilangan dengan cara melakukan pengelompokkan dua bilangan seperti contoh di atas.

      Bagaimana dengan Kelipatan Persekutuan Terkecil (KPK)? Apakah Algoritma Euclid dapat dipakai untuk mencari KPK? Nah, jika FPB dari dua bilangan telah ditemukan, maka kita dapat mencari KPK dengan menggunakan FPB. Misalnya diberikan dua bilangan bulat $a$ dan $b$ dengan $\text{FPB}(a, b) = p$. KPK dari $a$ dan $b$ sama dengan hasil kali $a$ dan $b$ dibagi dengan nilai FPB-nya, ditulis $\text{KPK}(a, b) = \dfrac{a \times b}{\text{FPB}(a, b)}$.

Contoh 1:
Kita akan mencari FPB dari $12$ dan $16$ menggunakan Algoritma Euclid.
$$\begin{aligned} 16 & = 1 \cdot \color{blue}{12} + \color{red}{4} && (\text{Iter}\text{asi}~1) \\ \color{blue}{12} & = 3 \cdot \color{red}{4} + 0 && (\text{Iter}\text{asi}~2) \end{aligned}$$Karena pada iterasi 2 sisa hasil baginya $0$, maka FPB dari $12$ dan $16$ adalah $\boxed{\color{red}{4}}$, yang merupakan sisa hasil bagi pada iterasi 1.
Dari contoh di atas, Algoritma Euclid hanya melibatkan beberapa kali iterasi saja untuk menemukan FPB. Ini dikarenakan nilai bilangan yang terlibat masih tergolong kecil.

Contoh 2:
Kita akan mencari FPB dari $18$ dan $63$ menggunakan Algoritma Euclid.
$$\begin{aligned} 63 & = 3 \cdot \color{blue}{18} + \color{red}{9} && (\text{Iter}\text{asi}~1) \\ \color{blue}{18} & = 2 \cdot \color{red}{9} + 0 && (\text{Iter}\text{asi}~2) \end{aligned}$$Karena pada iterasi 2 sisa hasil baginya $0$, maka FPB dari $18$ dan $63$ adalah $\boxed{\color{red}{9}}$, yang merupakan sisa hasil bagi pada iterasi 1.
Masih dua iterasi saja, ya, untuk contoh di atas.

Contoh 3:
Kita akan mencari FPB dari $52$ dan $124$ menggunakan Algoritma Euclid.
$$\begin{aligned} 124 & = 2 \cdot 52 + 20 && (\text{Iter}\text{asi}~1) \\ 52 & = 2 \cdot 20 + 12 && (\text{Iter}\text{asi}~2) \\ 20 & = 1 \cdot 12 + 8 && (\text{Iter}\text{asi}~3) \\ 12 & = 1 \cdot 8 + \color{red}{4} && (\text{Iter}\text{asi}~4) \\ 8 & = 2 \cdot 4 + 0 && (\text{Iter}\text{asi}~5) \end{aligned}$$Karena pada iterasi 5, sisa hasil baginya $0$, maka FPB dari $52$ dan $124$ adalah $\boxed{\color{red}{4}}$, yang merupakan sisa hasil bagi pada iterasi 4.
Waduh, sudah 5 iterasi ya, padahal bilangannya baru ratusan.

Contoh 4:
Kita akan mencari FPB dari $321$ dan $843$ menggunakan Algoritma Euclid.
$$\begin{aligned} 843 & = 2 \cdot 321 + 201 && (\text{Iter}\text{asi}~1) \\ 321 & = 1 \cdot 201 + 120 && (\text{Iter}\text{asi}~2) \\ 201 & = 1 \cdot 120 + 81 && (\text{Iter}\text{asi}~3) \\ 120 & = 1 \cdot 81+ 39 && (\text{Iter}\text{asi}~4) \\ 81 & = 2 \cdot 39 + \color{red}{3} && (\text{Iter}\text{asi}~5) \\ 39 & = 13 \cdot 3 + 0 && (\text{Iter}\text{asi}~6) \end{aligned}$$Karena pada iterasi 6, sisa hasil baginya $0$, maka FPB dari $321$ dan $843$ adalah $\boxed{\color{red}{3}}$, yang merupakan sisa hasil bagi pada iterasi 5.

Contoh 5:
Kita akan mencari FPB dari $3.579$ dan $4.567$ menggunakan Algoritma Euclid.
$$\begin{aligned} 4.567 & = 1 \cdot 3.579 + 988 && (\text{Iter}\text{asi}~1) \\ 3.579 & = 3 \cdot 988 + 615 && (\text{Iter}\text{asi}~2) \\ 988 & = 1 \cdot 615 + 373 && (\text{Iter}\text{asi}~3) \\ 615 & = 1 \cdot 373 + 242 && (\text{Iter}\text{asi}~4) \\ 373 & = 1 \cdot 242 + 131 && (\text{Iter}\text{asi}~5) \\ 242 & = 1 \cdot 131 + 111 && (\text{Iter}\text{asi}~6) \\ 131 & = 1 \cdot 111 + 20 && (\text{Iter}\text{asi}~7) \\ 111 & = 5 \times 20 + 11 && (\text{Iter}\text{asi}~8) \\ 20 & = 1 \cdot 11 + 9 && (\text{Iter}\text{asi}~9) \\ 11 & = 1 \cdot 9 + 2 && (\text{Iter}\text{asi}~10) \\ 9 & = 4 \cdot 2 + \color{red}{1} && (\text{Iter}\text{asi}~11) \\ 2 & = 2 \cdot 1 + 0 && (\text{Iter}\text{asi}~12) \end{aligned}$$Karena pada iterasi 12, sisa hasil baginya $0$, maka FPB dari $3.579$ dan $4.567$ adalah $\boxed{\color{red}{1}}$, yang merupakan sisa hasil bagi pada iterasi 11. Kita sebut $3.579$ dan $4.567$ relatif prima karena memiliki FPB $1$.

Contoh 6:
Kita akan mencari FPB dari $897$, $1.157$, dan $1.677$ menggunakan Algoritma Euclid.
Mengingat bahwa algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, maka kita harus memilih 2 dari 3 bilangan tersebut untuk dicari FPB-nya terlebih dahulu.
Misalkan di sini kita memilih bilangan $1.157$ dan $1.677$. Akan dicari $\text{FPB}(1.157, 1.677)$ menggunakan Algoritma Euclid.
$$\begin{aligned} 1.677 & = 1 \cdot 1.157 + 520 && (\text{Iter}\text{asi}~1) \\ 1.157 & = 2 \cdot 520 + 117 && (\text{Iter}\text{asi}~2) \\ 520 & = 4 \cdot 117 + 52 && (\text{Iter}\text{asi}~3) \\ 117 & = 2 \cdot 52 + 13 && (\text{Iter}\text{asi}~4) \\ 52 & = 4 \cdot 13 + 0 && (\text{Iter}\text{asi}~5) \end{aligned}$$Karena pada iterasi 5, sisa hasil baginya $0$, maka FPB dari $1.157$ dan $1.677$ adalah $\boxed{\color{red}{13}}$, yang merupakan sisa hasil bagi pada iterasi 4.
Langkah selanjutnya adalah mencari
$\text{FPB}(897, \text{FPB}(1.157, 1.677))$ $= \text{FPB}(897, 13),$ yaitu

$$\begin{aligned} 897 & = 69 \cdot 13 + 0 && (\text{Iter}\text{asi}~1) \end{aligned}$$Karena sisa hasil baginya $0$ pada iterasi pertama, maka $\text{FPB}(897, 13) = 13$.
Jadi, kita simpulkan bahwa FPB dari $897$, $1.157$, dan $1.677$ adalah $\boxed{13}$

Contoh 7:
Kita akan mencari FPB dari $1.058$, $1.564$, dan $2.323$ menggunakan Algoritma Euclid.
Mengingat bahwa algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, maka kita harus memilih 2 dari 3 bilangan tersebut untuk dicari FPB-nya terlebih dahulu.
Misalkan di sini kita memilih bilangan $1.564$ dan $2.323$. Akan dicari $\text{FPB}(1.564, 2.323)$ menggunakan Algoritma Euclid.
$$\begin{aligned} 2.323 & = 1 \cdot 1.564 + 759 && (\text{Iter}\text{asi}~1) \\ 1.564 & = 2 \cdot 759 + 46 && (\text{Iter}\text{asi}~2) \\ 759 & = 16 \cdot 46 + \color{red}{23} && (\text{Iter}\text{asi}~3) \\ 46 & = 2 \cdot 23 + 0&& (\text{Iter}\text{asi}~4) \end{aligned}$$Karena pada iterasi 4, sisa hasil baginya $0$, maka FPB dari $1.564$ dan $2.323$ adalah $\boxed{\color{red}{23}}$, yang merupakan sisa hasil bagi pada iterasi 3.
Langkah selanjutnya adalah mencari
$\text{FPB}(1.058, \text{FPB}(1.564, 2.323))$ $= \text{FPB}(1.058, 23),$ yaitu

$$\begin{aligned} 1.058 & = 46 \cdot 23 + 0 && (\text{Iter}\text{asi}~1) \end{aligned}$$Karena sisa hasil baginya $0$ pada iterasi pertama, maka $\text{FPB}(1.058, 23) = 23$.
Jadi, kita simpulkan bahwa FPB dari $1.058$, $1.564$, dan $2.323$ adalah $\boxed{23}$

Contoh 8:
Kita akan mencari FPB dari $1.015$, $2.001$, $2.871$, dan $3.915$ menggunakan Algoritma Euclid.
Mengingat bahwa algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, maka kita harus membentuk pasangan dua bilangan untuk dicari FPB-nya terlebih dahulu.
Pertama, misalkan kita memilih bilangan $1.015$ dan $2.001$. Akan dicari $\text{FPB}(1.015, 2.001)$ menggunakan Algoritma Euclid.
$$\begin{aligned} 2.001 & = 1 \cdot 1.015 + 986 && (\text{Iter}\text{asi}~1) \\ 1.015 & = 1 \cdot 986 + \color{red}{29} && (\text{Iter}\text{asi}~2) \\ 986 & = 34 \cdot 29 + 0 && (\text{Iter}\text{asi}~3) \end{aligned}$$Karena pada iterasi 3, sisa hasil baginya $0$, maka FPB dari $1.015$ dan $2.001$ adalah $\boxed{\color{red}{29}}$, yang merupakan sisa hasil bagi pada iterasi 2.
Setelah itu, cari $\text{FPB}(29, 2.871, 3.915)$. Bisa diperiksa bahwa $2.871$ dan $3.915$ habis dibagi $29$. Oleh karena itu, dapat kita simpulkan bahwa $\text{FPB}(29, 2.871, 3.915) = 29$, mengimplikasikan bahwa $\boxed{\text{FPB}(1.015, 2.001, 2.871, 3.915) = 29}$

Baca: Materi, Soal, dan Pembahasan – Kongruensi Modulo

      Di sini kita seharusnya menyadari bahwa bagian yang “sulit” dalam Algoritma Euclid adalah membuat kombinasi dua bilangan untuk dikalikan, lalu dijumlahkan dengan bilangan lain. Contohnya, $124$ sama dengan $52$ dikali berapa, lalu ditambah berapa. Ya, jawabannya $52$ dikali $2$, hasilnya $104$, lalu ditambah $20$, supaya hasilnya jadi $124$. Cara tebak-tebak seperti ini sebenarnya sudah diterapkan saat kita menggunakan pembagian bersusun.

        Teorema ini selanjutnya dipakai sebagai dasar untuk mengenal Identitas Bezout dan menyelesaikan Persamaan Diophantine. Kedua materi tersebut akan dibahas di postingan terpisah.

Baca: Materi, Soal, dan Pembahasan – Persamaan Diophantine

Tinggalkan Balasan

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *