Để tìm số tự nhiên \( n \) sao cho phân số \( \frac{3n + 1}{n + 2} \) là phân số tối giản, chúng ta cần kiểm tra xem tử số \( 3n + 1 \) và mẫu số \( n + 2 \) có ước chung lớn nhất (ƯCLN) là 1 hay không. Điều này có nghĩa là \( \gcd(3n + 1, n + 2) = 1 \).

Ta sẽ sử dụng thuật toán Euclid để tính ƯCLN.

1. Tính \( 3n + 1 \) và \( n + 2 \):
- Tử số: \( a = 3n + 1 \)
- Mẫu số: \( b = n + 2 \)

2. Áp dụng thuật toán Euclid:
\[
\gcd(a, b) = \gcd(3n + 1, n + 2)
\]
Ta sẽ tính \( a \mod b \):
\[
a \mod b = (3n + 1) \mod (n + 2)
\]

Tính \( 3n + 1 \) theo \( n + 2 \):
- Khi \( n + 2 \) lấy \( 3n + 1 \):
\[
3n + 1 - 3(n + 2) = 3n + 1 - 3n - 6 = -5
\]
Hay nói cách khác:
\[
(3n + 1) = 3(n + 2) - 5
\]
Vậy nên:
\[
\gcd(3n + 1, n + 2) = \gcd(n + 2, 5)
\]

3. Tính \( \gcd(n + 2, 5) \):
Khi đó, \( \gcd(n + 2, 5) = 1 \) khi \( n + 2 \) không chia hết cho 5. Điều này có nghĩa là \( n + 2 \neq 5k \) với mọi số nguyên \( k \). Tương đương với
\[
n \neq 5k - 2
\]
với \( k \) là số nguyên.

4. Xét các số tự nhiên \( n \):
Các giá trị \( n \) tự nhiên đều có thể chọn, nhưng cần chú ý những số mang dạng \( 5k - 2 \). Các số tự nhiên cần tránh là:
- \( n = 3 \) (khi \( k = 1 \)), vì \( 5 \cdot 1 - 2 = 3 \)
- \( n = 8 \) (khi \( k = 2 \)), vì \( 5 \cdot 2 - 2 = 8 \)
- \( n = 13 \) (khi \( k = 3 \)), vì \( 5 \cdot 3 - 2 = 13 \)
- ...

Vậy tất cả số tự nhiên có dạng \( n = 5k - 2 \) (với \( k \) là số nguyên) sẽ không làm cho phân số tối giản. Còn lại các số tự nhiên khác đều thỏa mãn điều kiện \( \gcd(3n + 1, n + 2) = 1 \).