Định lí cơ bản của số học

Định lí cơ bản của số học khẳng định rằng mọi số tự nhiên lớn hơn 1 đều phân tích được thành tích các số nguyên tố, và cách phân tích đó là duy nhất. Chẳng hạn, số 15 phân tích được thành tích của 2 số nguyên tố 3 · 5, số 30 thành tích của 3 số nguyên tố 2 · 3 · 5, còn số 16 thành tích của 4 số nguyên tố 2 · 2 · 2 · 2. Cách viết một số thành tích như vậy gọi là phân tích ra thừa số nguyên tố. Ta nói: số 10 phân tích ra thừa số nguyên tố là 2 · 5.

Các số nguyên tố có cách phân tích đơn giản nhất, vì chúng không cần phân tích thêm. Số 7 phân tích ra thừa số nguyên tố đơn giản là 7.

Phân tích một số ra thừa số nguyên tố

Nội dung của định lí cơ bản của số học

Định lí cơ bản của số học khẳng định hai điều:

• mọi số tự nhiên lớn hơn 1 đều phân tích được ra thừa số nguyên tố,
• mỗi số chỉ có đúng một cách phân tích ra thừa số nguyên tố.

Ta sẽ chứng minh rằng điều này đúng.

Chứng minh sự tồn tại

Trước hết ta chứng minh rằng mọi số tự nhiên lớn hơn 1 đều có ít nhất một cách phân tích ra thừa số nguyên tố. Ta dùng phương pháp quy nạp toán học. Bước cơ sở: số tự nhiên nhỏ nhất lớn hơn 1, tức là số 2, là số nguyên tố.

Bây giờ ta chứng minh rằng nếu mọi số trong dãy 2, …, n đều phân tích được ra thừa số nguyên tố, thì khi thêm số n + 1 vào dãy, số mới này cũng phân tích được ra thừa số nguyên tố. Trước hết ta xem một ví dụ.

Lúc đầu dãy 2, …, n hơi đặc biệt vì chỉ có một số là số 2. Ta khẳng định rằng khi thêm vào dãy số n + 1, tức là số 3, thì số này phân tích được ra thừa số nguyên tố. Vì 3 là số nguyên tố nên hiển nhiên nó có cách phân tích: chính là số 3.

Bây giờ dãy 2, …, n có hai số hạng: 2, 3. Ta thêm số 4 vào dãy. Số 4 không phải là số nguyên tố, nên nó phải viết được thành tích của hai số tự nhiên khác lớn hơn 1 nhưng nhỏ hơn 4. Mà tất cả các số như vậy đều nằm trong dãy của ta! Và dãy này chỉ gồm các số phân tích được ra thừa số nguyên tố! Do đó số 4 cũng phân tích được ra thừa số nguyên tố: 2 · 2.

Trở lại chứng minh tổng quát. Số 2 là số nguyên tố nên phân tích được ra thừa số nguyên tố. Giả sử mọi số trong dãy 2, …, n đều phân tích được ra thừa số nguyên tố, đây là giả thiết quy nạp. Khi đó số n + 1 hoặc là số nguyên tố, nên hiển nhiên phân tích được, hoặc là hợp số. Trong trường hợp thứ hai phải tồn tại hai số a, b sao cho

$$n+1=a\cdot b$$

trong đó hai số tự nhiên này tất nhiên nhỏ hơn n + 1 và lớn hơn 1:

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

Như vậy các số a, b phải thuộc dãy 2, …, n. Mà theo giả thiết quy nạp, mọi số trong dãy này đều phân tích được ra thừa số nguyên tố, tức là ta viết được

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

trong đó mọi p_i và q_j đều là số nguyên tố, và p₁ · p₂ · … · p_i, q₁ · q₂ · … · q_j là cách phân tích ra thừa số nguyên tố của hai số đó. Vì n + 1 = a · b nên

$$\begin{array}{rcl}n+1& =& a\cdot b\\ & =& p_1\cdot p_2\cdot \dots \cdot p_i\cdot q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Vậy số n + 1 là tích của các số nguyên tố p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, tức là số n + 1 mới thêm vào cũng phân tích được ra thừa số nguyên tố. Do đó mọi số tự nhiên lớn hơn 1 đều có ít nhất một cách phân tích ra thừa số nguyên tố.

Chứng minh tính duy nhất

Bây giờ ta chứng minh rằng không có số tự nhiên lớn hơn 1 nào có nhiều hơn một cách phân tích ra thừa số nguyên tố. Ta dùng phương pháp chứng minh phản chứng. Giả sử định lí sai, tức là tồn tại số tự nhiên n lớn hơn 1 có hai cách phân tích ra thừa số nguyên tố khác nhau:

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Đồng thời giả sử rằng trong tất cả các số có nhiều cách phân tích ra thừa số nguyên tố, n là số nhỏ nhất. Nghĩa là không có số tự nhiên nhỏ hơn nào có nhiều hơn một cách phân tích. Vì q₁ là một ước nguyên tố của n nên tích p₁ · p₂ · … · p_i cũng chia hết cho q₁.

Tiếp theo ta dùng bổ đề Euclid. Bổ đề này nói rằng nếu tích của hai số nguyên a · b chia hết cho số nguyên tố p thì ít nhất một trong hai số a, b chia hết cho p. Ví dụ: số 84 chia hết cho số nguyên tố 3. Số 84 viết được thành tích 12 · 7. Bổ đề Euclid nói rằng ít nhất một trong hai số 12 và 7 chia hết cho 3; ở đây đó là số 12.

Theo bổ đề này, vì tích p₁ · p₂ · … · p_i chia hết cho q₁ nên ít nhất một trong các số p₁, p₂, …, p_i chia hết cho q₁. Không mất tính tổng quát, giả sử p₁ chia hết cho q₁. Nhưng p₁ cũng là số nguyên tố. Khi nào một số nguyên tố chia hết cho một số nguyên tố khác? Chẳng hạn, số nguyên tố nào chia hết cho số nguyên tố 7? Chỉ có chính số 7. Số 7 không thể là ước của một số nguyên tố khác, vì khi đó số kia không còn là số nguyên tố. Do đó p₁ = q₁.

Như vậy hai cách phân tích có chung một số nguyên tố: p₁, cũng chính là q₁. Ta chia hai đẳng thức lần lượt cho p₁ và q₁:

$$\begin{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

Vì p₁ = q₁ nên vế trái của hai đẳng thức bằng nhau; gọi số đó là m. Ta có

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

Ở vế phải ta chỉ việc rút gọn phân số:

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

Số m chắc chắn là số tự nhiên nhỏ hơn n, vì m có được khi chia n cho một thừa số nguyên tố của nó. Nhưng vế phải của cả hai đẳng thức đều là cách phân tích ra thừa số nguyên tố của m. Như vậy ta đã tìm được số m nhỏ hơn n cũng có hai cách phân tích ra thừa số nguyên tố khác nhau. Điều này mâu thuẫn với giả thiết rằng n là số nhỏ nhất có nhiều hơn một cách phân tích.

Vậy chỉ có thể là không tồn tại “số nhỏ nhất có nhiều hơn một cách phân tích ra thừa số nguyên tố”. Mà không tồn tại số nhỏ nhất như vậy nghĩa là không tồn tại số nào có nhiều cách phân tích: mọi số nguyên lớn hơn 1 đều có đúng một cách phân tích ra thừa số nguyên tố.