Để chứng minh rằng 2n+1 và 4n+1 là hai số nguyên tố cùng nhau, ta sẽ sử dụng định lý Euclid về ước số chung lớn nhất (GCD).

Giả sử a và b là hai số nguyên dương và không chia hết cho nhau. Khi đó, GCD(a, b) = 1.

Giả sử 2n+1 và 4n+1 không phải là hai số nguyên tố cùng nhau. Khi đó, tồn tại một số nguyên dương k sao cho GCD(2n+1, 4n+1) = k > 1.

Theo định lý Euclid, ta có:
GCD(2n+1, 4n+1) = GCD(4n+1 - 2n(2), 2n+1) = GCD(1, 2n+1) = 1.

Điều này mâu thuẫn với giả định ban đầu. Vậy, 2n+1 và 4n+1 là hai số nguyên tố cùng nhau.