Setiap bilangan bulat positif memiliki faktor (pembagi). Misalnya, memiliki faktor , dan dirinya sendiri, yaitu Keempat bilangan ini disebut faktor dari karena membagi habis 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 dan , ditulis adalah . 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 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 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.
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 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
Diberikan dua bilangan bulat positif dan dengan . dapat ditentukan dengan melakukan iterasi (iteration) algoritma pembagian seperti berikut. Proses dilakukan sampai sisa hasil baginya dan algoritma dihentikan. Nilai , yaitu sisa terakhir dari pembagian di atas yang bukan nol merupakan .
Sebelum membuktikan algoritma Euclides, perlu kita buktikan lema berikut terlebih dahulu.
Lema: Jika dengan , maka
Bukti
Misalkan . Akan dibuktikan bahwa
Karena haruslah membagi habis dan
Diketahui ekuivalen dengan Dua suku itu memuat faktor yang habis dibagi sehingga juga habis membagi
Selanjutnya, misalkan ada bilangan bulat sehingga membagi habis dan . Di sini, belum tentu merupakan (Sebagai ilustrasi, habis membagi dan tetapi bukan
Selanjutnya dapat ditulis dan untuk suatu Kita peroleh, sehingga membagi habis
Karena serta membagi habis dan disimpulkan bahwa juga membagi habis .
Dengan kata lain, menjadi faktor sekutu terbesar dengan
Jadi, terbukti bahwa
[collapse]
Bukti Algoritma Euclides Algoritma berhenti ketika diperoleh suatu Hal ini dikarenakan sisa suatu pembagian terkecil yang mungkin adalah serta fakta bahwa Dengan menggunakan lema yang telah dibuktikan di atas bahwa disimpulkan bahwa algoritma Euclides terbukti.
Pada awalnya, pendekatan geometris dipakai Euclid untuk mencari FPB dua buah bilangan seperti tampak pada gambar berikut.
Algoritma Euclides Secara Geometris
Jarak satu titik ke titik lain mewakili bilangan yang dimaksud. Misalkan akan dicari FPB dari panjang dan . Karena lebih pendek dari , dipakai untuk mengukur tetapi cukup sekali saja karena sisanya, lebih pendek dari Selanjutnya, dipakai untuk mengukur , ternyata butuh dua kali (ditandai dengan warna merah), dengan sisa . Terakhir, dipakai untuk mengukur dan tepat kali pengukuran tanpa menghasilkan sisa panjang (ditandai dengan warna biru). Dengan kata lain, . Disimpulkan bahwa merupakan FPB yang kita cari.
FPB dari tiga bilangan atau lebih dapat dicari dengan mengalikan faktor-faktor prima bersama dengan pangkat terkecil dari bilangan-bilangan itu. Misalnya, karena haruslah Selain itu, FPB dari tiga atau lebih bilangan bisa dicari dengan mencari FPB masing-masing pasangan dua bilangan yang ada, yaitu 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 dan dengan KPK dari dan sama dengan hasil kali dan dibagi dengan nilai FPB-nya, ditulis
Contoh 1:
Kita akan mencari FPB dari dan menggunakan algoritma Euclides. Karena pada iterasi ke- sisa hasil baginya FPB dari dan adalah yang merupakan sisa hasil bagi pada iterasi ke- 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 dan menggunakan algoritma Euclides. Karena pada iterasi ke- sisa hasil baginya FPB dari dan adalah yang merupakan sisa hasil bagi pada iterasi ke- Masih dua iterasi saja, ya, untuk contoh di atas.
Contoh 3:
Kita akan mencari FPB dari dan menggunakan algoritma Euclides. Karena pada iterasi ke- sisa hasil baginya FPB dari dan adalah yang merupakan sisa hasil bagi pada iterasi ke- Waduyy! Sudah iterasi, ya, padahal bilangannya baru ratusan.
Contoh 4:
Kita akan mencari FPB dari dan menggunakan algoritma Euclides. Karena pada iterasi ke- sisa hasil baginya FPB dari dan adalah yang merupakan sisa hasil bagi pada iterasi ke-
Contoh 5:
Kita akan mencari FPB dari dan menggunakan algoritma Euclides. Karena pada iterasi ke- sisa hasil baginya FPB dari dan adalah yang merupakan sisa hasil bagi pada iterasi ke- Kita sebut dan relatif prima karena memiliki FPB
Contoh 6
Kita akan mencari FPB dari , , dan 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 dan . Akan dicari menggunakan algoritma Euclides. Karena pada iterasi ke- sisa hasil baginya , FPB dari dan adalah yang merupakan sisa hasil bagi pada iterasi ke- Langkah selanjutnya adalah mencari yaitu Karena sisa hasil baginya pada iterasi pertama, Jadi, kita simpulkan bahwa FPB dari , , dan adalah
Contoh 7:
Kita akan mencari FPB dari , , dan menggunakan algoritma Euclides. Karena algoritma tersebut hanya berlaku untuk mencari FPB dari dua bilangan, kita harus memilih dari bilangan tersebut untuk dicari FPB-nya terlebih dahulu. Misalkan kita memilih bilangan dan Akan dicari menggunakan algoritma Euclides. Karena pada iterasi ke- sisa hasil baginya FPB dari dan adalah yang merupakan sisa hasil bagi pada iterasi ke- Langkah selanjutnya adalah mencari yaitu Karena sisa hasil baginya pada iterasi pertama, Jadi, kita simpulkan bahwa FPB dari , , dan adalah
Contoh 8:
Kita akan mencari FPB dari , , , dan 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 dan Akan dicari menggunakan algoritma Euclides. Karena pada iterasi ke- sisa hasil baginya FPB dari dan adalah yang merupakan sisa hasil bagi pada iterasi ke- Setelah itu, cari . Dapat diperiksa bahwa dan habis dibagi Oleh karena itu, dapat kita simpulkan bahwa mengimplikasikan bahwa
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, sama dengan dikali berapa, lalu ditambah berapa. Ya, jawabannya dikali , hasilnya , lalu ditambah , supaya hasilnya jadi 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.