Một thuật toán để tính ước chung lớn nhất của hai số nguyên dương. Đó là Euclid(a,b) (nếu (b = 0) sau đó trở lại một; khác trở lại Euclid (b, mod b);). Thời gian chạy phức tạp là O ((đăng nhập một)(log b)) bit hoạt động.