Số nguyên tố

Đó là lý do số nguyên tố được gọi là 'nguyên tử' của số học: mỗi số chỉ có đúng một công thức để tạo ra, nên biết các số nguyên tố và số mũ của chúng là biết mọi thứ về ước của số đó.

Sự tồn tại (bằng phản ví dụ nhỏ nhất): Giả sử có số nguyên $n > 1$ không viết được thành tích các số nguyên tố, và gọi $m > 1$ là số nhỏ nhất như vậy. Vì mỗi số nguyên tố đã là tích của một số nguyên tố nên $m$ phải là hợp số, tức là $m = a b$ với các số nguyên thỏa $1 < a, b < m$. Do tính nhỏ nhất của $m$, cả $a$ và $b$ đều là tích các số nguyên tố, suy ra tích $m = a b$ cũng là tích các số nguyên tố—mâu thuẫn.

Bổ đề Euclid: Giả sử số nguyên tố $p$ thỏa $p \mid a b$ và $p \nmid a$. Vì $p$ nguyên tố và $p \nmid a$ nên $\gcd(p, a) = 1$. Theo đẳng thức Bézout, tồn tại các số nguyên $x, y$ sao cho $p x + a y = 1$. Nhân hai vế với $b$ ta được $p(b x) + (a b)y = b$; vì $p$ chia hết cả $p(b x)$ lẫn $a b$ nên $p$ chia hết vế phải, suy ra $p \mid b$.

Tính duy nhất: Giả sử phản chứng có số nguyên phân tích được theo hai cách khác nhau, và gọi $n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$ (sắp thứ tự $p_1 \le \cdots \le p_r$ và $q_1 \le \cdots \le q_s$) là số nhỏ nhất như thế. Vì $p_1 \mid q_1 q_2 \cdots q_s$, áp dụng liên tiếp bổ đề Euclid suy ra $p_1$ chia hết một số nguyên tố $q_j$ nào đó, buộc $p_1 = q_j \ge q_1$. Do tính đối xứng ta cũng có $q_1 \ge p_1$, vậy $p_1 = q_1$. Chia cả hai vế cho $p_1$ cho ta số nguyên nhỏ hơn $n / p_1 < n$ có hai phân tích khác nhau, mâu thuẫn với tính nhỏ nhất của $n$.

Lập luận của Euclid (khoảng 300 TCN): giả sử chỉ có hữu hạn số nguyên tố $p_1, p_2, \ldots, p_k$. Nhân tất cả lại rồi cộng 1: $N = p_1 p_2 \cdots p_k + 1$. Chia $N$ cho bất kỳ $p_i$ nào cũng dư 1, nên không $p_i$ nào chia hết $N$. Nhưng $N$ phải có một ước nguyên tố nào đó (theo định lý cơ bản của số học) — một số nguyên tố không có trong danh sách. Vậy danh sách ban đầu chưa bao giờ đầy đủ.

Bước 1 (Thiết lập số Euclid): Cho $\{p_1, p_2, \dots, p_k\}$ là một tập hợp hữu hạn các số nguyên tố bất kỳ. Lập số nguyên $N = p_1 p_2 \cdots p_k + 1$ bằng cách nhân tất cả các số nguyên tố trong danh sách rồi cộng thêm $1$. Vì $p_1 \ge 2$ nên $N \ge 2 + 1 = 3 > 1$.

Bước 2 (Sự tồn tại ước nguyên tố): Theo định lý cơ bản của số học, mọi số nguyên $N > 1$ đều có ít nhất một ước nguyên tố $q$, tức là $q \mid N$ (trong đó $q = N$ nếu bản thân $N$ là số nguyên tố, hoặc $q < N$ nếu $N$ là hợp số).

**Bước 3 (Chứng minh $q$ là số nguyên tố mới):** Giả sử phản chứng $q = p_i$ với một chỉ số $i$ nào đó. Khi đó $q \mid p_1 p_2 \cdots p_k$, mà $q \mid N$ nên số nguyên tố $q$ phải chia hết hiệu của chúng: $q \mid (N - p_1 p_2 \cdots p_k) = 1$. Điều này vô lý vì mọi số nguyên tố đều thỏa $q \ge 2$. Vậy $q \notin \{p_1, p_2, \dots, p_k\}$, chứng tỏ không một danh sách hữu hạn nào chứa hết mọi số nguyên tố.