Lý thuyết số — Số nguyên tố, tính chia hết và số học mô-đun

Lý thuyết số là ngành nghiên cứu về các số nguyên. Nếu bạn muốn hiểu số nguyên tố, tính chia hết hay số học mô-đun, thì bạn đang tiếp cận đúng phần cốt lõi của lý thuyết số.

Số nguyên tố là số nguyên lớn hơn $1$ và có đúng hai ước dương: $1$ và chính nó. Tính chia hết xét xem một số nguyên có chia một số nguyên khác mà không dư hay không. Số học mô-đun theo dõi các số dư, vì vậy nó thường được gọi là số học đồng hồ.

Lý thuyết số bao gồm những gì

Ba ý tưởng này gắn kết với nhau:

• Số nguyên tố là những viên gạch cơ bản cấu tạo nên các số nguyên dương.
• Tính chia hết cho biết khi nào một số nguyên chia hết một số nguyên khác.
• Số học mô-đun chuyển các câu hỏi về chia hết thành các câu hỏi về số dư.

Ví dụ, nói rằng "$a$ chia hết cho $n$" cũng chính là nói rằng

$$a \equiv 0 \pmod n$$

Vì thế, một bài toán về tính chia hết thường có thể được viết lại thành một bài toán về số dư.

Số nguyên tố: Những khối xây dựng cơ bản

Các số nguyên tố bắt đầu là

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

Số $2$ là số nguyên tố chẵn duy nhất. Mọi số chẵn khác đều chia hết cho $2$, nên không thể là số nguyên tố.

Nếu một số nguyên dương lớn hơn $1$ không phải là số nguyên tố, thì nó được gọi là hợp số. Chẳng hạn, $21$ là hợp số vì

$$21 = 3 \cdot 7$$

Số nguyên tố quan trọng vì mọi số nguyên lớn hơn $1$ đều có thể viết thành tích của các số nguyên tố, không kể thứ tự các thừa số. Đó chính là ý tưởng đằng sau phân tích thừa số nguyên tố.

Tính chia hết: Khi một số chia đúng một số khác

Nếu $a$ và $b$ là các số nguyên với $b \ne 0$, thì "$b$ chia hết $a$" nghĩa là tồn tại một số nguyên $k$ sao cho

$$a = bk$$

Điều này được viết là

$$b \mid a$$

Ví dụ, $4 \mid 20$ vì $20 = 4 \cdot 5$. Nhưng $4 \nmid 22$ vì khi chia $22$ cho $4$ thì còn dư.

Tính chia hết là ngôn ngữ đứng sau các khái niệm ước, bội, ước chung lớn nhất và bội chung nhỏ nhất. Nó cũng giải thích các dấu hiệu quen thuộc:

• Một số chia hết cho $2$ nếu chữ số tận cùng là số chẵn.
• Một số chia hết cho $5$ nếu chữ số tận cùng là $0$ hoặc $5$.
• Một số chia hết cho $3$ nếu tổng các chữ số của nó chia hết cho $3$.

Quy tắc cuối cùng đó không phải mẹo. Nó xuất phát từ số học mô-đun.

Số học mô-đun: Làm việc với số dư

Khi hai số nguyên cho cùng một số dư khi chia cho $n$, ta nói chúng đồng dư theo mô-đun $n$. Ta viết

$$a \equiv b \pmod n$$

Điều này có nghĩa là $n$ chia hết $a-b$.

Ví dụ,

$$17 \equiv 5 \pmod{12}$$

vì $17$ và $5$ đều cho số dư $5$ khi chia cho $12$, và cũng vì $12$ chia hết $17 - 5 = 12$.

Điều này hữu ích vì bạn có thể thay một số bằng một số đồng dư đơn giản hơn. Trên đồng hồ $12$ giờ, cộng thêm $15$ giờ cho cùng kết quả như cộng thêm $3$ giờ vì

$$15 \equiv 3 \pmod{12}$$

Ví dụ có lời giải: Vì sao $231$ chia hết cho $3$?

Xét số $231$.

Trước hết, viết nó dưới dạng giá trị theo hàng:

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

Bây giờ làm việc theo mô-đun $3$. Vì

$$10 \equiv 1 \pmod 3$$

nên suy ra

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

Do đó

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

Vì $231 \equiv 0 \pmod 3$, nên số này chia hết cho $3$.

Điều này giải thích quy tắc tổng chữ số: trong hệ cơ số $10$, mỗi lũy thừa của $10$ đều đồng dư với $1$ theo mô-đun $3$, nên cả số sẽ có cùng số dư với tổng các chữ số của nó.

Và khi thực hiện phép chia, ta có

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

nên $231$ là hợp số, không phải số nguyên tố.

Những lỗi thường gặp trong lý thuyết số

Coi $1$ là số nguyên tố

$1$ không phải là số nguyên tố. Một số nguyên tố phải có đúng hai ước dương, còn $1$ chỉ có một ước.

Quên điều kiện trong tính chia hết

Mệnh đề $b \mid a$ chỉ có nghĩa khi $b \ne 0$. Không được phép chia cho $0$.

Nhầm lẫn giữa bằng nhau và đồng dư

$17 \equiv 5 \pmod{12}$ không có nghĩa là $17 = 5$. Nó có nghĩa là hiệu của chúng là một bội của $12$.

Lạm dụng các quy tắc chia hết

Một số dấu hiệu chia hết rất nhanh vì số học trong hệ cơ số $10$ khiến chúng hoạt động đẹp. Nhưng điều đó không có nghĩa là mọi ước đều có một quy tắc chữ số đơn giản.

Lý thuyết số xuất hiện ở đâu

Ở mức học đường, lý thuyết số xuất hiện trong phân tích thừa số, bài toán số dư, chứng minh chia hết và các câu hỏi kiểu đồng hồ. Nó cũng xuất hiện khi bạn rút gọn phân số, tìm ước chung hoặc giải các bài toán có chu kỳ lặp lại.

Ở mức sâu hơn, số nguyên tố và số học mô-đun còn giữ vai trò trung tâm trong mật mã học và khoa học máy tính. Bạn không cần nền tảng đó để dùng các ý tưởng này, nhưng nó giúp giải thích vì sao lý thuyết số cứ liên tục xuất hiện trong các bối cảnh ứng dụng.

Hãy tự thử một phiên bản của riêng bạn

Hãy thử lập luận tương tự với $462$. Trước tiên dùng tổng chữ số để kiểm tra tính chia hết cho $3$, rồi phân tích thừa số đủ để quyết định nó là số nguyên tố hay hợp số.

Nếu bạn muốn kiểm tra cách làm của mình, hãy giải một bài toán tương tự về chia hết hoặc số dư trong một công cụ giải toán và so sánh các bước số học mô-đun với cách làm của bạn.