1
SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH NINH BÌNH
TRƯỜNG THPT CHUYÊN LƯƠNG VĂN TỤY
BẢN ĐĂNG KÍ SÁNG KIẾN
NĂM HỌC 2014 – 2015
ĐỀ TÀI: ỨNG DỤNG HỆ THẶNG DƯ
GIẢI CÁC BÀI TOÁN SỐ HỌC
NGƯỜI THỰC HIỆN:
1) ĐẶNG ĐÌNH SƠN TỔ: TOÁN – TIN
2) AN VĂN TÂN PHÒNG: KT&KĐCL
SỞ GDĐT TỈNH NINH BÌNH
NINH BÌNH NĂM 2015
2
I. ĐẶT VẤN ĐỀ
1. Lí do chọn đề tài
Số học là một môn khoa học có vai trò rất quan trọng trong việc rèn luyện
tư duy sáng tạo cho học sinh. Thế giới những con số cũng thật gần gũi, thân
quen nhưng cũng đầy bí ẩn. Tư duy số học rất tự nhiên nhưng thực sự rất phức
tạp đòi hỏi người học, nghiên cứu phải có tư duy cao. Các bài toán số học là
thách thức của bao thế hệ học sinh trong các kỳ thi chọn học sinh giỏi (HSG)
toán các cấp, như kỳ thi chọn HSG cấp tỉnh, kỳ thi HSG cấp Quốc gia, Olympic
Quốc tế và nhiều bài toán số học vẫn còn là thách thức của cả nhân loại. Số học
có một sức hút và một vẻ đẹp kì lạ, chính vì vậy nó được gọi là “Bà chúa của
Toán học”.
Việc học tập môn số học trong chương trình toán trung học của các em
học sinh gặp rất nhiều khó khăn bởi nhiều lí do. Trong đó phần lớn là do việc
tiếp cận các bài toán số học một cách không tự nhiên, không cơ bản, do đó
không hình thành được tư duy số học cho các em nên các em thường bế tắc khi
giải các bài toán số học. Với mong muốn trang bị cho người học một cách tiếp
cận tốt với bộ môn số học là lí do các tác giả viết đề tài này.
3
2. Mục đích nghiên cứu
Cách tiếp cận, xây dựng hệ thống kiến thức số học qua lí thuyết về Hệ
thặng dư có thể coi là cách tiếp cận tự nhiên nhất cho người học. Ngay từ khi
mới học về những con số ở các lớp tiểu học, trung học cơ sở khi giải các bài
toán về chia hết, chẳng hạn chứng minh một biểu thức f(n) (n nguyên) chia hết
cho 3 chúng ta đã biết xét các trường hợp n = 3k, n = 3k + 1, n = 3k + 2 (k là số
nguyên), mô hình chung chúng ta đã hiểu rằng tập số nguyên được chia thành 3
phần (3 lớp thặng dư modulo 3), khi đó chúng ta chỉ làm việc với ba số 0, 1, 2 là
ba đại diện của ba phần ({0, 1, 2} là một hệ thặng dư đầy đủ modulo 3). Như
vậy chúng ta đã tiếp cận với Hệ thặng dư từ những bài học lọt lòng về số học.
Tiếp cận các bài toán số học bằng lí thuyết về Hệ thặng dư là mục đích
nghiên cứu đề tài này của các tác giả.
3. Đối tượng, phạm vi nghiên cứu
Đối tượng nghiên cứu của đề tài là các kiến thức về Hệ thặng dư, các định
lí cơ bản của số học và các bài toán số học trong chương trình toán học trung
học phổ thông, từ các bài tập cơ bản đến các bài tập khó trong các kỳ thi học
sinh giỏi toán cấp tỉnh, cấp quốc gia và Olympic toán quốc tế.
4. Phạm vi ứng dụng của đề tài
Bản sáng kiến này được sử dụng cho các em học sinh học học tập môn số
học, ôn thi học sinh giỏi toán THPT cấp tỉnh, cấp quốc gia và Olympic toán
4
quốc tế. Sáng kiến cũng được sử dụng cho các thầy cô giáo dạy bộ môn Toán và
bồi dưỡng học sinh giỏi THPT.
5. Phương pháp nghiên cứu
Nghiên cứu qua thực tế giảng dạy ở các lớp chuyên toán và công tác tổ
chức các kì thi chọn học sinh giỏi, chọn đội tuyển học sinh giỏi Quốc gia.
Nghiên cứu qua các tài liệu, semina, mạng internet…
5
II. GIẢI QUYẾT VẤN ĐỀ
1. HỆ THẶNG DƯ
Tập hợp các số dư trong phép chia các số nguyên cho số nguyên dương n
là {0, 1, 2, …, n – 1}. Như vậy tập số nguyên được chia thành n lớp thặng dư
modulo n, trong đó hai số nguyên thuộc cùng một lớp nếu chúng có cùng số dư
khi chia cho n (đồng dư theo modulo n). Mỗi lớp ta chọn một đại diện, tập hợp
các đại diện của các lớp gọi là một Hệ thặng dư đầy đủ modulo n. Các thông
tin thu được từ hệ thặng dư giúp chúng ta nghiên cứu tính chất của tập số
nguyên tập số nguyên. Như vậy hệ thặng dư giúp ta nghiên cứu tính chất của
một tập vô hạn thông qua một tập hữu hạn.
1.1 Hệ thặng dư đầy đủ
Định nghĩa: Với n là một số nguyên dương, hệ thặng dư đầy đủ
(HTDĐĐ) modulo n là tập hợp gồm n số nguyên mà hai số bất kì không có cùng
số dư khi chia cho n.
Ví dụ:
HTDĐĐ nguyên dương nhỏ nhất modulo n: {1, 2, 3,…, n}
HTDĐĐ có giá trị tuyệt đối nhỏ nhất modulo (2n+1): {–n, –(n–1),…,1, 0,
1, 2,…, n}
Từ định nghĩa hệ thặng dư đầy đủ modulo n suy ra một số tính chất
sau: