Kalkulator Algoritma Euclid

a = q * b + r, sehingga FPB(a, b) = FPB(b, r); ulangi sampai r = 0, dan b adalah jawabannya

a = q * b + r

Satu putaran algoritma, ditulis sebagai persamaan. a adalah bilangan yang lebih besar pada putaran ini, b yang lebih kecil, q adalah berapa kali utuh b masuk ke dalam a, dan r adalah sisanya. Inilah notasi yang sama dengan langkah-langkah tercetak di halaman, tempat angkanya muncul tanpa pemisah ribuan: 1.071 = 2 * 462 + 147 adalah satu putaran

a, b

Dua bilangan yang dibandingkan. Keduanya bertukar peran setiap putaran — b pada satu putaran menjadi a pada putaran berikutnya, dan r menjadi b yang baru. Pertukaran inilah sebabnya kedua kolom masukan tidak bernama bilangan yang dibagi dan pembagi: pada putaran pertama 1.071 adalah yang dibagi, pada putaran kedua 462, sehingga satu label yang benar untuk satu putaran menjadi salah pada putaran lain

q

Hasil bagi, yaitu berapa kali utuh b masuk ke dalam a. Nilainya selalu sekurang-kurangnya 1, karena pasangannya disusun menurun sebelum perulangan dimulai — dan karena itu pula Anda tidak akan pernah melihat q = 0 di sini. Satu-satunya putaran yang hasil baginya tidak menarik perhatian adalah putaran terakhir, tempat sisanya nol dan pembagiannya pas

r

Sisanya, selalu lebih kecil daripada b dan tidak pernah negatif. Aturan berhentinya algoritma adalah r = 0, yang dicetak sebagai putaran terakhir alih-alih dihilangkan: 147 = 7 * 21 + 0 adalah baris yang mengatakan bahwa pencarian sudah selesai dan bahwa 21 adalah jawabannya

FPB(a, b)

Faktor persekutuan terbesar: bilangan bulat terbesar yang membagi habis a dan b tanpa sisa. Jawabannya adalah b pada putaran terakhir, diambil langsung dari perulangan alih-alih dihitung ulang. Untuk 1.071 dan 462 jawabannya 21, dan karena itu 1.071 = 21 × 51 serta 462 = 21 × 22, dan tidak ada bilangan yang lebih besar yang membagi habis keduanya

610 = 1 * 377 + 233

Putaran pembuka kasus terburuk: dua bilangan Fibonacci yang berurutan. Setiap hasil bagi di sini bernilai 1 dan angkanya hampir tidak menyusut, dan itulah yang membuat pasangan ini perlu tiga belas putaran. Teorema Lamé mengatakan tidak ada pasangan seukuran ini yang bisa lebih lama

Menyederhanakan pecahan adalah pemakaian sehari-hari. Untuk menulis pecahan yang dibentuk 462 dan 1.071 dalam bentuk paling sederhana, Anda memerlukan faktor persekutuan terbesar keduanya, dan halaman ini menyerahkan bilangan itu beserta buktinya — 21, dan tiga putaran yang menghasilkannya. Membagi kedua bilangan dengan 21 menghasilkan 22 dan 51, yang tidak lagi punya faktor bersama. Kebutuhan yang sama muncul setiap kali sebuah perbandingan harus disederhanakan: rasio roda gigi, perbandingan sisi layar, gambar berskala, dan pembagian rata tanpa sisa. Pertanyaannya selalu sama, yaitu berapa bagian terbesar yang bisa dibagi rata. Mencari FPB juga langkah pertama sebelum menjumlahkan pecahan berpenyebut berbeda, karena penyebut bersama dicari dari kelipatan persekutuan terkecil kedua penyebut (lihat Kalkulator KPK).

1. Pasangan klasik dari buku teks: 1.071 dan 462

   1. Berapa kali 462 masuk ke dalam 1.071? Dua kali, dan 2 × 462 = 924, sehingga sisanya 1.071 − 924 = 147
   2. Sekarang pasangannya 462 dan 147: 147 masuk ke dalam 462 tiga kali, 3 × 147 = 441, dan sisanya 21
   3. Sekarang pasangannya 147 dan 21: 21 masuk ke dalam 147 tepat tujuh kali, dan sisanya 0
   4. Sisanya nol, jadi algoritma berhenti dan jawabannya 21

   Masukan bawaan halaman, dan contoh yang biasa dipakai untuk memperkenalkan algoritma ini. Ada dua pemeriksaan yang layak dilakukan atas hasilnya. Bagi kedua bilangan dengan 21 dan Anda sampai di 51 dan 22, yang tidak punya faktor bersama — itulah yang membuat 21 menjadi yang terbesar, bukan sekadar salah satu pembagi bersama. Lalu perhatikan bahwa tidak ada satu pun langkah yang melibatkan pemfaktoran: untuk mencari faktor 1.071 dengan uji bagi Anda harus memeriksa pembagi sampai 32, sedangkan algoritma ini hanya membagi sebuah bilangan dengan bilangan yang sudah ada di tangan. Tiga putaran, masing-masing lebih murah daripada sebelumnya.

