Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English
Discrete MathĐọc trong 8 phút

Đồng dư và Định lý nhỏ Fermat

Số học đồng hồ với một cái tên chính thức. Bạn sẽ học cách đọc a ≡ b (mod n), cách cộng và nhân các đồng dư một cách an toàn, cách tìm số dư của một số như 3100 trong ba dòng, và vì sao mệnh đề đảo của định lý Fermat sai. Mọi con số ở đây đều đã được máy tính kiểm tra.

Luyện tập chủ đề này trong ứng dụng miễn phí →Tất cả bài hướng dẫn Discrete Math

Bạn đã làm điều này với đồng hồ rồi#

Bây giờ là 9 giờ. 5 giờ nữa sẽ là mấy giờ? Không phải 14. Sẽ là 2 giờ. Trên đồng hồ, 14 và 2 là cùng một vị trí, vì chúng khác nhau đúng một vòng 12.

Đồng dư (congruence) chỉ là như vậy: hai số rơi vào cùng một chỗ khi bạn quay vòng sau mỗi n. Trên đồng hồ n là 12. Trong toán rời rạc, n có thể là bất kỳ số nguyên dương nào, và nó được gọi là modulus.

Ý nghĩa của a ≡ b (mod n)#

Hãy đọc a ≡ b (mod n) thành lời là “a đồng dư với b, modulo n”. Nó có nghĩa là:

n chia hết a − b. Nói cách khác, a − b = n · k với một số nguyên k nào đó (k có thể âm hoặc bằng không).

Một cách nói tương đương: a và b có cùng số dư khi bạn chia cho n. Đó là hình ảnh chiếc đồng hồ.

Mệnh đềKiểm tra hiệuĐúng không?
17 ≡ 2 (mod 5)17 − 2 = 15 = 5 · 3Có
−3 ≡ 4 (mod 7)−3 − 4 = −7 = 7 · (−1)Có
14 ≡ 3 (mod 5)14 − 3 = 11Không, 11 không phải là bội của 5

Ký hiệu này do Gauss đưa ra vì các đồng dư hoạt động rất giống phương trình. Phần tiếp theo cho thấy chính xác giống đến mức nào.

Bạn được phép làm gì với các đồng dư#

Giả sử a ≡ b và c ≡ d, đều theo modulo n. Khi đó tất cả những điều sau là an toàn:

  • Cộng: a + c ≡ b + d (mod n).
  • Trừ: a − c ≡ b − d (mod n).
  • Nhân: ac ≡ bd (mod n).
  • Lũy thừa: ak ≡ bk (mod n), vì lũy thừa là phép nhân lặp lại.

Vì sao phép nhân đúng: viết a = b + nk và c = d + nm. Khi đó ac = bd + n(bm + dk + nkm). Phần dư ra là một bội của n, nên ac và bd đồng dư. Phép cộng cũng làm tương tự, với ít đại số hơn.

Phép chia là phép duy nhất có thể sai. 6 ≡ 16 (mod 10) là đúng, vì 16 − 6 = 10. Chia cả hai vế cho 2 và bạn được 3 ≡ 8 (mod 10), là sai, vì 8 − 3 = 5.

Quy tắc chia

Bạn chỉ được giản ước một thừa số c khỏi cả hai vế khi c và modulus n không có thừa số chung (gcd(c, n) = 1, đọc là “ước chung lớn nhất của c và n là 1”). Modulo 10 bạn có thể giản ước 3, nhưng không thể giản ước 2 hoặc 5.

Định lý nhỏ Fermat#

Đây là định lý, nói bằng lời trước. Lấy một số nguyên tố p. Lấy một số nguyên a bất kỳ không phải là bội của p. Nâng a lên lũy thừa p − 1. Kết quả luôn lớn hơn một bội của p đúng một đơn vị.

Bằng ký hiệu: nếu p là số nguyên tố và p không chia hết a, thì ap−1 ≡ 1 (mod p).

Hãy kiểm tra với a = 2, như trong bài giảng:

p2p−1Viết dưới dạng một bội của p, cộng 1
524 = 163 · 5 + 1
726 = 649 · 7 + 1
11210 = 102493 · 11 + 1

Chữ “nhỏ” có ở đó để phân biệt với định lý lớn của Fermat, một kết quả khác và khó hơn nhiều. Cả hai đều được gọi là FLT, điều này gây nhầm lẫn.

Một dạng thứ hai không cần điều kiện nào về a: ap ≡ a (mod p) với mọi số nguyên a. Nếu p không chia hết a thì bạn có thể giản ước một thừa số a (quy tắc chia cho phép, vì gcd(a, p) = 1) và nhận lại dạng đầu.

Lũy thừa khổng lồ được thu nhỏ#

Đây là chỗ định lý giúp bạn ghi điểm trong bài thi. Bạn được hỏi số dư của một lũy thừa khổng lồ. Bạn không bao giờ phải tính lũy thừa đó.

Ví dụ 1: 2100 chia cho 11. Fermat với p = 11 cho 210 ≡ 1. Khi đó 2100 = (210)10 ≡ 110 = 1. Số dư là 1.

Ví dụ 2: 3100 chia cho 7. Fermat với p = 7 cho 36 ≡ 1. Chia số mũ cho 6: 100 = 6 · 16 + 4. Vậy

3100 = (36)16 · 34 ≡ 1 · 81 ≡ 4 (mod 7), vì 81 = 77 + 4.

Công thức luôn giống nhau: tìm lũy thừa cho kết quả 1, chia số mũ cho nó, và chỉ giữ lại phần dư.

