Định lý Euclid về số nguyên tố


Tiếp tục câu chuyện về số nguyên tố, hôm nay chúng ta sẽ chứng minh rằng tồn tại vô số các số nguyên tố. Đây chính là Định lý Euclid về số nguyên tố. Định lý này có một cách chứng minh rất là đơn giản, nhưng cách chứng minh này có lẽ là một trong những chứng minh hay nhất trong toán học.


Chúng ta chứng minh tồn tại vô số số nguyên tố như sau. Giả sử rằng $p_1$, $p_2$, ..., $p_k$ là một dãy số nguyên tố. Chúng ta chỉ ra rằng chúng ta sẽ tìm được một số nguyên tố mới không nằm trong dãy số này. Từ đó suy ra sẽ phải có vô số các số nguyên tố.

Để chỉ ra số nguyên tố mới, chúng ta xây dựng số $n = p_1 p_2 \dots p_k + 1$.


Rõ ràng $n$ sẽ có một ước số nguyên tố $p$. Nhưng vì $n$ không chia hết cho các số nguyên tố $p_i$ ở trên nên ước số nguyên tố $p$ của $n$ sẽ là một số nguyên tố mới không nằm trong dãy số này.

Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố thì chúng ta lại tìm được một số nguyên tố mới, điều đó chứng tỏ sẽ có vô hạn các số nguyên tố.


Cách chứng minh ở trên thật là hay. Chúng ta sẽ dùng phương pháp chứng minh này để giải một vài bài toán tương tự.



Bài toán 1. Chứng minh rằng có vô số các số nguyên tố có dạng $4N+3$.

Chúng ta biết rằng 2 là số nguyên tố chẵn duy nhất, còn tất cả các số nguyên tố còn lại là số nguyên tố lẻ. Một số nguyên tố lẻ thì hoặc là có dạng $4N+1$ hoặc là có dạng $4N+3$. Muốn chứng minh rằng có vô số các số nguyên tố có dạng $4N+3$, chúng ta lý luận tương tự như trên. Đó là với mọi dãy số nguyên tố $p_1$, $p_2$, ..., $p_k$ bất kỳ có dạng $4N+3$, chúng ta sẽ chỉ ra được một số nguyên tố mới không nằm trong dãy này và cũng có dạng $4N+3$.

Chúng ta xây dựng số $n = 4 p_1 p_2 \dots p_k - 1$, số này có dạng $4N+3$.

Số $n$ này sẽ phải có một ước số nguyên tố $p$ có dạng $4N+3$. Vì sao? Bởi vì $n$ là số lẻ lớn hơn 1, cho nên nếu $n$ không có ước số nguyên tố có dạng $4N+3$ thì tất cả các ước số nguyên tố của $n$ sẽ có dạng $4N+1$. Vậy $n$ sẽ là tích của các số có dạng $4N+1$. Nhưng mà chúng ta dễ dàng thấy rằng tích của các số có dạng $4N+1$ là một số có dạng $4N+1$. Cho nên $n$ cũng có dạng $4N+1$, và đây là điều vô lý.

Như vậy $n$ sẽ có ước số nguyên tố $p$ có dạng $4N+3$. Tiếp theo, chúng ta thấy rằng vì $n$ không chia hết cho các số nguyên tố $p_i$ ở trên nên ước số nguyên tố $p$ của $n$ sẽ là một số nguyên tố mới không nằm trong dãy số này. Vậy coi như chúng ta đã tìm ra lời giải cho bài toán.



Lời giải bài toán 1. Để chứng minh rằng tồn tại vô số các số nguyên tố có dạng $4N+3$, chúng ta sẽ chứng minh rằng, với mọi dãy số nguyên tố $p_1$, $p_2$, ..., $p_k$ có dạng $4N+3$, sẽ tồn tại một số nguyên tố khác cũng có dạng $4N+3$, và không nằm trong dãy số nguyên tố này.

Thực vậy, lấy $n = 4 p_1 p_2 \dots p_k - 1$, số này có dạng $4N+3$.

Đầu tiên chúng ta khẳng định rằng $n$ phải có một ước số nguyên tố có dạng $4N+3$. Đó là vì nếu tất cả các ước số nguyên tố của $n$ có dạng $4N+1$ thì $n$ sẽ là tích của các số có dạng $4N+1$, suy ra $n$ cũng có dạng $4N+1$, vô lý.

Tóm lại, $n$ có ít nhất một ước số nguyên tố $p$ có dạng $4N+3$. Cuối cùng vì $n$ không chia hết cho các số nguyên tố $p_i$ nên $p \neq p_i$.

Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố có dạng $4N+3$ thì chúng ta lại tìm được một số nguyên tố mới cũng có dạng $4N+3$, do đó sẽ tồn tại vô số các số nguyên tố có dạng $4N+3$. $\blacksquare$



