Tại Sao Gom Nhóm Lũy Thừa Lại Chứng Minh Được Chia Hết? – Không Phải Đoán Mò

Luận điểm: Gom nhóm không phải đoán mò. Số dư của lũy thừa luôn chạy vòng, và độ dài một vòng cho biết phải gom bao nhiêu số.

Lập luận

1. Mẹo quen thuộc. 1 + 5 + 5² + … + 5⁹: gom từng cặp, mỗi cặp là một lũy thừa nhân với (1 + 5) = 6, nên cả tổng chia hết cho 6. 1 + 2 + … + 2²⁹: gom từng 3 số, mỗi nhóm có (1 + 2 + 4) = 7. Nhưng với 1 + 2 + … + 2⁷⁹ và số 17 thì gom 2, 3, 4 số đều không ra (3, 7, 15).
2. Số dư chạy vòng. 2ⁿ chia 17 dư lần lượt 1, 2, 4, 8, 16, 15, 13, 9 rồi quay về 1. Mẹo tính: số dư mới = số dư cũ × 2, lớn hơn 17 thì trừ 17. Một vòng dài 8 bước, tức 2⁸ = 256 = 15·17 + 1.
3. Gom đúng một vòng. 1 + 2 + … + 2ᵏ⁻¹ = 2ᵏ − 1. Gom 8 số được 2⁸ − 1 = 255 = 15·17. Tổng 80 số hạng = 10 nhóm, mỗi nhóm là 255 nhân một lũy thừa của 2, nên chia hết cho 17.
4. Đọc đề để đoán số nhóm. Muốn biết gom mấy, tìm độ dài vòng số dư (3ⁿ chia 13: 1, 3, 9 → vòng 3, nên gom 1 + 3 + 9 = 13). Đề thường chọn số số hạng chia hết cho độ dài vòng.
5. Mẹo thứ hai: về cùng cơ số. 4⁶ + 2⁹ = 2¹² + 2⁹ = 2⁹·(8 + 1) = 2⁹·9. 27⁴ + 9⁵ = 3¹² + 3¹⁰ = 3¹⁰·10. Đây là gom nhóm ngược: rút phần chung ra ngoài.

Câu chuyện

• 1640, Pierre de Fermat, luật sư ở Toulouse, làm toán lúc rảnh. Trong thư gửi Frénicle de Bessy, ông nêu định lý nhỏ Fermat (p nguyên tố, a không chia hết cho p thì aᵖ⁻¹ chia p dư 1), và viết rằng sẽ gửi chứng minh "nếu không sợ nó quá dài".
• 1736, Leonhard Euler công bố chứng minh đầu tiên, 96 năm sau lá thư (Leibniz có chứng minh gần giống trong bản thảo trước 1683 nhưng không công bố).
• 1801, Carl Friedrich Gauss, 24 tuổi, in Disquisitiones Arithmeticae, biến các mẹo số dư thành một môn có hệ thống và đưa ra kí hiệu đồng dư ≡.
• 1977, mã hoá RSA (Rivest, Shamir, Adleman, MIT) ra đời; chứng minh RSA giải mã đúng dựa trên định lý nhỏ Fermat / định lý Euler.

Ứng dụng

• Lịch: thứ trong tuần chạy vòng 7. Thứ Sáu + 100 ngày: 100 = 14·7 + 2 → Chủ nhật.
• Đồng hồ: 9 giờ + 4 tiếng = 1 giờ (vòng 12).
• Mã hoá RSA khi đăng nhập, chuyển khoản: tính lũy thừa rất lớn rồi chỉ giữ số dư.
• Chữ số kiểm tra của số thẻ ngân hàng (mod 10), ISBN: gõ sai một chữ số là bị phát hiện.

Nguồn

• Wikipedia: Fermat's little theorem · Disquisitiones Arithmeticae · Modular arithmetic · RSA cryptosystem · Luhn algorithm
• MacTutor (St Andrews): Fermat · Gauss
• cut-the-knot: Fermat's Little Theorem · MIT 18.310 RSA notes · Wikisource: Disquisitiones Arithmeticae (bản dịch)