Thuật toán Euclid trên 1071 và 465 đi tới ƯCLN 3 qua các số dư 141, 42, 15, 12

Lấy số dư cho tới khi một bên bằng không; số dư khác không cuối cùng là ước chung lớn nhất.

Phương trình và đại số · Mức độ: Kết quả kinh điển · Cập nhật ngày 2026-11-10

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.

Đây là một trang công cụ độc lập của bên thứ ba. Trang không liên kết, được tài trợ hay ủy quyền bởi Casio, Texas Instruments hoặc các nhà phân phối của họ. Tên model và sản phẩm là nhãn hiệu của các chủ sở hữu tương ứng và chỉ được dùng ở đây để nhận diện thiết bị.

Các chuỗi phím trong những hướng dẫn này được viết dựa trên dữ liệu bố cục riêng của trang — chính là dữ liệu mà máy tính trực tuyến sử dụng — cùng với thông tin sản phẩm công khai. Thông số kỹ thuật và cấu hình theo khu vực được kiểm chứng trên thiết bị thật và tài liệu mới nhất của nhà sản xuất.