Bài toán 2. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng $4N+1$.



Làm theo phương pháp ở trên thì chúng ta sẽ chọn $n = 4 p_1 p_2 \dots p_k + 1$ và tìm cách chứng minh rằng $n$ sẽ có ước số nguyên tố có dạng $4N+1$. Tuy nhiên nhìn kỹ ra thì cách chứng minh này không ổn. Đó là vì tích của hai số có dạng $4N+3$ là số có dạng $4N+1$. Do đó có khả năng là $n$ là tích của hai số nguyên tố có dạng $4N+3$ và vì vậy $n$ sẽ không có ước số nguyên tố nào có dạng $4N+1$. Chúng ta phải tìm cách giải khác.

Chúng ta sẽ dùng $n = 4 p_1^2 p_2^2 \dots p_k^2 + 1$. Để chứng minh $n$ có ước số nguyên tố có dạng $4N+1$, chúng ta sẽ dùng bổ đề sau.


Bổ đề. Với mọi số tự nhiên $x$ thì $x^2 + 1$ không có ước nguyên tố có dạng $4N+3$.


Để chứng minh bổ đề này, chúng ta sẽ sử dụng Định lý nhỏ Fermat. Các bạn có thể đọc thêm về Định lý nhỏ Fermat ở đây: "modulo - Phần 5".

Theo định lý nhỏ Fermat thì với mọi số nguyên tố $p$ và với mọi số nguyên $a$ không chia hết cho $p$, $$a^{p-1} = 1 \pmod{p}.$$

Bây giờ chúng ta chứng minh bổ đề theo phương pháp phản chứng. Đó là, giả sử như $x^2+1$ có một ước số nguyên tố $p=4N+3$. Tức là $$x^2 = -1 \pmod{p}.$$ Từ đó chúng ta có $$x^{4N+2} = (x^2)^{2N+1} = (-1)^{2N+1} = -1 \pmod{p}.$$

Nhưng theo định lý nhỏ Fermat thì $$x^{4N+2} = 1 \pmod{p}.$$

Vậy $1=-1 \pmod{p}$, hay $2=0 \pmod{p}$. Đây là điều vô lý. Cho nên bổ đề đã được chứng minh. $\blacksquare$



Lời giải bài toán 2. Để chứng minh rằng tồn tại vô số các số nguyên tố có dạng $4N+1$, chúng ta sẽ chứng minh rằng, với mọi dãy số nguyên tố $p_1$, $p_2$, ..., $p_k$ có dạng $4N+1$, sẽ tồn tại một số nguyên tố khác cũng có dạng $4N+1$ và không nằm trong dãy số nguyên tố này.

Thực vậy, lấy $n = 4 p_1^2 p_2^2 \dots p_k^2 + 1$.

Vì $n$ có dạng $x^2+1$, nên theo bổ đề trên mà chúng ta vừa chứng minh, thì $n$ không có ước số nguyên tố có dạng $4N+3$. Vì $n$ là số lẻ nên toàn bộ các ước số nguyên tố của $n$ sẽ có dạng $4N+1$. Chúng ta lại dễ dàng thấy rằng không một số $p_i$ nào trong dãy số trên là ước số của $n$. Vì vậy chúng ta đã tìm được những số nguyên tố mới có dạng $4N+1$.

Tóm tại, cứ lấy bất kỳ một dãy số hữu hạn các số nguyên tố có dạng $4N+1$ thì chúng ta lại tìm được một số nguyên tố mới cũng dạng $4N+1$, do đó sẽ có vô hạn các số nguyên tố có dạng $4N+1$.


Chúng ta tạm dừng ở đây. Chỉ xin lưu ý là hai bài toán ở trên là hai trường hợp đặc biệt của một định lý tổng quát. Định lý này gọi là định lý Dirichlet về cấp số cọng. Định lý Dirichlet về cấp số cọng phát biểu như sau: nếu $a$ và $b$ là hai số nguyên tố cùng nhau thì sẽ tồn tại vô số các số nguyên tố có dạng $aN+b$.

Hẹn gặp lại các bạn ở bài sau.



Bài tập về nhà.

1. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng $6N+1$.

2. Chứng minh rằng tồn tại vô số các số nguyên tố có dạng $6N+5$.

3. Thử chọn vài giá trị khác cho $a$ và $b$ rồi chứng minh rằng tồn tại vô số các số nguyên tố có dạng $aN+b$.