Sáu chiếc ghế, sáu người, một quy tắc#
Sáu người ngồi trên các ghế đánh số từ 1 đến 6. Chuông reo, và mọi người di chuyển theo cùng một quy tắc: người ở ghế x chuyển sang ghế 3x, quay vòng modulo 7. (“Mod 7” nghĩa là lấy phần dư sau khi chia cho 7.)
Ai cũng có ghế không? Có ai đụng nhau không? Câu hỏi đó, khi được đặt ra cẩn thận, chính là toàn bộ chủ đề này.
Ánh xạ x ↦ 3x mod 7#
Mũi tên ↦ đọc là “đi đến”. Đây là nơi mọi người chuyển đến:
| x | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 3x | 3 | 6 | 9 | 12 | 15 | 18 |
| 3x mod 7 | 3 | 6 | 2 | 5 | 1 | 4 |
Mỗi ghế từ 1 đến 6 xuất hiện đúng một lần ở hàng dưới. Không có hai người nào đụng nhau, nên ánh xạ là đơn ánh (injective, một-một). Không ghế nào bị bỏ trống, nên nó là toàn ánh (surjective, lên). Cả hai cùng lúc tạo nên một song ánh (bijection). Một song ánh từ một tập hợp lên chính nó còn được gọi là một hoán vị (permutation) của tập hợp đó.
Vì sao nó là song ánh, và khi nào thì không#
Giả sử hai ghế x và y được chuyển đến cùng một chỗ: 3x ≡ 3y (mod 7). Khi đó 7 chia hết 3(x − y). Vì 7 là số nguyên tố và không chia hết 3, nó phải chia hết x − y. Với x và y đều nằm giữa 1 và 6, điều đó buộc x = y. Vậy không thể có đụng nhau.
Điều then chốt là 3 và 7 không có ước chung. Thay đổi điều đó thì ánh xạ hỏng. Thử x ↦ 2x mod 8 trên {0, 1, …, 7}: 2 · 0 = 0 và 2 · 4 = 8 ≡ 0. Hai đầu vào đụng nhau, và đầu ra chỉ là 0, 2, 4, 6. Một nửa số ghế vẫn trống.
x ↦ ax mod n là một song ánh khi và chỉ khi a và n không có ước chung, tức gcd(a, n) = 1. Khi n là số nguyên tố p, điều đó đúng với mọi a từ 1 đến p − 1.
Lần theo một số: quỹ đạo của nó#
Giờ hãy cứ tiếp tục rung chuông. Chỉ nhìn một người. Danh sách các ghế người đó đi qua được gọi là quỹ đạo (orbit).
Bắt đầu từ 1 và mỗi lần nhân với 3, modulo 7:
1 → 3 → 2 → 6 → 4 → 5 → 1.
Sau sáu bước họ trở về chỗ xuất phát. Trên một tập hữu hạn, quỹ đạo cuối cùng phải lặp lại, vì chỉ có chừng ấy ghế. Xét như một tập hợp, quỹ đạo là {1, 2, 3, 4, 5, 6}: người này đi qua mọi ghế.
Viết bằng lũy thừa, các ghế đi qua từ 1 là 31, 32, 33, … mod 7. Ký hiệu f2(x) nghĩa là f(f(x)), tức áp dụng quy tắc hai lần. Đó không phải là bình phương.
Cấp nhân#
Số bước cho đến khi bạn trở lại 1 lần đầu tiên được gọi là cấp nhân (multiplicative order) của a modulo p. Đó là số nguyên dương k nhỏ nhất sao cho ak ≡ 1 (mod p).
| a | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| cấp của a modulo 7 | 1 | 3 | 6 | 3 | 6 | 2 |
Hai trường hợp nhanh làm bằng tay. Với a = 2: 2, 4, 8 ≡ 1, nên cấp là 3. Với a = 3: để ý 33 = 27 ≡ 6 ≡ −1, nên 36 ≡ (−1)2 = 1, và cấp là 6.
Hãy nhìn các cấp: 1, 3, 6, 3, 6, 2. Tất cả đều là ước của 6 = p − 1. Điều đó không phải ngẫu nhiên. Định lý nhỏ Fermat nói ap−1 ≡ 1, và các lũy thừa của a lặp lại với chu kỳ bằng cấp, nên cấp phải chia hết p − 1.
Căn nguyên thủy#
Một số g là căn nguyên thủy (primitive root) modulo p khi quỹ đạo của nó đi qua mọi ghế: các lũy thừa g, g2, …, gp−1 cho ra tất cả 1, 2, …, p − 1. Tương đương, cấp của g là p − 1, lớn nhất có thể.
- 3 là căn nguyên thủy của 7. Các lũy thừa của nó là 3, 2, 6, 4, 5, 1: đủ cả sáu số.
- 2 thì không. Các lũy thừa của nó là 2, 4, 1, rồi lặp lại. Các ghế 3, 5 và 6 không bao giờ được đi qua.
Modulo 7 các căn nguyên thủy chính xác là 3 và 5. Là số nguyên tố không làm một số thành căn nguyên thủy (2 là số nguyên tố mà vẫn không phải), và ap−1 ≡ 1 của Fermat đúng với mọi a, nên nó cũng không thể chọn ra các căn nguyên thủy.
Bài tập về nhà của bài giảng, modulo 11. Ánh xạ x ↦ 5x mod 11 là một song ánh trên {1, …, 10} vì gcd(5, 11) = 1. (Bạn thậm chí có thể hoàn tác nó: 5 · 9 = 45 ≡ 1, nên nhân với 9 sẽ đảo ngược nó.) Để tìm căn nguyên thủy, thử 2: các lũy thừa của nó modulo 11 là 2, 4, 8, 5, 10, 9, 7, 3, 6, 1. Cả mười số đều xuất hiện trước số 1 đầu tiên, nên 2 là căn nguyên thủy của 11.
Cấp của a là số lần bạn nhân với a để trở về 1, nó luôn là ước của p − 1, và căn nguyên thủy là một số có cấp bằng toàn bộ p − 1.
Sai ở chỗ nào#
- Quên rút gọn. 2 · 4 = 8, và 8 phải được viết là 1 modulo 7. Để nguyên 8 khiến quỹ đạo trông dài hơn thực tế.
- Đếm điểm xuất phát hai lần. Quỹ đạo 1 → 2 → 4 → 1 có ba phần tử, không phải bốn.
- Cho rằng mọi ánh xạ x ↦ ax đều là song ánh. Chỉ khi gcd(a, n) = 1. Hãy kiểm tra 2x mod 8.
- Nhầm cấp với căn nguyên thủy. Mọi a đều có một cấp. Chỉ những số có cấp p − 1 mới là căn nguyên thủy.
- Đọc f2(x) như một bình phương. Nó có nghĩa là áp dụng f hai lần.
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 quỹ đạo và căn nguyên thủy →Câu hỏi thường gặp#
Vì sao x ↦ 3x mod 7 là một song ánh?
Vì 3 và 7 không có ước chung. Nếu 3x ≡ 3y (mod 7) thì 7 chia hết 3(x − y), nên 7 chia hết x − y, điều này buộc x = y trên {1, …, 6}. Một ánh xạ đơn ánh từ một tập hữu hạn vào chính nó cũng là toàn ánh, nên nó là một song ánh.
Cấp nhân của một số modulo p là gì?
Là số nguyên dương k nhỏ nhất sao cho a^k ≡ 1 (mod p). Ví dụ 2^3 = 8 ≡ 1 (mod 7), nên cấp của 2 modulo 7 là 3. Cấp luôn là ước của p − 1.
Căn nguyên thủy là gì?
Là một số g mà các lũy thừa g, g², …, g^(p−1) modulo p cho ra mọi số dư khác 0 từ 1 đến p − 1. Tương đương, cấp của nó là p − 1. Modulo 7 các căn nguyên thủy là 3 và 5; 2 không phải vì các lũy thừa của nó chỉ là 2, 4, 1.
Quỹ đạo là gì?
Bắt đầu từ một phần tử và liên tục áp dụng cùng một hàm: a, f(a), f(f(a)), và cứ thế. Tập hợp các vị trí bạn đi qua là quỹ đạo của a. Trên một tập hữu hạn, quỹ đạo cuối cùng luôn lặp lại, nên nó hữu hạn.
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.