Vì sao p chia hết np − n: chứng minh quy nạp#

Bài giảng đã chứng minh dạng thứ hai cho p = 3 và p = 5 bằng quy nạp theo n. Đây là trường hợp p = 5. Đặt M(n) = n5 − n.

Bước cơ sở. M(1) = 1 − 1 = 0, và 5 chia hết 0.

Bước quy nạp. Giả sử 5 chia hết M(n). Xét hiệu M(n + 1) − M(n). Khai triển (n + 1)5 dùng hàng 5 của tam giác Pascal, 1, 5, 10, 10, 5, 1:

(n + 1)5 − (n + 1) − n5 + n = 5n4 + 10n3 + 10n2 + 5n = 5(n4 + 2n3 + 2n2 + n).

Đó là một bội của 5. Vậy M(n + 1) = M(n) + (một bội của 5), và M(n) là bội của 5 theo giả thiết quy nạp. Tổng của hai bội của 5 là một bội của 5. Theo nguyên lý quy nạp toán học, 5 chia hết n5 − n với mọi n ≥ 1.

Điều làm nó thành công: mọi số ở giữa trong hàng 5 của tam giác Pascal đều là bội của 5. Điều này cũng đúng với hàng của mọi số nguyên tố. Hàng 7 là 1, 7, 21, 35, 35, 21, 7, 1, và 7, 21, 35 đều là bội của 7. Đó là bài tập về nhà của bạn, và chứng minh giống từng chữ.

Mệnh đề đảo là sai: 341 và 561#

Mệnh đề đảo của một định lý hoán đổi giả thiết và kết luận của nó. Ở đây nó sẽ nói: nếu 2n−1 ≡ 1 (mod n), thì n là số nguyên tố. Người ta từng hy vọng dùng điều này làm phép kiểm tra tính nguyên tố.

Nó sai. Lấy n = 341. Nó không phải số nguyên tố: 341 = 11 · 31. Tuy vậy 2340 ≡ 1 (mod 341). Giả thiết đúng và kết luận sai, và một ví dụ như vậy là đủ để bác bỏ một mệnh đề kéo theo.

Bạn có thể hy vọng sửa nó bằng cách thử mọi cơ số a, không chỉ 2. Với 341 điều đó hiệu quả, vì 3340 không ≡ 1 (mod 341). Nhưng n = 561 = 3 · 11 · 17 đánh bại cả cách đó: a560 ≡ 1 (mod 561) với mọi a không có thừa số chung với 561. Những số như 561 được gọi là số Carmichael, và 561 là số nhỏ nhất.

Một câu để mang vào phòng thi

Fermat chỉ đi một chiều: số nguyên tố p cho ap−1 ≡ 1, nhưng an−1 ≡ 1 không suy ra n nguyên tố, và 341 là phản ví dụ.

Sai ở chỗ nào#

  • Quên điều kiện về a. ap−1 ≡ 1 cần p không chia hết a. Với a = 7 và p = 7, 76 ≡ 0, không phải 1.
  • Dùng modulus là hợp số. Định lý nói về số nguyên tố. 28 = 256 có số dư 4 khi chia cho 9, không phải 1.
  • Chia một đồng dư cho một thừa số chung. Hãy kiểm tra gcd(c, n) = 1 trước khi giản ước c.
  • Rút gọn số mũ theo modulo p thay vì modulo p − 1. Với 3100 mod 7 bạn chia 100 cho 6, không phải cho 7.
  • Cố chứng minh mệnh đề đảo. Nếu một câu hỏi yêu cầu bạn bác bỏ nó, đáp án là một phản ví dụ, chẳng hạn 341 với cơ số 2.

Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí

Luyện tập Discrete Math theo chủ đề: dùng được khi không có mạng, không quảng cáo, không cần tài khoản.

Luyện tập đồng dư và Fermat →

Câu hỏi thường gặp#

a ≡ b (mod n) có nghĩa là gì?

Nó có nghĩa là n chia hết a − b, nên a − b là một bội nguyên của n. Tương đương, a và b có cùng số dư khi chia cho n. Ví dụ 17 ≡ 2 (mod 5) vì 17 − 2 = 15 = 5 · 3.

Định lý nhỏ Fermat là gì?

Nếu p là số nguyên tố và a không phải là bội của p, thì a^(p−1) ≡ 1 (mod p). Một dạng tương đương đúng với mọi số nguyên a là a^p ≡ a (mod p).

Làm sao tìm số dư của một lũy thừa khổng lồ như 3^100 chia cho 7?

Dùng Fermat: 3^6 ≡ 1 (mod 7). Chia số mũ cho 6: 100 = 6 · 16 + 4. Vậy 3^100 = (3^6)^16 · 3^4 ≡ 3^4 = 81 ≡ 4 (mod 7). Số dư là 4.

Mệnh đề đảo của định lý nhỏ Fermat có đúng không?

Không. 341 = 11 · 31 là hợp số, nhưng 2^340 ≡ 1 (mod 341). Tệ hơn, 561 = 3 · 11 · 17 thỏa a^560 ≡ 1 (mod 561) với mọi a nguyên tố cùng nhau với 561. Những số như vậy gọi là số Carmichael.

Có thể chia cả hai vế của một đồng dư không?

Chỉ chia cho một số không có thừa số chung với modulus. 6 ≡ 16 (mod 10) là đúng, nhưng chia cho 2 được 3 ≡ 8 (mod 10), là sai, vì 2 và 10 có chung thừa số 2.

Đề xuất chỉnh sửa

Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.