Trong
toán học,
giải thuật Euclid[gc 1] (hay
thuật toán Euclid) là một
giải thuật để tính
ước chung lớn nhất (ƯCLN) của hai
số nguyên, là số lớn nhất có thể chia được bởi hai số nguyên đó với
số dư bằng không. Giải thuật này được đặt tên theo nhà toán học người Hy Lạp cổ đại
Euclid, người đã viết nó trong bộ
Cơ sở của ông (khoảng năm 300 TCN). Nó là một ví dụ về
thuật toán, một chuỗi các bước tính toán theo điều kiện nhất định và là một trong số những thuật toán lâu đời nhất được sử dụng rộng rãi.Giải thuật Euclid dựa trên nguyên tắc là ước chung lớn nhất của hai số nguyên không thay đổi khi thay số lớn hơn bằng hiệu của nó với số nhỏ hơn. Chẳng hạn, 21 là ƯCLN của 252 và 105 (vì 252 = 21 × 12 và 105 = 21 × 5) và cũng là ƯCLN của 105 và 252 − 105 = 147. Khi lặp lại quá trình trên thì hai số trong cặp số ngày càng nhỏ đến khi chúng bằng nhau, và khi đó chúng là ƯCLN của hai số ban đầu. Bằng cách
đảo ngược lại các bước, ƯCLN này có thể được biểu diễn thành tổng của hai số hạng, mỗi số hạng bằng một trong hai số đã cho nhân với một số nguyên dương hoặc âm (
đồng nhất thức Bézout), chẳng hạn, 21 = 5 × 105 + (−2) × 252.Dạng ban đầu của giải thuật như trên có thể tốn nhiều bước thực hiện phép trừ để tìm ƯCLN nếu một trong hai số lớn hơn rất nhiều so với số còn lại. Một dạng khác của giải thuật rút ngắn lại các bước này, thay vào đó thế số lớn hơn bằng số dư của nó khi chia cho số nhỏ hơn (dừng lại khi số dư bằng không). Dạng thuật toán này chỉ tốn số bước nhiều nhất là năm lần số chữ số của số nhỏ hơn trên
hệ thập phân.
Gabriel Lamé chứng minh được điều này vào năm 1844, đánh dấu sự ra đời của
lý thuyết độ phức tạp tính toán. Nhiều phương pháp khác để tăng hiệu quả của thuật toán cũng đã được phát triển trong thế kỷ 20.Giải thuật Euclid có rất nhiều ứng dụng trong lý thuyết và thực tế. Nó được dùng để rút gọn
phân số về
dạng tối giản và thực hiện phép chia trong
số học module. Thuật toán cũng là một thành phần then chốt trong
giao thức mật mã để bảo mật kết nối
Internet và được dùng để phá vỡ hệ thống mật mã này qua
phân tích số nguyên. Nó cũng được áp dụng để giải
phương trình Diophantine, chẳng hạn như tìm một số thỏa mãn nhiều biểu thức đồng dư theo
định lý số dư Trung Quốc, để xây dựng
liên phân số hay tìm
xấp xỉ gần đúng nhất cho số thực. Cuối cùng, nó là công cụ cơ bản để chứng minh nhiều định lý trong
lý thuyết số như
định lý bốn số chính phương của Lagrange và
tính duy nhất của phân tích số nguyên ra thừa số nguyên tố. Thuật toán Euclid ban đầu chỉ được giới hạn về
số tự nhiên và độ dài hình học (
số thực), nhưng đến thế kỷ 19 đã được mở rộng cho nhiều dạng số khác như
số nguyên Gauss và
đa thức một biến, dẫn đến các khái niệm về
đại số trừu tượng như
miền Euclid.