Để tìm các số tự nhiên n thỏa mãn n + 4 và 3n - 5 nguyên tố cùng nhau, ta cần kiểm tra điều kiện là ước chung lớn nhất (UCLN) của hai số này phải là 1.

Ta sẽ giải bài toán bằng cách sử dụng thuật toán Euclid để tính UCLN của hai số.

Bước 1: Gán a = n + 4 và b = 3n - 5.
Bước 2: Sử dụng thuật toán Euclid để tính UCLN của a và b.
- Nếu b = 0, UCLN(a, b) = a.
- Nếu b ≠ 0, thực hiện phép chia lấy dư a cho b, gán a = b và b = a % b, sau đó quay lại Bước 2.
Bước 3: Kiểm tra UCLN(a, b) có bằng 1 hay không.
- Nếu UCLN(a, b) = 1, n là số tự nhiên thỏa mãn yêu cầu.
- Nếu UCLN(a, b) ≠ 1, n không thỏa mãn yêu cầu.

Ví dụ:
Giả sử n = 10.
Ta có a = 10 + 4 = 14 và b = 3(10) - 5 = 25.
Áp dụng thuật toán Euclid:
Bước 1: a = 14, b = 25.
Bước 2: a = 25, b = 14.
Bước 2: a = 14, b = 11.
Bước 2: a = 11, b = 3.
Bước 2: a = 3, b = 2.
Bước 2: a = 2, b = 1.
Bước 2: a = 1, b = 0.
Bước 3: UCLN(a, b) = 1.
Vậy n = 10 là một số tự nhiên thỏa mãn yêu cầu.

Tương tự, ta có thể áp dụng thuật toán trên để tìm các số tự nhiên n khác thỏa mãn yêu cầu.