Algoritme Euclid
Algoritme Euclid muncul sebagai Proposisi II dalam Book VII ("Elementary Number Theory") dari Elements. [45] Euclid mengajukan permasalahan: "Ambil dua angka bukan prima, untuk mencari bilangan pembagi terbesar". Dia menentukan "Sebuah angka [merupakan] besaran yang terdiri dari unit-unit": angka penghitung, integer positif kecuali 0. Dan "mengukur" adalah menempatkan ukuran panjang terkecil s dengan tepat (q kali) di antara ukuran terpanjang l sampai sisa r lebih kecil dari panjang terkecil s. [46] Dalam dunia modern, sisa r = l - q*s, q sebagai hasil bagi, atau sisa r adalah "modulus", bagian sisa-integer yang tersisa setelah pembagian. [47]
Supaya metode Euclid berhasil, panjang awalnya harus memenuhi dua kebutuhan: (i) panjangnya tidak 0, DAN (ii) hasil pengurangan harus "lebih", sebuah pengujian harus menjamin bahwa bilangan terkecil dari dua angka adalah hasil pengurangan dari yang terbesar (cara lain, keduanya bisa sama sehingga pengurangan menghasilkan 0).
Pembuktian asli Euclid mengikutkan kebutuhan yang ketiga: kedua panjang bukanlah bilangan prima. Euclid menentukan hal ini supaya dia bisa membentuk sebuah bukti reductio ad absurdum bahwa dua pembagi dua angka adalah yang terbesar. [48] Walau algoritme Nicomachus sama dengan Euclid, bila kedua bilangan prima maka menghasilkan angka "1" untuk bilangan pembagi terbesar.
Tidak ada komentar:
Posting Komentar