Để chứng tỏ rằng 2n và 2n + 1 là 2 số nguyên tố cùng nhau, ta cần chứng minh rằng ước chung lớn nhất của chúng là 1. Giả sử 2n và 2n + 1 có một ước chung lớn hơn 1, ký hiệu là d. Điều này có nghĩa là d chia hết cho cả 2n và 2n + 1. Ta biết rằng 2n là một số chẵn, do đó d cũng phải là một số chẵn. Khi đó, ta có thể viết d = 2k, với k thuộc N. Vì d chia hết cho 2n, ta có 2n = d * m, với m thuộc N. Thay d = 2k vào, ta có 2n = 2k * m, hay n = k * m. Điều này có nghĩa là n chia hết cho k, tức là k là một ước của n. Tuy nhiên, ta biết rằng 2n + 1 là một số lẻ. Vì vậy, d không thể chia hết cho 2n + 1. Do đó, giả thuyết ban đầu là sai và ta kết luận rằng 2n và 2n + 1 là 2 số nguyên tố cùng nhau.