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.
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 Euclides. Pencetusnya jelas, Euclid, matematikawan legendaris berkebangsaan Yunani. Ia menuliskan teorema ini di buku maha karyanya, Elements. Algoritma diartikan sebagai langkah/prosedur sistematis untuk menyelesaikan suatu permasalahan.
Quote by Jean Piaget
Algoritma Euclides mungkin tidak ditemui pada pembelajaran di kelas sekolah menengah, tetapi 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 Euclides
$$\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 Euclides, 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).$
Misalkan $\text{FPB}(a,b) = M$. Akan dibuktikan bahwa $\text{FPB}(b, r) = M.$
- Karena $\text{FPB}(a, b) = M,$ haruslah $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$ serta $N$ membagi habis $a$ dan $b,$ 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.$
Bukti Algoritma Euclides
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.$$Dengan 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,$$disimpulkan bahwa algoritma Euclides terbukti. $\blacksquare$
Pada awalnya, pendekatan geometris dipakai Euclid untuk mencari FPB dua buah bilangan seperti tampak pada gambar berikut.
Jarak satu titik ke titik lain mewakili bilangan yang dimaksud. Misalkan akan dicari FPB dari panjang $AB$ dan $CD$. Karena $CD$ lebih pendek dari $AB$, $CD$ dipakai untuk mengukur $AB,$ tetapi cukup sekali saja karena sisanya, $EA$ lebih pendek dari $DC.$ Selanjutnya, $EA$ 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}$
haruslah $\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 Euclides 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 Euclides dapat dipakai untuk mencari KPK? Nah, jika FPB dari dua bilangan telah ditemukan, maka kita dapat mencari KPK dengan menggunakan FPB. Misalkan 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 Euclides.
$$\begin{aligned} 16 & = 1 \cdot \color{blue}{12} + \color{red}{4} && (\text{Iter}\text{asi ke-}1) \\ \color{blue}{12} & = 3 \cdot \color{red}{4} + 0 && (\text{Iter}\text{asi ke-}2) \end{aligned}$$Karena pada iterasi ke-$2$ sisa hasil baginya $0,$ FPB dari $12$ dan $16$ adalah $\boxed{\color{red}{4}},$ yang merupakan sisa hasil bagi pada iterasi ke-$1.$
Dari contoh di atas, algoritma Euclides hanya melibatkan beberapa kali iterasi untuk menemukan FPB. Ini dikarenakan nilai bilangan yang terlibat masih tergolong kecil.
Contoh 2:
Kita akan mencari FPB dari $18$ dan $63$ menggunakan algoritma Euclides.
$$\begin{aligned} 63 & = 3 \cdot \color{blue}{18} + \color{red}{9} && (\text{Iter}\text{asi ke-}1) \\ \color{blue}{18} & = 2 \cdot \color{red}{9} + 0 && (\text{Iter}\text{asi ke-}2) \end{aligned}$$Karena pada iterasi ke-$2$ sisa hasil baginya $0,$ FPB dari $18$ dan $63$ adalah $\boxed{\color{red}{9}},$ yang merupakan sisa hasil bagi pada iterasi ke-$1.$
Masih dua iterasi saja, ya, untuk contoh di atas.
Contoh 3:
Kita akan mencari FPB dari $52$ dan $124$ menggunakan algoritma Euclides.
$$\begin{aligned} 124 & = 2 \cdot 52 + 20 && (\text{Iter}\text{asi ke-}1) \\ 52 & = 2 \cdot 20 + 12 && (\text{Iter}\text{asi ke-}2) \\ 20 & = 1 \cdot 12 + 8 && (\text{Iter}\text{asi ke-}3) \\ 12 & = 1 \cdot 8 + \color{red}{4} && (\text{Iter}\text{asi ke-}4) \\ 8 & = 2 \cdot 4 + 0 && (\text{Iter}\text{asi ke-}5) \end{aligned}$$Karena pada iterasi ke-$5,$ sisa hasil baginya $0,$ FPB dari $52$ dan $124$ adalah $\boxed{\color{red}{4}},$ yang merupakan sisa hasil bagi pada iterasi ke-$4.$
Waduyy! Sudah $5$ iterasi, ya, padahal bilangannya baru ratusan.
Contoh 4:
Kita akan mencari FPB dari $321$ dan $843$ menggunakan algoritma Euclides.
$$\begin{aligned} 843 & = 2 \cdot 321 + 201 && (\text{Iter}\text{asi ke-}1) \\ 321 & = 1 \cdot 201 + 120 && (\text{Iter}\text{asi ke-}2) \\ 201 & = 1 \cdot 120 + 81 && (\text{Iter}\text{asi ke-}3) \\ 120 & = 1 \cdot 81+ 39 && (\text{Iter}\text{asi ke-}4) \\ 81 & = 2 \cdot 39 + \color{red}{3} && (\text{Iter}\text{asi ke-}5) \\ 39 & = 13 \cdot 3 + 0 && (\text{Iter}\text{asi ke-}6) \end{aligned}$$Karena pada iterasi ke-$6,$ sisa hasil baginya $0,$ FPB dari $321$ dan $843$ adalah $\boxed{\color{red}{3}},$ yang merupakan sisa hasil bagi pada iterasi ke-$5.$
Contoh 5:
Kita akan mencari FPB dari $3.579$ dan $4.567$ menggunakan algoritma Euclides.
$$\begin{aligned} 4.567 & = 1 \cdot 3.579 + 988 && (\text{Iter}\text{asi ke-}1) \\ 3.579 & = 3 \cdot 988 + 615 && (\text{Iter}\text{asi ke-}2) \\ 988 & = 1 \cdot 615 + 373 && (\text{Iter}\text{asi ke-}3) \\ 615 & = 1 \cdot 373 + 242 && (\text{Iter}\text{asi ke-}4) \\ 373 & = 1 \cdot 242 + 131 && (\text{Iter}\text{asi ke-}5) \\ 242 & = 1 \cdot 131 + 111 && (\text{Iter}\text{asi ke-}6) \\ 131 & = 1 \cdot 111 + 20 && (\text{Iter}\text{asi ke-}7) \\ 111 & = 5 \cdot 20 + 11 && (\text{Iter}\text{asi ke-}8) \\ 20 & = 1 \cdot 11 + 9 && (\text{Iter}\text{asi ke-}9) \\ 11 & = 1 \cdot 9 + 2 && (\text{Iter}\text{asi ke-}10) \\ 9 & = 4 \cdot 2 + \color{red}{1} && (\text{Iter}\text{asi ke-}11) \\ 2 & = 2 \cdot 1 + 0 && (\text{Iter}\text{asi ke-}12) \end{aligned}$$Karena pada iterasi ke-$12,$ sisa hasil baginya $0,$ FPB dari $3.579$ dan $4.567$ adalah $\boxed{\color{red}{1}},$ yang merupakan sisa hasil bagi pada iterasi ke-$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 Euclides.
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 Euclides.
$$\begin{aligned} 1.677 & = 1 \cdot 1.157 + 520 && (\text{Iter}\text{asi ke-}1) \\ 1.157 & = 2 \cdot 520 + 117 && (\text{Iter}\text{asi ke-}2) \\ 520 & = 4 \cdot 117 + 52 && (\text{Iter}\text{asi ke-}3) \\ 117 & = 2 \cdot 52 + 13 && (\text{Iter}\text{asi ke-}4) \\ 52 & = 4 \cdot 13 + 0 && (\text{Iter}\text{asi ke-}5) \end{aligned}$$Karena pada iterasi ke-$5,$ sisa hasil baginya $0,$, FPB dari $1.157$ dan $1.677$ adalah $\boxed{\color{red}{13}},$ yang merupakan sisa hasil bagi pada iterasi ke-$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 ke-}1) \end{aligned}$$Karena sisa hasil baginya $0$ pada iterasi pertama, $\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 Euclides.
Karena algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, kita harus memilih $2$ dari $3$ bilangan tersebut untuk dicari FPB-nya terlebih dahulu.
Misalkan kita memilih bilangan $1.564$ dan $2.323.$ Akan dicari $\text{FPB}(1.564, 2.323)$ menggunakan algoritma Euclides.
$$\begin{aligned} 2.323 & = 1 \cdot 1.564 + 759 && (\text{Iter}\text{asi ke-}1) \\ 1.564 & = 2 \cdot 759 + 46 && (\text{Iter}\text{asi ke-}2) \\ 759 & = 16 \cdot 46 + \color{red}{23} && (\text{Iter}\text{asi ke-}3) \\ 46 & = 2 \cdot 23 + 0&& (\text{Iter}\text{asi ke-}4) \end{aligned}$$Karena pada iterasi ke-$4,$ sisa hasil baginya $0,$ FPB dari $1.564$ dan $2.323$ adalah $\boxed{\color{red}{23}},$ yang merupakan sisa hasil bagi pada iterasi ke-$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 ke-}1) \end{aligned}$$Karena sisa hasil baginya $0$ pada iterasi pertama, $\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 Euclides.
Karena algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, 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 Euclides.
$$\begin{aligned} 2.001 & = 1 \cdot 1.015 + 986 && (\text{Iter}\text{asi ke-}1) \\ 1.015 & = 1 \cdot 986 + \color{red}{29} && (\text{Iter}\text{asi ke-}2) \\ 986 & = 34 \cdot 29 + 0 && (\text{Iter}\text{asi ke-}3) \end{aligned}$$Karena pada iterasi ke-$3,$ sisa hasil baginya $0,$ FPB dari $1.015$ dan $2.001$ adalah $\boxed{\color{red}{29}},$ yang merupakan sisa hasil bagi pada iterasi ke-$2.$
Setelah itu, cari $\text{FPB}(29, 2.871, 3.915)$. Dapat 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 Euclides 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 Bézout dan menyelesaikan persamaan Diophantine. Kedua materi tersebut akan dibahas pada pos terpisah.