Vì sao có vô hạn số nguyên tố?

Những viên gạch của số học

Số nguyên tố là số nguyên lớn hơn

1

chỉ có hai ước dương:

1

và chính nó. Dãy số bắt đầu bằng

2, 3, 5, 7, 11, 13, \dots

Định lý của Euclid

Định lý 1. Có vô hạn số nguyên tố.

Chứng minh. Giả sử chỉ có hữu hạn số nguyên tố $p_{1}, \dots, p_{n}$ . Xét số $N = p_{1} p_{2} \dots p_{n} + 1$ . Mọi $p_{i}$ đều không chia hết $N$ , vì phép chia luôn dư $1$ . Nhưng $N > 1$ phải có ít nhất một ước nguyên tố, và ước này không thuộc danh sách đã cho. Mâu thuẫn.

□

Một điều dễ nhầm

Số

N

trong chứng minh không nhất thiết là số nguyên tố. Ta chỉ cần một ước nguyên tố mới.

Ví dụ 2. $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ .

Bài tập

Bài tập 3. Chứng minh có vô hạn số nguyên tố dạng $4 k + 3$ . Gợi ý: giả sử danh sách hữu hạn và xét số bằng bốn lần tích của chúng trừ một.

Định lý của Euclid

Định lý 1. Có vô hạn số nguyên tố.

□