Tính chia hết và số nguyên tố

Tính chia hết, ước số chung lớn nhất và các số nguyên tố tạo thành nền tảng của lý thuyết số: mọi số nguyên đều được xây dựng theo phép nhân từ các số nguyên tố, và cách nó được xây dựng chi phối gần như mọi kết quả sau này.

Definition

Một số nguyên a chia hết cho b nếu b bằng a nhân với một số nguyên nào đó; một số nguyên tố là một số nguyên lớn hơn một mà các ước số dương duy nhất của nó là một và chính nó. Tính chia hết và số nguyên tố liên quan đến sự phân tích nhân tử của các số nguyên và các khối xây dựng không thể rút gọn của sự phân tích đó.

Scope

Chủ đề này đề cập đến quan hệ chia hết trên các số nguyên, thuật toán chia, ước số chung lớn nhất và bội số chung nhỏ nhất được tính toán thông qua thuật toán Euclid, đồng nhất thức Bezout, bổ đề Euclid, định lý cơ bản của số học, và lý thuyết sơ cấp về số nguyên tố — tính vô hạn, các phương pháp phỏng đoán phân bố, và tính nguyên tố.

Core questions

• Thuật toán Euclid tính ước số chung lớn nhất và cho ra đồng nhất thức Bezout như thế nào?
• Tại sao bổ đề Euclid lại buộc sự phân tích thành các số nguyên tố phải là duy nhất?
• Làm thế nào để chứng minh có vô số số nguyên tố, và những chứng minh như vậy tiết lộ điều gì?
• Các số nguyên tố được phân bố như thế nào trong các số nguyên, và tính nguyên tố được xác định trong thực tế ra sao?

Key theories

Thuật toán chia và thuật toán Euclid

Bất kỳ số nguyên nào chia cho một số nguyên dương đều cho một thương và số dư duy nhất; lặp lại quá trình này sẽ cho ước số chung lớn nhất và, thông qua phép thế ngược, các số nguyên biểu thị nó dưới dạng tổ hợp tuyến tính (đồng nhất thức Bezout).

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

Mọi số nguyên lớn hơn một đều là tích của các số nguyên tố là duy nhất theo thứ tự; bổ đề Euclid (một số nguyên tố chia hết một tích thì chia hết một thừa số) là bước quan trọng.

Tính vô hạn của các số nguyên tố

Lập luận cổ điển của Euclid cho thấy không có danh sách hữu hạn các số nguyên tố nào là đầy đủ; công thức tích Euler cho hàm zeta đưa ra một chứng minh giải tích và định lượng mật độ số nguyên tố thông qua sự phân kỳ của tổng các nghịch đảo của các số nguyên tố.

Clinical relevance

Phân tích nhân tử nhanh và kiểm tra tính nguyên tố là nền tảng của mật mã học: bảo mật RSA dựa trên độ khó của việc phân tích các tích lớn của hai số nguyên tố, trong khi các kiểm tra tính nguyên tố hiệu quả (như Miller-Rabin) giúp việc tạo khóa trở nên khả thi.

History

Bộ sách Cơ sở (Elements) của Euclid (khoảng năm 300 TCN) đã chứa thuật toán Euclid, bổ đề Euclid và chứng minh rằng các số nguyên tố là vô hạn. Sàng Eratosthenes cung cấp phương pháp có hệ thống đầu tiên để liệt kê các số nguyên tố, và các công trình của Euler, Legendre và Gauss vào thế kỷ 18 và 19 đã định hình lại sự phân bố số nguyên tố thành một vấn đề định lượng.

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

Một có phải là số nguyên tố không?

Không. Số một bị loại trừ theo định nghĩa để sự phân tích thừa số nguyên tố là duy nhất; nếu số một được coi là số nguyên tố, mọi số sẽ có vô số cách phân tích thừa số.

Đồng nhất thức Bezout được dùng để làm gì?

Nó phát biểu rằng ước số chung lớn nhất của hai số nguyên là một tổ hợp tuyến tính nguyên của chúng, đây là cơ sở để tính toán các nghịch đảo modulo và giải các phương trình Diophantine tuyến tính.