Gọi d là ƯCLN(2n+1;3n+1)   (d ∈ N*)
Ta có:
+) 2n + 1 chia hết cho d
          => 3 . (2n + 1) chia hết cho d
          => 6n + 3 chia hết cho d  (1)
+) 3n + 1 chia hết cho d
          => 2 . (3n + 1) chia hết cho d
          => 6n + 2 chia hết cho d  (2)
Từ (1) và (2), ta suy ra:
     (6n + 3) - (6n + 2) chia hết cho d
=> 1 chia hết cho d
=> d = 1
Do đó, ƯCLN(2n+1;3n+1) = 1
   => 2n + 1 và 3n + 1 là 2 số nguyên tố cùng nhau  (đpcm)