Giả sử n và 2n+1 không phải là cặp số nguyên tố cùng nhau, nghĩa là chúng có ước chung khác
Gọi ước chung đó là u (u # 1).Vì u là ước của n nên suy ra u cũng là ước của 2n (*) 
Mặt khác u là ước của 2n+1 (**) 
Từ (*) và (**) => u cũng là ước của 1 => u chỉ có thể là 1 (mâu thuẫn giả thiết) => n và 2n+1 là cặp số nguyên tố cùng nhau.