1071 mod 465 ialah 141. 465 mod 141 ialah 42. 141 mod 42 ialah 15, 42 mod 15 ialah 12, 15 mod 12 ialah 3, 12 mod 3 ialah 0. Sisa tak-nol terakhir, 3, ialah FPB, dan alasan setiap langkah dibolehkan selalu sama: bilangan yang membagi a dan b juga membagi a − qb, sehingga pasangan bilangan dan sisanya punya pembagi yang persis sama. Tidak perlu faktorisasi di sini, dan itulah makna praktisnya. 3 menjadi jawaban jauh sebelum siapa pun tahu mengapa 1071 ialah 3·357.
Banyaknya langkah layak diperhatikan. Pada 1844 Lamé membuktikan bahwa algoritma Euclid untuk dua bilangan bulat tidak pernah melebihi sekitar lima kali jumlah digit desimal yang lebih kecil, dan kasus terburuknya adalah bilangan Fibonacci yang bersebelahan. Maka 141, 42, 15, 12, 3 di halaman ini menyusut cepat; di sini tak satu pun merupakan tetangga Fibonacci. Versi perluasan dari tabel sisa yang sama bahkan memberi koefisien yang memenuhi 3 = 1071s + 465t, bahan bagi setiap prosedur pembagian modular dalam sistem aljabar komputer.
Jawaban
3
Cara membacanya
15 mod 12, sisa tak-nol terakhir. Dua tautan sebelumnya ialah langkah pertama 1071 mod 465 = 141 dan 465 mod 141 = 42.
Sumber
Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give
Kerjakan di kalkulator
Tautan ini membuka kalkulator yang tepat dengan angka soal ini sudah diketik. Baris di atas adalah yang seharusnya ditampilkan layar — periksa sendiri.