Algoritma Euclid untuk 1071 dan 465 melewati sisa 141, 42, 15, 12 menuju FPB 3

Ambil sisa terus sampai sisanya 0. Sisa tak-nol terakhir ialah FPB.

Persamaan dan aljabar · Tingkat: Hasil klasik · Diperbarui pada 2026-11-10

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.

Ini adalah situs alat pihak ketiga yang independen. Situs ini tidak berafiliasi dengan, disponsori oleh, atau diizinkan oleh Casio, Texas Instruments, maupun distributor mereka. Nama model dan nama produk adalah merek dagang dari pemiliknya masing-masing dan ditampilkan di sini hanya untuk mengidentifikasi perangkat.

Urutan penekanan tombol dalam manual ini ditulis berdasarkan data tata letak milik situs ini sendiri — data yang sama yang ditampilkan oleh kalkulator online — serta fakta produk yang tersedia untuk umum. Spesifikasi dan konfigurasi regional dikonfirmasi terhadap perangkat fisik dan materi terbaru dari produsen.