Để chứng minh rằng \( 2n + 1 \) và \( 3n + 1 \) là hai số nguyên tố cùng nhau cho mọi \( n \) thuộc tập hợp số tự nhiên, chúng ta cần chỉ ra rằng ước số chung lớn nhất (ƯSCLN) của hai số này là 1.

Giả sử \( d \) là ước số chung của \( 2n + 1 \) và \( 3n + 1 \). Khi đó, \( d \) chia cả hai số này, nghĩa là:

\[
d \mid (2n + 1) \quad \text{và} \quad d \mid (3n + 1)
\]

Từ đó, ta có thể viết:

\[
2n + 1 \equiv 0 \mod d \quad \text{và} \quad 3n + 1 \equiv 0 \mod d
\]

Chúng ta sẽ xem xét một số phép toán giữa 2 biểu thức này. Trước tiên, chúng ta lấy hiệu của hai biểu thức:

\[
(3n + 1) - (2n + 1) = n
\]

Như vậy, ta có:

\[
d \mid n
\]

Tiếp theo, chúng ta sẽ thay \( n \) bằng \( kd \) (với \( k \) là một số nguyên). Ta thay vào các biểu thức:

1. \( 2n + 1 = 2(kd) + 1 = 2kd + 1 \)
2. \( 3n + 1 = 3(kd) + 1 = 3kd + 1 \)

Hai biểu thức có dạng:

\[
2kd + 1 \equiv 0 \mod d \quad \Rightarrow \quad 1 \equiv 0 \mod d
\]

Tương tự, đối với \( 3n + 1 \):

\[
3kd + 1 \equiv 0 \mod d \quad \Rightarrow \quad 1 \equiv 0 \mod d
\]

Đó là mâu thuẫn, vì \( d \) không thể chia hết cho 1 nếu \( d > 1 \).

Vậy nên, ước số chung lớn nhất của \( 2n + 1 \) và \( 3n + 1 \) chỉ có thể là 1, từ đó suy ra rằng \( 2n + 1 \) và \( 3n + 1 \) là hai số nguyên tố cùng nhau.

Do đó, chúng ta đã chứng minh rằng \( 2n + 1 \) và \( 3n + 1 \) là hai số nguyên tố cùng nhau với mọi \( n \in \mathbb{N} \).