Để chứng minh rằng 2n+1 và 3n+1 là hai số nguyên tố cùng nhau, ta sẽ sử dụng định lý Euclid.

Định lý Euclid: Nếu hai số nguyên a và b không chia hết cho nhau (tức là UCLN(a, b) = 1), thì tồn tại hai số nguyên x và y sao cho ax + by = 1.

Giả sử 2n+1 và 3n+1 không phải là hai số nguyên tố cùng nhau, tức là UCLN(2n+1, 3n+1) ≠ 1. Khi đó, theo định lý Euclid, tồn tại hai số nguyên x và y sao cho (2n+1)x + (3n+1)y = 1.

Tiếp theo, ta sẽ chứng minh rằng phương trình trên không thể xảy ra.

(2n+1)x + (3n+1)y = 1
2nx + x + 3ny + y = 1
(2nx + 3ny) + (x + y) = 1
n(2x + 3y) + (x + y) = 1

Vì n là số tự nhiên, n(2x + 3y) là một số tự nhiên. Tuy nhiên, x + y không thể là một số tự nhiên vì nếu như vậy, ta sẽ có n(2x + 3y) + (x + y) ≥ n + 1 > 1, mâu thuẫn với phương trình trên.

Vậy giả thuyết ban đầu là sai, tức là 2n+1 và 3n+1 là hai số nguyên tố cùng nhau.