Bạn sẽ học được gì
- Dùng thuật toán Euclid mở rộng để tính ước chung lớn nhất, hệ số Bézout và nghịch đảo modulo
- Chứng minh định lý cơ bản của số học và các kết quả về sự phân bố số nguyên tố ở mức sơ cấp
- Giải phương trình và hệ phương trình đồng dư bằng định lý phần dư Trung Hoa
- Áp dụng định lý Fermat nhỏ, định lý Euler và căn nguyên thủy để tính lũy thừa modulo và kiểm tra nguyên tố
- Giải thích và cài đặt các hệ mật mã Diffie–Hellman và RSA, chỉ ra điểm yếu khi chọn tham số không an toàn
- Xác định một số có phải thặng dư bậc hai hay không bằng ký hiệu Legendre và luật thuận nghịch bậc hai
- Khai triển liên phân số của số hữu tỉ và số vô tỉ bậc hai, áp dụng vào phương trình Pell và bài toán tổng hai bình phương
Nên học trước
Giới thiệu
Lý thuyết số nghiên cứu các số nguyên: chia hết, số nguyên tố, đồng dư và các phương trình nghiệm nguyên. Đây là một trong những ngành cổ xưa nhất của toán học — thuật toán Euclid đã hơn hai nghìn năm tuổi — nhưng cũng là một trong những ngành ứng dụng nhiều nhất hôm nay: mỗi lần bạn mở một trang web qua HTTPS, trình duyệt đang thực hiện phép lũy thừa modulo và các thuật toán số học trên những số nguyên hàng trăm chữ số. Chủ đề này tương ứng với MIT 18.781 Theory of Numbers, Berkeley Math 115 và học phần Số học ở các khoa Toán Việt Nam.
Ba trụ cột
- Chia hết và số nguyên tố. Thuật toán Euclid (và dạng mở rộng) tính ước chung lớn nhất cùng các hệ số Bézout; từ đó suy ra định lý cơ bản của số học: mọi số nguyên lớn hơn 1 phân tích duy nhất thành tích các số nguyên tố. Có vô hạn số nguyên tố, và định lý số nguyên tố mô tả mật độ của chúng.
- Đồng dư. Viết a ≡ b (mod n) nghĩa là n chia hết a − b; các lớp đồng dư tạo thành vành ℤ/nℤ. Các kết quả nền tảng: định lý phần dư Trung Hoa (giải hệ đồng dư với mô-đun nguyên tố cùng nhau), định lý Fermat nhỏ aᵖ⁻¹ ≡ 1 (mod p), định lý Euler với hàm φ, và căn nguyên thủy — nhóm nhân (ℤ/pℤ)* luôn xyclic.
- Thặng dư bậc hai. Phương trình x² ≡ a (mod p) có nghiệm hay không? Ký hiệu Legendre, tiêu chuẩn Euler và luật thuận nghịch bậc hai của Gauss cho phép trả lời nhanh — một định lý có hàng trăm chứng minh khác nhau.
Tính toán là một phần của môn học
Khác với nhiều môn toán thuần túy, lý thuyết số hiện đại gắn chặt với thuật toán: lũy thừa nhanh theo modulo, tìm nghịch đảo modulo bằng Euclid mở rộng, kiểm tra nguyên tố xác suất (Miller–Rabin), phân tích số nguyên. Sách chính của lộ trình — Elementary Number Theory: Primes, Congruences, and Secrets của William Stein, đọc miễn phí từ trang tác giả với sự đồng ý của Springer — minh họa mọi khái niệm bằng tính toán trên máy (Sage) và dẫn thẳng tới mật mã: trao đổi khóa Diffie–Hellman, hệ mật mã RSA và cách tấn công RSA khi chọn tham số kém. Hãy cài Python hoặc dùng SageMathCell để thử mọi ví dụ: tự nhìn thấy các quy luật trên số liệu là cách tốt nhất để hiểu vì sao cần chứng minh chúng.
Xa hơn: liên phân số và đường cong elliptic
Nửa sau của sách Stein giới thiệu liên phân số (xấp xỉ số vô tỉ tốt nhất, phương trình Pell, định lý tổng hai bình phương) và đường cong elliptic — đối tượng đứng sau chứng minh định lý Fermat lớn, thuật toán phân tích số nguyên của Lenstra và mật mã đường cong elliptic đang được dùng rộng rãi.
Nên học thế nào
- Nền tảng: kỹ năng chứng minh (quy nạp, phản chứng) từ học phần nhập môn chứng minh là đủ để bắt đầu. Nếu đã học lý thuyết nhóm, bạn sẽ thấy định lý Fermat – Euler chỉ là hệ quả của định lý Lagrange — nên học nhóm song song hoặc trước là rất có lợi.
- Luyện tập: làm nhiều bài tập nhỏ tính tay trước khi dùng máy; sách của Niven – Zuckerman – Montgomery là kho bài tập kinh điển. Sách miễn phí của Shoup phù hợp nếu bạn thiên về khoa học máy tính: mọi kết quả đều đi kèm độ phức tạp thuật toán.
- Tài liệu MIT: bài giảng và bài tập của MIT 18.781 Theory of Numbers có trên MIT OpenCourseWare để đối chiếu.
Lý thuyết số là cửa ngõ tự nhiên dẫn tới mật mã học, lý thuyết mã, đại số máy tính và lý thuyết số đại số.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Elementary Number Theory: Primes, Congruences, and Secrets
William Stein · 2009
Vì sao chọn: Sách của Springer (Undergraduate Texts in Mathematics) được đọc miễn phí hợp pháp từ trang tác giả với sự đồng ý của nhà xuất bản; được Viện Toán học Hoa Kỳ (AIM) giới thiệu. Chọn làm sách chính vì gắn lý thuyết với tính toán và mật mã, ngắn gọn, phủ đúng nội dung lộ trình.
Nên đọc: Chương 1–6 (số nguyên tố, vành ℤ/nℤ, mật mã khóa công khai, luật thuận nghịch bậc hai, liên phân số, đường cong elliptic)
An Introduction to the Theory of Numbers
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery · 1991 · Bản thứ 5
Giáo trình kinh điển (Niven – Zuckerman – Montgomery), sách tham khảo của MIT 18.781 Theory of Numbers, với kho bài tập phong phú, trình bày chặt chẽ cả phần đồng dư, thặng dư bậc hai và phương trình Diophantine. Dùng để luyện bài tập và đọc sâu hơn; sách trả phí.
A Computational Introduction to Number Theory and Algebra
Victor Shoup · 2009 · Bản thứ 2
Sách của Cambridge University Press, tác giả cho tải miễn phí bản PDF. Phù hợp với người thiên về khoa học máy tính: mọi kết quả đi kèm thuật toán và phân tích độ phức tạp.
Nên đọc: Chương 1–4 (số nguyên, đồng dư, tính toán với số lớn, thuật toán Euclid); Chương 10–12 (kiểm tra nguyên tố, logarit rời rạc, thặng dư bậc hai)
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Chia hết, số nguyên tố và thuật toán Euclid
khoảng 7 giờHọc phép chia có dư, ước chung lớn nhất, thuật toán Euclid mở rộng, định lý cơ bản của số học và sự phân bố số nguyên tố (vô hạn số nguyên tố, sàng Eratosthenes, định lý số nguyên tố). Cài đặt thuật toán Euclid mở rộng và sàng Eratosthenes, đếm số nguyên tố nhỏ hơn 10⁶ và so sánh với x/ln x.
- Đọc: Chương 1 Prime Numbers — Elementary Number Theory: Primes, Congruences, and Secrets
- Đọc: Chương 1 Basic properties of the integers; Chương 4 Euclid’s algorithm — A Computational Introduction to Number Theory and Algebra
Bước 2: Đồng dư, định lý phần dư Trung Hoa, Fermat và Euler
khoảng 8 giờHọc đồng dư, vành ℤ/nℤ, phương trình đồng dư tuyến tính, định lý phần dư Trung Hoa, hàm Euler, định lý Fermat nhỏ, định lý Euler và lũy thừa nhanh theo modulo. Giải bài toán “Hàn Tín điểm binh” (hệ ba đồng dư) bằng tay và tính 3¹⁰⁰⁰ mod 101 không cần máy.
- Đọc: Chương 2 The Ring of Integers Modulo n (mục 2.1–2.3) — Elementary Number Theory: Primes, Congruences, and Secrets
- Đọc: Chương 2 Congruences — A Computational Introduction to Number Theory and Algebra
Bước 3: Căn nguyên thủy và kiểm tra nguyên tố
khoảng 6 giờHọc cấu trúc nhóm nhân (ℤ/pℤ)*, căn nguyên thủy, logarit rời rạc, phép thử Fermat, số Carmichael và thuật toán Miller–Rabin. Cài đặt Miller–Rabin, kiểm tra với số Carmichael 561 và tìm căn nguyên thủy nhỏ nhất modulo các số nguyên tố dưới 100.
- Đọc: Chương 2 The Ring of Integers Modulo n (mục 2.4 Primality Testing, 2.5 The Structure of (ℤ/pℤ)*) — Elementary Number Theory: Primes, Congruences, and Secrets
- Đọc: Chương 10 Probabilistic primality testing; Chương 11 Finding generators and discrete logarithms in ℤp* — A Computational Introduction to Number Theory and Algebra
Bước 4: Mật mã khóa công khai: Diffie–Hellman và RSA
khoảng 6 giờHọc trao đổi khóa Diffie–Hellman, hệ mật mã RSA, chữ ký số và các tấn công RSA khi tham số yếu. Tự sinh khóa RSA với hai số nguyên tố khoảng 20 chữ số, mã hóa rồi giải mã một thông điệp, sau đó phá khóa khi p và q quá gần nhau bằng phương pháp phân tích Fermat. Đọc thêm tài liệu trên OpenER về mật mã học ứng dụng để thấy RSA được dùng ra sao trong bảo mật phần mềm.
- Đọc: Chương 3 Public-key Cryptography — Elementary Number Theory: Primes, Congruences, and Secrets
Bước 5: Thặng dư bậc hai và luật thuận nghịch bậc hai
khoảng 7 giờHọc thặng dư bậc hai, ký hiệu Legendre và Jacobi, tiêu chuẩn Euler, bổ đề Gauss, luật thuận nghịch bậc hai và thuật toán tìm căn bậc hai modulo p. Dùng luật thuận nghịch tính ký hiệu Legendre (219/383) bằng tay rồi kiểm tra lại bằng máy.
- Đọc: Chương 4 Quadratic Reciprocity — Elementary Number Theory: Primes, Congruences, and Secrets
- Đọc: Chương 12 Quadratic reciprocity and computing modular square roots — A Computational Introduction to Number Theory and Algebra
Bước 6: Liên phân số, tổng hai bình phương và đường cong elliptic
khoảng 6 giờHọc liên phân số hữu hạn và vô hạn, số vô tỉ bậc hai, phương trình Pell, định lý tổng hai bình phương; nhóm điểm trên đường cong elliptic và ứng dụng trong phân tích số nguyên và mật mã. Tìm nghiệm nhỏ nhất của x² − 13y² = 1 bằng liên phân số của √13 và cộng vài điểm trên một đường cong elliptic modulo 17. Bài giảng MIT 18.781 trên MIT OpenCourseWare là nguồn đối chiếu tốt cho bước này.
- Đọc: Chương 5 Continued Fractions; Chương 6 Elliptic Curves — Elementary Number Theory: Primes, Congruences, and Secrets
Khái niệm chính
- Thuật toán Euclid mở rộng
- Tính ƯCLN(a, b) cùng các số nguyên x, y với ax + by = ƯCLN(a, b); dùng để tìm nghịch đảo modulo trong thời gian đa thức theo số chữ số.
- Định lý cơ bản của số học
- Mọi số nguyên lớn hơn 1 phân tích được thành tích các số nguyên tố, và phân tích đó là duy nhất nếu không kể thứ tự.
- Đồng dư và vành ℤ/nℤ
- a ≡ b (mod n) khi n chia hết a − b; các lớp đồng dư modulo n tạo thành vành ℤ/nℤ, với nhóm nhân (ℤ/nℤ)* gồm các lớp nguyên tố cùng nhau với n.
- Định lý phần dư Trung Hoa
- Hệ đồng dư với các mô-đun đôi một nguyên tố cùng nhau luôn có nghiệm duy nhất modulo tích các mô-đun.
- Định lý Fermat nhỏ và định lý Euler
- aᵖ⁻¹ ≡ 1 (mod p) khi p nguyên tố không chia a; tổng quát, a^φ(n) ≡ 1 (mod n) khi ƯCLN(a, n) = 1, với φ là hàm Euler.
- Căn nguyên thủy (Primitive root)
- Phần tử sinh của nhóm nhân (ℤ/pℤ)*; luôn tồn tại với p nguyên tố, là nền của bài toán logarit rời rạc.
- Kiểm tra nguyên tố xác suất
- Các thuật toán như Miller–Rabin kiểm tra một số lớn có là số nguyên tố với xác suất sai nhỏ tùy ý, nhanh hơn nhiều so với phân tích thừa số.
- Hệ mật mã RSA
- Khóa công khai (n, e) với n = pq; mã hóa m ↦ mᵉ mod n, giải mã bằng d với ed ≡ 1 (mod φ(n)); an toàn dựa trên độ khó của phân tích n.
- Thặng dư bậc hai và ký hiệu Legendre
- a là thặng dư bậc hai modulo p nếu x² ≡ a (mod p) có nghiệm; ký hiệu Legendre (a/p) bằng 1, −1 hoặc 0 ghi nhận điều đó, và (a/p) ≡ a^((p−1)/2) (mod p) theo tiêu chuẩn Euler.
- Luật thuận nghịch bậc hai
- Với p, q là hai số nguyên tố lẻ khác nhau, (p/q)(q/p) = (−1)^((p−1)(q−1)/4); cho phép tính ký hiệu Legendre nhanh như thuật toán Euclid.
- Liên phân số
- Biểu diễn số thực bằng dãy phân số lồng nhau; các giản phân cho xấp xỉ hữu tỉ tốt nhất và dùng để giải phương trình Pell x² − dy² = 1.
- Đường cong elliptic
- Đường cong y² = x³ + ax + b với 4a³ + 27b² ≠ 0; các điểm hữu tỉ hoặc modulo p, thêm điểm vô cực O, tạo thành một nhóm abel; dùng trong phân tích số nguyên (Lenstra) và mật mã ECC.
Học xong để làm gì
- Mật mã khóa công khai: RSA, trao đổi khóa Diffie–Hellman, chữ ký số và mật mã đường cong elliptic trong HTTPS, ví điện tử, blockchain
- Sinh số giả ngẫu nhiên và hàm băm dựa trên số học modulo
- Mã kiểm tra lỗi: số ISBN, số tài khoản ngân hàng (IBAN), mã vạch dùng đồng dư để phát hiện lỗi nhập liệu
- Thuật toán số học máy tính: nhân số lớn, tính toán theo modulo nhiều số nguyên tố (định lý phần dư Trung Hoa) trong đại số máy tính
- Toán thi Olympic: số học là một trong bốn mảng chính của các kỳ thi học sinh giỏi và IMO
Câu hỏi thường gặp
Lý thuyết số ở đây khác gì số học phổ thông chuyên?
Nhiều kết quả trùng nhau (đồng dư, Fermat, Euler), nhưng ở đây trọng tâm là chứng minh có hệ thống, cấu trúc nhóm – vành phía sau và thuật toán hiệu quả, dẫn tới mật mã và đường cong elliptic.
Có cần học lý thuyết nhóm trước không?
Không bắt buộc, chỉ cần kỹ năng chứng minh. Nhưng học nhóm trước hoặc song song giúp nhiều định lý (Fermat, Euler, căn nguyên thủy) trở thành hệ quả tự nhiên của định lý Lagrange.
Tại sao sách chính lại dùng máy tính nhiều như vậy?
Vì lý thuyết số hiện đại gắn với thuật toán: tính toán giúp phát hiện quy luật, kiểm tra giả thuyết và hiểu vì sao RSA an toàn khi số đủ lớn nhưng yếu khi chọn tham số kém.
Học xong có đủ để làm mật mã học không?
Đủ nền toán cho mật mã khóa công khai cơ bản; để làm mật mã thực tế cần thêm trường hữu hạn, xác suất, độ phức tạp tính toán và các chuẩn an toàn (padding, sinh khóa).

