1071 mod 465 bằng 141. 465 mod 141 bằng 42. 141 mod 42 bằng 15; 42 mod 15 bằng 12; 15 mod 12 bằng 3 và 12 mod 3 bằng 0. Số dư khác không cuối cùng, 3, là ước chung lớn nhất và mỗi bước hợp lệ vì cùng một lý do: mọi số chia hết cả a lẫn b cũng chia hết a − qb; nên cặp số và số dư có chính xác cùng các ước. Chẳng có gì ở đây đòi hỏi phân tích thừa số, và đó là điểm thực tiễn: 3 là đáp án từ rất lâu trước khi bất kỳ ai biết vì sao 1071 là 3·357.
Thứ đáng theo dõi là số bước. Lamé chứng minh năm 1844 rằng thuật toán Euclid trên một cặp số nguyên không bao giờ cần nhiều hơn khoảng năm lần số chữ số thập phân của số nhỏ hơn, và các trường hợp tệ nhất là các số Fibonacci liên tiếp: đó là lý do 141, 42, 15, 12, 3 trên trang này co lại nhanh, khi chẳng số nào là hàng xóm Fibonacci. Bản mở rộng của cùng bảng số dư còn trả về các hệ số với 3 = 1071s + 465t; thành phần của mọi routine chia modulo trong một hệ đại số máy tính.
Đáp án
3
Cách đọc
15 mod 12, số dư khác không cuối cùng. Hai liên kết đầu là các bước mở đầu, 1071 mod 465 = 141 và 465 mod 141 = 42.
Nguồn
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
Giải trong máy tính
Các liên kết này mở đúng máy tính với các con số của bài toán đã nhập sẵn. Dòng bên trên là những gì màn hình phải hiện — hãy tự kiểm tra.