Chứng minh 2n + 3 và 3n + 1 nguyên tố cùng nhau

Để chứng minh rằng \(2n + 3\) và \(3n + 1\) là nguyên tố cùng nhau, chúng ta cần chứng minh rằng ước chung lớn nhất (ƯCLN) của chúng là 1, tức là \(\gcd(2n + 3, 3n + 1) = 1\).

Giả sử \(\gcd(2n + 3, 3n + 1) = d\), tức là \(d\) là ước chung của \(2n + 3\) và \(3n + 1\). Điều này có nghĩa là \(d\) chia cả \(2n + 3\) và \(3n + 1\).

Ta có:
\[ 2n + 3 = kd \]
\[ 3n + 1 = ld \]

với \(k\) và \(l\) là các số nguyên.

Bây giờ, chúng ta sẽ sử dụng phương pháp Euclid để tìm ƯCLN. Ta thực hiện phép trừ:

\[ (3n + 1) - (2n + 3) = ld - kd \]
\[ 3n + 1 - 2n - 3 = ld - kd \]
\[ n - 2 = (l - k)d \]

Điều này có nghĩa là \(d\) cũng chia \(n - 2\).

Tiếp tục, ta thực hiện phép trừ khác:

\[ 2(3n + 1) - 3(2n + 3) = 2ld - 3kd \]
\[ 6n + 2 - 6n - 9 = 2ld - 3kd \]
\[ -7 = (2l - 3k)d \]

Điều này có nghĩa là \(d\) cũng chia \(-7\). Vì \(7\) là số nguyên tố, nên \(d\) chỉ có thể là \(1\) hoặc \(7\).

Nếu \(d = 7\), thì \(7\) phải chia cả \(2n + 3\) và \(3n + 1\). Tuy nhiên, ta sẽ kiểm tra điều này:

Giả sử \(2n + 3 \equiv 0 \pmod{7}\), tức là:
\[ 2n + 3 \equiv 0 \pmod{7} \]
\[ 2n \equiv -3 \pmod{7} \]
\[ 2n \equiv 4 \pmod{7} \]
\[ n \equiv 2 \pmod{7} \]

Giả sử \(3n + 1 \equiv 0 \pmod{7}\), tức là:
\[ 3n + 1 \equiv 0 \pmod{7} \]
\[ 3n \equiv -1 \pmod{7} \]
\[ 3n \equiv 6 \pmod{7} \]
\[ n \equiv 2 \pmod{7} \]

Từ hai điều trên, ta thấy rằng \(n \equiv 2 \pmod{7}\) thỏa mãn cả hai điều kiện. Tuy nhiên, điều này không mâu thuẫn với giả thiết ban đầu rằng \(d = 1\).

Do đó, \(d\) không thể là \(7\), và do đó \(d\) phải là \(1\).

Vậy, \(\gcd(2n + 3, 3n + 1) = 1\), tức là \(2n + 3\) và \(3n + 1\) là nguyên tố cùng nhau.