2. Satu putaran saja cukup: 12 dan 60

   1. Susun pasangannya menurun: 60 lebih dulu, lalu 12
   2. 60 = 5 × 12 + 0, jadi 12 membagi habis 60
   3. Sisanya sudah nol sejak awal, jadi algoritma berhenti setelah satu putaran
   4. Jawabannya 12 — bilangan yang lebih kecil dari keduanya, karena ia membagi habis yang lebih besar

   Putaran tidak trivial yang paling pendek, dan kasus yang menunjukkan mengapa putaran terakhir dicetak alih-alih dilewati. Baris 60 = 5 * 12 + 0 adalah jawaban yang utuh: baris itu mengatakan sisanya sudah nol, dan itu satu-satunya cara algoritma ini berhenti. Hilangkan baris tersebut dan daftar langkahnya menjadi kosong, sehingga pembaca tidak bisa membedakan jawaban satu putaran dari halaman yang tidak menjalankan apa pun. Setiap kali satu bilangan membagi habis bilangan lain, faktor persekutuan terbesarnya adalah yang lebih kecil dari keduanya.

3. Bilangan koprima: 9 dan 20

   1. 20 = 2 × 9 + 2, jadi pasangannya menjadi 9 dan 2
   2. 9 = 4 × 2 + 1, jadi pasangannya menjadi 2 dan 1
   3. 2 = 2 × 1 + 0, jadi algoritma berhenti
   4. Jawabannya 1, yang berarti 9 dan 20 tidak punya faktor bersama di atas 1

   Faktor persekutuan terbesar yang bernilai 1 adalah jawaban sungguhan, bukan kegagalan, dan punya nama: kedua bilangan itu disebut koprima. Nilai 1 juga punya arti praktis, yaitu pecahan 9/20 sudah dalam bentuk paling sederhana sehingga tidak ada penyederhanaan yang tersisa. Semakin besar bilangannya, pasangan koprima semakin menjadi kasus yang lazim — itulah sebabnya metode ini penting dalam kriptografi, karena menyusun kunci RSA berarti mencari bilangan yang tidak berbagi faktor dengan bilangan tertentu.

Kedua bilangan harus bulat, dan keduanya harus berada di antara 1 dan 1.000.000. Nol ditolak alih-alih diperlakukan sebagai kasus khusus. Faktor persekutuan terbesar dari a dan 0 adalah a, yang merupakan jawaban sah, tetapi halaman ini tidak bisa menampilkannya: putaran pertamanya adalah a = q * 0 + r, dan q semacam itu tidak ada. Daripada mencetak proses yang berlubang, halaman ini menolak masukannya. Bilangan negatif ditolak karena alasan yang sama — langkah-langkahnya, sebagaimana dicetak, mengandaikan kedua bilangan minimal 1, dan satu operan negatif akan menuntut aturan tentang arti hasil bagi dan sisanya yang tidak dinyatakan di mana pun pada halaman ini. Batas 1.000.000 bukan soal algoritmanya, yang akan berjalan lancar pada bilangan jauh lebih besar; batas itu ada agar setiap pengurangan, perkalian, dan sisa di sepanjang jalan bersifat eksak dalam aritmetika biasa berpresisi ganda, dan agar langkah yang tercetak tidak sampai menjadi sepanjang yang tidak lagi terbaca. Dua bilangan yang cukup kecil tetap bisa menghasilkan banyak putaran — 610 dan 377 perlu tiga belas — tetapi dalam praktik jumlahnya dibatasi oleh batas atas itu, dan tabel referensi memuat kolom jumlah putaran justru supaya Anda bisa melihatnya bervariasi. Langkah-langkahnya dicetak sebagai persamaan — a = q * b + r, dipisahkan titik koma — dan bukan sebagai pembagian bersusun, jadi kalau Anda mencari bentuk pembagian berkurung yang biasa, halaman ini tidak menyediakannya. Kedua masukan bisa ditukar: halaman ini menyusunnya menurun sebelum mulai, sehingga Anda tidak bisa memakai halaman ini untuk melihat bagaimana bentuk 3 = 0 * 5 + 3, karena putaran itu tidak pernah dihasilkan. Langkah-langkahnya adalah teks biasa: angka di dalamnya keluar sebagai rentetan angka tanpa pemisah ribuan, sedangkan FPB-nya dicetak sebagai bilangan dan mengikuti penulisan angka bahasa Indonesia — keduanya berada di panel yang sama dengan dua gaya penulisan yang berbeda. Kalau bilangan Anda bisa negatif, atau Anda ingin aturan sisa yang dinyatakan tegas, Kalkulator Sisa Bagi adalah halaman untuk pertanyaan itu.

