QuickCalculators menjalankan algoritme Euclid pada dua bilangan bulat tak negatif, mencetak setiap hasil bagi dan sisanya hingga FPB muncul sebagai sisa bukan nol terakhir. Masukkan pasangan dalam urutan mana pun; tabel langkah menunjukkan bentuk pembagian sehingga setiap baris dapat diperiksa dengan tangan.
Temukan FPB dengan pembagian berulang
Algoritma Euclid mencari faktor persekutuan terbesar dengan membagi bilangan yang lebih besar dengan bilangan yang lebih kecil dan mengganti bilangan yang lebih besar dengan sisanya, kemudian mengulanginya. Ketika sisa nol muncul, pembagi dari langkah tersebut adalah FPB. Kalkulator Algoritma Euclid mencatat setiap divisi sehingga rantainya dapat diaudit.
Untuk 816 dan 2260, mulai dengan 2260 ÷ 816. Hasil bagi adalah 2 dan sisanya adalah 628. Selanjutnya, 816 ÷ 628 menyisakan sisa 188. Lanjutkan sampai sisa nol menghentikan rantai. Sisa bukan nol terakhir adalah FPB dari pasangan aslinya.
Baca tabel langkah
Tabel langkah mencantumkan pembagian, pembagi, hasil bagi, dan sisa untuk setiap putaran. Membaca kolom sisa menunjukkan urutan penyusutan yang berakhir pada nol. QuickCalculators menyelaraskan kolom-kolom tersebut sehingga salinan buku catatan dapat memverifikasi × b + r sama dengan dividen sebelumnya pada setiap baris.
Sketsa ringkas untuk 48 dan 18: | Dividen | Pembagi | Hasil bagi | Sisa | | --- | --- | --- | --- | | 48 | 18 | 2 | 12 | | 18 | 12 | 1 | 6 | | 12 | 6 | 2 | 0 |
Sisa bukan nol terakhir adalah 6, jadi FPB(48, 18) = 6.
Hindari kesalahan umum ini
Bentuk pengurangan dan bentuk pembagiannya merupakan algoritma yang sama. Pembagian adalah pengurangan berulang yang dikompres menjadi satu hasil bagi. Siswa terkadang memperlakukannya sebagai metode saingan dengan jawaban berbeda. Keduanya berakhir di FPB yang sama bila diterapkan dengan benar. Mengurangi 18 dari 48 dua kali akan menghasilkan 12, yang merupakan hasil bagi yang dikodekan 2 dalam satu baris.
Lebih memilih pembagian menghemat penulisan tanpa mengubah jalur matematika yang dijelaskan Euclid.
Pahami mengapa algoritme selalu berhenti
Setiap sisa adalah bilangan bulat non-negatif yang lebih kecil dari pembagi sebelumnya, sehingga barisan sisanya tidak dapat turun selamanya. Keturunan yang terbatas memaksa sisa nol setelah beberapa langkah yang terbatas. Jaminan tersebut berlaku untuk semua input bilangan bulat non-negatif yang diterima halaman.
Pasangan kasus terburuk yang terkait dengan angka Fibonacci memerlukan lebih banyak langkah daripada contoh kelas pada umumnya, namun tetap selesai. Jumlah langkah bertambah secara kasar seiring dengan logaritma masukan untuk pasangan acak biasa, itulah sebabnya metode Euclid menskalakan faktor-faktor daftar sebelumnya.
Pertanyaan yang sering diajukan
Apa algoritma Euclid?
Algoritma Euclid adalah suatu metode untuk mencari faktor persekutuan terbesar dari dua bilangan bulat tak negatif dengan cara membagi berulang-ulang dengan sisa. Sisa bukan nol yang terakhir adalah FPB. Kalkulator mencetak setiap langkah pembagian tersebut.
Bagaimana algoritma Euclid menemukan FPB?
Algoritma Euclid mencari FPB dengan mengganti bilangan yang lebih besar dengan sisa setelah pembagian dengan bilangan yang lebih kecil, berulang-ulang hingga sisanya nol. Pembagi yang digunakan pada langkah sisa bukan nol terakhir adalah FPB.
Berapakah FPB dari 816 dan 2260?
FPB dari 816 dan 2260 ditemukan dengan menjalankan algoritma Euclid pada pasangan tersebut dan membaca sisa bukan nol terakhir dari tabel langkah. Masukkan kedua bilangan bulat di halaman ini untuk melihat setiap hasil bagi dan sisanya secara berurutan.
Mengapa algoritma Euclid berhasil?
Algoritme Euclid berfungsi karena setiap pembagi persekutuan dari a dan b juga merupakan pembagi persekutuan dari b dan a mod b. Mengganti pasangan dengan angka yang lebih kecil dan sisanya akan mempertahankan FPB hingga sisanya mencapai nol.
Berapa banyak langkah yang dilakukan algoritma Euclid?
Jumlah langkah yang diambil algoritma Euclid bergantung pada masukan; setiap sisanya lebih kecil dari pembagi sebelumnya, sehingga prosesnya berhingga. Pasangan seperti Fibonacci membutuhkan lebih banyak langkah daripada rata-rata, tetapi angka-angka kelas pada umumnya selesai dengan cepat.
Apa perbedaan bentuk pengurangan dan pembagian?
Bentuk pengurangan berulang kali mengurangkan yang lebih kecil dari yang lebih besar; bentuk pembagian mengurangkan secara massal menggunakan hasil bagi. Kedua bentuk menghitung FPB yang sama. Pembagian hanyalah pengurangan berulang yang ditulis secara kompak.
Ringkasan
Kalkulator Algoritma Euclid menemukan FPB dengan pembagian berulang dan menampilkan setiap hasil bagi dan sisa dalam tabel langkah. Pasangan seperti 48 dan 18 berakhir pada sisa 6, cocok dengan FPB(48, 18). Bentuk pengurangan dan pembagian merupakan algoritma yang sama pada tingkat kompresi yang berbeda. Sisanya berkurang secara drastis, sehingga proses selalu berakhir untuk bilangan bulat non-negatif.