Thuật toán Euclid tìm ƯCLN(a, b) hoạt động theo nguyên lý:

ƯCLN(a, b) = ƯCLN(b, a % b)

Về mặt hình học, điều này tương đương với việc cố gắng lấp đầy hình chữ nhật a × b bằng các hình vuông có kích thước bằng phần nhỏ hơn b × b.

Khi lấp xong, vùng còn thừa lại (phần dư a % b) sẽ tạo thành một hình chữ nhật mới nhỏ hơn, và quá trình được lặp lại đệ quy cho đến khi hoàn toàn lấp kín bằng các hình vuông (phần dư = 0). Cạnh của hình vuông nhỏ nhất cuối cùng đó chính là Ước Chung Lớn Nhất.