Apa itu faktor persekutuan terbesar, dalam satu kalimat?

Bilangan bulat terbesar yang membagi habis kedua bilangan tanpa sisa. Untuk 1.071 dan 462 jawabannya 21: 1.071 = 21 × 51 dan 462 = 21 × 22, sedangkan 51 dan 22 tidak punya faktor bersama — itulah yang membuat 21 menjadi yang terbesar. Perhatikan bahwa 3 dan 7 juga membagi habis kedua bilangan itu; keduanya pembagi bersama, hanya bukan yang terbesar. Keluaran utama halaman ini selalu bilangan tersebut, dan langkah-langkah di bawahnya adalah buktinya.

Mengapa langkah terakhir selalu berakhiran + 0?

Karena sisa yang bernilai nol adalah satu-satunya hal yang menghentikan algoritma. Perulangannya menukar pasangan dengan pasangan yang lebih kecil — bilangan kedua dan sisanya — dan angkanya turun pada setiap putaran, jadi cepat atau lambat keduanya harus mencapai nol. 147 = 7 * 21 + 0 adalah putaran tempat hal itu terjadi, dan faktor persekutuan terbesarnya adalah pembagi pada putaran itu, yaitu 21. Halaman ini mencetaknya alih-alih menyembunyikannya, karena daftar langkah yang berhenti pada sisa terakhir yang bukan nol akan membuat pembaca menyimpulkan sendiri bahwa pencariannya sudah usai.

Apakah urutan kedua bilangan yang saya masukkan berpengaruh?

Tidak. Halaman ini menyusunnya menurun sebelum putaran pertama, sehingga 462 dan 1.071 menghasilkan tiga baris yang persis sama dengan 1.071 dan 462. Ini pilihan halaman, bukan sifat algoritmanya — aturan FPB(a, b) = FPB(b, a) menjamin urutan mana pun memberi jawaban yang benar — tetapi tanpa penyusunan itu baris pertamanya akan menjadi 3 = 0 * 5 + 3 pada pasangan 3 dan 5, yang merupakan pembagian sah, namun memberi kesan bahwa membagi bilangan kecil dengan bilangan yang lebih besar adalah bagian dari metodenya. Karena itu pula kedua kolom masukan bernama bilangan pertama dan bilangan kedua, bukan yang dibagi dan pembagi: kedua peran itu berganti setiap putaran.

Apa artinya kalau jawabannya 1?

Bahwa kedua bilangan tidak berbagi faktor di atas 1, dan itu jawaban yang lengkap, bukan kegagalan. Bilangan seperti itu disebut koprima, dan pasangan 9 dan 20 di halaman ini adalah contohnya. Ada pula arti praktisnya: pecahan 9/20 sudah dalam bentuk paling sederhana, jadi tidak ada penyederhanaan yang tersedia. Semakin besar bilangannya, pasangan koprima menjadi kasus yang paling lazim, dan itulah sebabnya metode ini penting dalam kriptografi — menyusun kunci RSA berarti mencari bilangan yang tidak berbagi faktor dengan bilangan tertentu.

Apakah bilangan yang lebih besar selalu perlu lebih banyak putaran?

Tidak, dan tabel referensi di halaman ini ada untuk membuatnya konkret. 1.000.000 dan 999.998 selesai dalam dua putaran, sedangkan 610 dan 377 — masing-masing hanya tiga digit — perlu tiga belas putaran. Yang memaksa banyak putaran bukan besarnya angka, melainkan lambatnya hasil bagi menyusut. Teorema Lamé menyatakan pasangan terburuk untuk suatu ukuran selalu sepasang bilangan Fibonacci berurutan, dan 610 serta 377 adalah pasangan seperti itu.

Kalau saya hanya butuh jawabannya, apakah halaman ini yang tepat?

Bisa, tetapi halaman ini dibuat untuk orang yang ingin melihat jalannya. Faktor persekutuan terbesar selalu menjadi keluaran utama, jadi jawabannya ada di sana; bedanya, setiap putaran pembagiannya ikut dicetak, sehingga Anda bisa memeriksa hasilnya alih-alih memercayainya. Kalau yang Anda perlukan justru banyak pasangan sekaligus, atau FPB dari tiga bilangan atau lebih, Kalkulator FPB adalah halaman yang langsung memberi jawabannya tanpa langkah perantara.

• Euclidean Algorithm — the recurrence gcd(a, b) = gcd(b, a mod b), the proof that it terminates, and the connection to continued fractions — Wolfram MathWorld (United States)
• Greatest Common Divisor — what the greatest common factor is, and why gcd(a, 0) = a is the base case the algorithm stops on — Wolfram MathWorld (United States)
• Lamé's Theorem — the result that the pair taking the most rounds for its size is always a pair of consecutive Fibonacci numbers — Wolfram MathWorld (United States)