Dãy Fibonacci, dãy Lucas và các ứng dụng

Các số Fibonacci rất quan trọng trong việc phân tích thời gian tính toán trong thuật toán Euclid, để xác định ước số chung lớn nhất của hai số nguyên. Ví dụ, đầu vào xấu nhất cho thuật toán này là một cặp các số Fibonacci liên tiếp. Yuri Matiyasevich đã chỉ ra rằng các số Fibonacci có thể được định nghĩa bởi một phương trình Diophant, đây là cơ sở ban đầu của ông đối với vấn đề thứ muwoif của Hilbet (Liệu có tồn tại một phương pháp chung giải phương trình Diophant?)