Đồng dư thức là công cụ mà dân thi Olympic dùng gần như mỗi ngày trong các kỳ International Mathematical Olympiad và các cuộc thi quốc gia. Chỉ cần quen tay, những bài hỏi “số dư của lũy thừa lớn” biến thành vài dòng tính nhẩm. Nhiều bạn lớp 9 từng sợ cái tên này, nhưng ý tưởng lại rất gần gũi, giống như việc đọc giờ trên đồng hồ. Bài này đi từ khái niệm tới định lý Fermat nhỏ, rồi làm các ví dụ có lời giải.
Khái niệm đồng dư
Ta nói a đồng dư với b theo modulo m, viết a ≡ b (mod m), khi a và b có cùng số dư khi chia cho m. Cách nói tương đương là hiệu a − b chia hết cho m. Cả hai cách đều dùng được, tùy bài mà chọn cách thuận tiện hơn.
Ví dụ 17 ≡ 2 (mod 5), vì 17 − 2 = 15 chia hết cho 5. Cũng có 23 ≡ 3 (mod 5) và −1 ≡ 4 (mod 5). Đồng hồ là ví dụ quen thuộc nhất: sau 12 giờ, kim giờ quay về chỗ cũ, nên 15 giờ trùng với 3 giờ. Đó chính là tính toán theo modulo 12.
Mỗi số nguyên đồng dư với đúng một số trong tập {0, 1, …, m − 1}, gọi là số dư của nó. Nhờ vậy, ta có thể thay các số khổng lồ bằng số dư nhỏ khi tính toán. Trang đồng dư thức trên Wikipedia trình bày thêm phần lý thuyết nếu bạn muốn tham khảo.
Tính chất cơ bản
Đồng dư thức cư xử rất giống đẳng thức. Nếu a ≡ b và c ≡ d (mod m) thì a + c ≡ b + d, a − c ≡ b − d, và a · c ≡ b · d (mod m). Từ phép nhân suy ra phép lũy thừa: nếu a ≡ b thì aⁿ ≡ bⁿ (mod m) với mọi số tự nhiên n.
Với phép chia thì phải cẩn thận. Ta không được tự ý chia hai vế cho cùng một số. Chẳng hạn 6 ≡ 2 (mod 4), nhưng chia cả hai vế cho 2 được 3 và 1, mà 3 không đồng dư với 1 theo modulo 4. Việc chia chỉ an toàn khi số đem chia nguyên tố cùng nhau với m. Xem lại bài về số nguyên tố và ước chung lớn nhất sẽ giúp bạn hiểu rõ điều kiện này.
Ví dụ 1: chữ số tận cùng
Tìm chữ số tận cùng của 7²⁰²⁴. Chữ số tận cùng chính là số dư khi chia cho 10.
Ta tính 7² = 49 ≡ 9 (mod 10). Suy ra 7⁴ ≡ 9² = 81 ≡ 1 (mod 10). Số mũ 2024 chia hết cho 4, vì 2024 = 4 · 506. Vậy 7²⁰²⁴ = (7⁴)⁵⁰⁶ ≡ 1⁵⁰⁶ = 1 (mod 10). Chữ số tận cùng là 1.
Ví dụ 2: số dư của 2¹⁰⁰ chia cho 7
Ta có 2³ = 8 ≡ 1 (mod 7). Chu kỳ này rất ngắn, nên ta tách số mũ theo bội của 3. Ta có 100 = 3 · 33 + 1. Vậy 2¹⁰⁰ = (2³)³³ · 2 ≡ 1³³ · 2 = 2 (mod 7).
Số dư là 2. Cách làm tổng quát: tìm số mũ nhỏ nhất làm cho lũy thừa đồng dư với 1, rồi dựa vào chu kỳ đó. Với những số có chu kỳ dài, định lý Fermat nhỏ sẽ cho ta một chu kỳ có sẵn.
Dấu hiệu chia hết cho 9
Vì 10 ≡ 1 (mod 9), nên 10ⁿ ≡ 1 với mọi n. Một số bất kỳ khi đó đồng dư với tổng các chữ số của nó theo modulo 9. Chẳng hạn 123456 có tổng chữ số là 21, mà 21 chia 9 dư 3, nên 123456 chia 9 dư 3. Đây chính là dấu hiệu chia hết cho 9 quen thuộc, nay được giải thích bằng một dòng.
Định lý Fermat nhỏ
Định lý Fermat nhỏ phát biểu: nếu p là số nguyên tố và a là số nguyên không chia hết cho p, thì a^(p−1) ≡ 1 (mod p). Dạng tương đương không cần điều kiện: aᵖ ≡ a (mod p) với mọi số nguyên a. Bạn có thể xem phần giới thiệu ở trang định lý nhỏ Fermat trên Wikipedia.
Hãy thử với số nhỏ để kiểm chứng. Lấy p = 7 và a = 3. Ta tính 3⁶ = 729. Vì 729 = 7 · 104 + 1 nên 729 ≡ 1 (mod 7), đúng như định lý nói. Lấy p = 11 và a = 2: 2¹⁰ = 1024 = 11 · 93 + 1, cũng cho số dư 1.
Điều kiện “p nguyên tố” là bắt buộc. Với modulo hợp số, kết quả thường sai. Thử modulo 9 (hợp số) và a = 2: 2⁸ = 256 = 9 · 28 + 4, số dư là 4 chứ không phải 1. Vì vậy hãy kiểm tra p có nguyên tố trước khi dùng.
Vì sao định lý đúng
Ý tưởng chứng minh gọn như sau. Xét các số a, 2a, 3a, …, (p − 1)a. Khi chia cho p, chúng cho p − 1 số dư khác nhau và đều khác 0. Vậy tập số dư chính là {1, 2, …, p − 1} theo thứ tự nào đó.
Nhân tất cả lại, ta có a^(p−1) · (p − 1)! ≡ (p − 1)! (mod p). Vì (p − 1)! nguyên tố cùng nhau với p, ta rút gọn được và thu về a^(p−1) ≡ 1. Định lý chỉ dựa trên phép nhân đồng dư và việc chia an toàn.
Ví dụ và bài tập
Phần luyện tập này giúp bạn làm quen với đồng dư thức trước khi gặp các đề math olympiad problems. Hãy thử nháp trước khi đọc lời giải.
Bài 1: số dư của 3¹⁰⁰ chia cho 7
Vì 7 nguyên tố và 3 không chia hết cho 7, ta có 3⁶ ≡ 1 (mod 7). Số mũ 100 = 6 · 16 + 4. Vậy 3¹⁰⁰ = (3⁶)¹⁶ · 3⁴ ≡ 3⁴ = 81 (mod 7). Vì 81 = 77 + 4 nên số dư là 4.
Bài 2: n⁵ − n chia hết cho 5
Chứng minh rằng với mọi số nguyên n, n⁵ − n chia hết cho 5.
Áp dụng dạng thứ hai của Fermat với p = 5: n⁵ ≡ n (mod 5). Suy ra n⁵ − n ≡ 0 (mod 5), tức chia hết cho 5. Thử n = 2: 32 − 2 = 30, chia hết cho 5. Thử n = 3: 243 − 3 = 240, cũng chia hết cho 5.
Bài 3: chữ số cuối của 3²⁰²⁵
Ta xét modulo 10. Có 3² = 9, 3³ = 27 ≡ 7, 3⁴ = 81 ≡ 1 (mod 10). Chu kỳ bằng 4. Số mũ 2025 = 4 · 506 + 1, nên 3²⁰²⁵ ≡ 3¹ = 3 (mod 10). Chữ số tận cùng là 3.
Ba bài trên dùng chung một mạch: giảm số mũ nhờ chu kỳ, rồi tính số nhỏ. Khi đã quen mạch này, bạn có thể giải các bài olympiad training cấp tỉnh mà không phải lo con số khổng lồ.
Gặp bài lạ, hãy tự hỏi ba câu: modulo nào là hợp lý, có chu kỳ ngắn nào không, và có số nguyên tố nào để áp dụng Fermat không. Thường thì một trong ba câu hỏi đã đủ mở đường. Sau khi thành thạo, bạn có thể sang các chủ đề nâng cao hơn như phần dư Trung Hoa hay định lý Euler.
Nếu bạn còn đang ôn thi THPT, đừng bỏ quên các mảng khác. Bài tổng hợp công thức lượng giác giúp bạn ôn xen kẽ. Học đều nhiều mảng giúp việc luyện tập bền hơn, và đôi khi ý tưởng từ mảng này soi sáng mảng kia.
