Hiểu kết quả phân tích thừa số nguyên tố
Bảng dưới đây trình bày phân tích thừa số nguyên tố của một vài số quen thuộc để minh họa cách hoạt động của ký hiệu lũy thừa.
| Số | Phân tích thừa số nguyên tố | Số lượng ước |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17 (một số nguyên tố) | 17 (chính nó, số mũ 1) | 2 |
| 1.024 | 2¹⁰ | 11 |
- Phân tích của chính một số nguyên tố đơn giản là bản thân nó với số mũ 1, và nó luôn có đúng 2 ước: 1 và chính nó. Đây chính xác là tính chất định nghĩa của số nguyên tố.
- Số 1 không phải số nguyên tố cũng không phải hợp số và không có phân tích thừa số nguyên tố (nó là tích rỗng); máy tính này yêu cầu dữ liệu nhập từ 2 trở lên.
- Với những số rất lớn, phép chia thử trở nên chậm về mặt tính toán vì nó phải thử các số nguyên tố ứng viên đến tận căn bậc hai của số đó — đây là lý do việc phân tích những số cực lớn (hàng trăm chữ số) là bài toán khó về mặt tính toán và tạo nên cơ sở bảo mật của mã hóa RSA.
Phân tích thừa số nguyên tố là gì?
Phân tích thừa số nguyên tố là quá trình tách một số nguyên thành tập hợp các số nguyên tố mà khi nhân với nhau sẽ tạo ra chính số đó. Số nguyên tố là số nguyên lớn hơn 1 có đúng hai ước dương: 1 và chính nó (2, 3, 5, 7, 11, 13, ... là những số nguyên tố đầu tiên). Ví dụ, 360 phân tích thành 2³ × 3² × 5, nghĩa là 360 = 2×2×2×3×3×5.
Định lý cơ bản của số học, một trong những kết quả nền tảng của lý thuyết số, bảo đảm rằng mọi số nguyên lớn hơn 1 đều có một và chỉ một cách phân tích thừa số nguyên tố, không kể thứ tự viết các thừa số. Chính tính duy nhất này khiến phân tích thừa số nguyên tố trở thành một phép toán được xác định rõ ràng và đáng tin cậy, chứ không phải một trong nhiều đáp án đều hợp lệ như nhau.
Phân tích thừa số nguyên tố là nền tảng của những lĩnh vực cốt lõi trong toán học và khoa học máy tính: nó được dùng để tìm ước chung lớn nhất và bội chung nhỏ nhất của các số, để xác định mọi ước của một số, để rút gọn phân số và căn thức, và — với những số rất lớn — độ khó tính toán của nó chính là cơ sở toán học của mật mã khóa công khai RSA, vốn dựa trên thực tế rằng phân tích một số lớn khó hơn rất nhiều so với nhân các thừa số của nó với nhau.
Cách dùng máy tính phân tích thừa số nguyên tố này
- Nhập một số nguyên từ 2 trở lên (tối đa 1 nghìn tỷ).
- Máy tính chia liên tiếp cho thừa số nguyên tố nhỏ nhất có thể cho đến khi chỉ còn lại 1, theo phương pháp chia thử tiêu chuẩn.
- Đọc phân tích thừa số nguyên tố ở dạng lũy thừa (ví dụ 2³ × 3² × 5), trong đó mỗi số mũ cho biết thừa số nguyên tố đó xuất hiện bao nhiêu lần trong tích.
- Xem tổng số ước dương mà số đó có, và tổng của tất cả các ước ấy — cả hai đều được suy ra trực tiếp từ phân tích thừa số nguyên tố.
Cách tính phân tích thừa số nguyên tố, số ước và tổng các ước
Phép chia thử tìm ra phân tích thừa số nguyên tố bằng cách thử lần lượt các số nguyên tố ứng viên, bắt đầu từ 2, chia số đó cho từng số nguyên tố nhiều lần nhất có thể mà vẫn chia hết, rồi chuyển sang ứng viên tiếp theo. Ví dụ minh họa: 360 ÷ 2 = 180, ÷2 = 90, ÷2 = 45 (không còn chia hết cho 2 nữa, nên 2 xuất hiện 3 lần); 45 ÷ 3 = 15, ÷3 = 5 (không còn chia hết cho 3 nữa, nên 3 xuất hiện 2 lần); 5 ÷ 5 = 1 (5 xuất hiện một lần). Kết quả: 360 = 2³ × 3² × 5.
Một khi đã biết phân tích thừa số nguyên tố n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ, tổng số ước dương (kể cả 1 và chính n) được tìm bằng cách cộng 1 vào từng số mũ rồi nhân các kết quả lại: (e₁+1) × (e₂+1) × ... × (eₖ+1). Ví dụ minh họa với 360 = 2³ × 3² × 5¹: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 ước.
Tổng tất cả các ước được tìm bằng công thức tổng ước có tính nhân: với mỗi lũy thừa nguyên tố p^e trong phân tích, phần đóng góp của nó là (p^(e+1) − 1) ÷ (p − 1) — tổng của một cấp số nhân 1 + p + p² + ... + p^e — và các phần đóng góp này được nhân với nhau qua tất cả các thừa số nguyên tố. Ví dụ minh họa với 360: số hạng 2³ đóng góp (2⁴−1)/(2−1) = 15, số hạng 3² đóng góp (3³−1)/(3−1) = 13, và số hạng 5¹ đóng góp (5²−1)/(5−1) = 6; nhân 15 × 13 × 6 = 1170, tức tổng của cả 24 ước của 360.
Những sai lầm thường gặp
- Dừng phân tích quá sớm trước khi về đến 1 — mọi thừa số tìm được đều phải được chia hết ra hoàn toàn (không chỉ một lần) trước khi chuyển sang số nguyên tố ứng viên tiếp theo.
- Coi 1 là số nguyên tố — theo quy ước toán học hiện đại, 1 không phải số nguyên tố cũng không phải hợp số, và việc đưa nó vào một phân tích sẽ vi phạm tính duy nhất mà định lý cơ bản của số học bảo đảm.
- Quên rằng số mũ (chứ không chỉ cơ số nguyên tố) mới quan trọng khi đếm ước — công thức số lượng ước dùng (số mũ + 1) cho mỗi số nguyên tố, chứ không chỉ đếm số lượng các số nguyên tố phân biệt.
- Cho rằng mọi số lớn đều có thừa số nguyên tố nhỏ — nhiều số lớn (đặc biệt là tích của hai số nguyên tố lớn) hoàn toàn không có thừa số nhỏ nào, và đó chính là tính chất khiến chúng hữu ích cho các ứng dụng mật mã.
Câu hỏi thường gặp
Làm thế nào để tìm phân tích thừa số nguyên tố của một số?
Chia số đó liên tiếp cho số nguyên tố nhỏ nhất chia hết nó, tiếp tục với chính số nguyên tố ấy cho đến khi không còn chia hết, rồi chuyển sang số nguyên tố tiếp theo, và lặp lại cho đến khi thương còn lại bằng 1. Với 360: chia cho 2 ba lần (360→180→90→45), rồi chia cho 3 hai lần (45→15→5), rồi chia cho 5 một lần (5→1), cho ra 360 = 2³ × 3² × 5.
Một số có bao nhiêu ước?
Cộng 1 vào từng số mũ trong phân tích thừa số nguyên tố rồi nhân các kết quả lại với nhau. Với 360 = 2³ × 3² × 5¹, số lượng ước là (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24. Con số này tính tất cả các ước dương, kể cả 1 và chính số đó.
Định lý cơ bản của số học là gì?
Định lý cơ bản của số học phát biểu rằng 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ố theo đúng một cách duy nhất, ngoại trừ thứ tự liệt kê các số nguyên tố. Chính tính duy nhất này khiến phân tích thừa số nguyên tố là một phép toán được xác định rõ ràng chứ không phải một trong nhiều đáp án đều hợp lệ như nhau, và nó là nền tảng của phần lớn lý thuyết số.
Số 1 có phải là số nguyên tố không?
Không. Theo quy ước toán học hiện đại, 1 không phải số nguyên tố cũng không phải hợp số. Số nguyên tố được định nghĩa là có đúng hai ước dương phân biệt (1 và chính nó); số 1 chỉ có một ước dương (chính nó), nên nó không thỏa mãn định nghĩa. Việc loại 1 khỏi các số nguyên tố cũng là cần thiết để định lý cơ bản của số học đúng, vì nếu không thì một số có thể được 'phân tích' với bao nhiêu thừa số 1 thêm vào cũng được.
Vì sao phân tích thừa số nguyên tố lại quan trọng với mã hóa?
Mật mã khóa công khai RSA hiện đại dựa trên thực tế rằng nhân hai số nguyên tố lớn với nhau thì dễ về mặt tính toán, nhưng phân tích tích lớn đó ngược lại thành các số nguyên tố ban đầu thì rất khó về mặt tính toán với các thuật toán cổ điển hiện được biết đến. Sự bất đối xứng này — dễ nhân, khó phân tích — cho phép chia sẻ công khai khóa công khai (tích số) trong khi khóa riêng (các thừa số nguyên tố) vẫn giữ bí mật và thực tế là không thể khôi phục trong khung thời gian khả thi nếu các số nguyên tố đủ lớn.
Làm thế nào để tìm tổng tất cả các ước của một số?
Dùng phân tích thừa số nguyên tố n = p₁^e₁ × p₂^e₂ × ..., tính (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1) cho mỗi thừa số nguyên tố rồi nhân các kết quả lại. Với 360 = 2³ × 3² × 5: số hạng 2³ cho (2⁴−1)/(2−1)=15, số hạng 3² cho (3³−1)/(3−1)=13, và số hạng 5¹ cho (5²−1)/(5−1)=6; nhân 15×13×6 = 1170, tức tổng tất cả các ước của 360.
Tài liệu tham khảo
- Rosen KH. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2010. (Fundamental theorem of arithmetic, divisor functions.)
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
- Rivest RL, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1978; 21(2): 120–126. (RSA and the factoring problem.)