Sáng kiến kinh nghiệm Ứng dụng hệ thặng dư giải các bài toán số học

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: 
ĐẶNG ĐÌNH SƠN TỔ: TOÁN – TIN
AN VĂN TÂN PHÒNG: KT&KĐCL 
 SỞ GDĐT TỈNH NINH BÌNH
NINH BÌNH NĂM 2015
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.
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 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
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:
Tập hợp n số nguyên {x1, x2, x3,, xn} là một HTDĐĐ modulo n khi và chỉ khi “Nếu xi º xj (modn) thì i = j với mọi i, j Î{1, 2,, n}”.
Cho {x1, x2, x3,, xn} là một HTDĐĐ modulo n, khi đó với mỗi số nguyên x luôn tồn tại duy nhất i Î{1, 2,, n} thỏa mãn x º xi (modn).
Cho {x1, x2, x3,, xn} là một HTDĐĐ modulo n và hai số nguyên a, b thỏa mãn (a, n) = 1, khi đó:{ax1+b, ax2+b, ax3+b,, axn+b} là một HTDĐĐ modulo n.
Cho là một đa thức n biến với hệ số nguyên và {a1, a2,, an}, {b1, b2, , bn} là các HTDĐĐ modulo n ta luôn có: 
.
	Khi chỉ nghiên cứu các số nguyên tố cùng nhau với số nguyên dương n ta sử dụng khái niệm hệ thăng dư thu gọn modulo n.
1.2. Hệ thặng dư thu gọn
Nhận xét: Với mỗi số nguyên dương n, kí hiệu j(n) là số các số nguyên dương nguyên tố cùng nhau với n và nhỏ hơn n. Ta có: trong đó là tập hợp các ước nguyên tố của n.
Định nghĩa: Tập hợp các số nguyên {x1, x2, x3,, xj(n)} gọi là một hệ thặng dư thu gọn (HTDTG) modulo n nếu các số xi đều nguyên tố cùng nhau với n và hai số bất kì không đồng dư với nhau theo modulo n.
Nhận xét: 
Cho {x1, x2, x3,, xj(n)} là một HTDTG modulo n. Khi đó với mọi số nguyên x nguyên tố cùng nhau với n luôn tồn tại duy nhất i Î{1, 2,, xj(n)} thỏa mãn x º xi (modn).
Cho {x1, x2, x3,, xj(n)} là một HTDĐĐ modulo n và số nguyên a thỏa mãn (a, n) = 1, khi đó:{ax1, ax2, ax3,, axn} là một HTDĐĐ modulo n.
Cho {x1, x2, x3,, xj(n)} là một HTDĐĐ modulo n. Khi đó với mọi thuộc {x1, x2, x3,, xj(n)} luôn tồn tại duy nhất thuộc thỏa mãn (x, gọi là nghịch đảo modunlo n) và nếu thì . 
Chứng minh: 
Vì x Î{x1, x2, x3,, xj(n)} nên x nguyên tố cùng nhau với n, do đó {xx1, xx2, xx3,, xxj(n)} là một HTDĐĐ modulo n. Suy ra tồn tại duy nhất i Î{1, 2,, xj(n)} thỏa mãn xxi º 1 (modn). 
Trong nhận xét trên có thể tổng quát hơn: Cho {x1, x2, x3,, xj(n)} là một HTDĐĐ modulo n và số nguyên a nguyên tố cùng nhau với n. Khi đó với mọi thuộc {x1, x2, x3,, xj(n)} luôn tồn tại duy nhất thuộc thỏa mãn và nếu thì . 
Từ định nghĩa và các tính chất của hệ thặng dư ta có thể áp dụng để giải các bài chứng minh đồng dư, chia hết; chứng minh tồn tại các số tự nhiên, tìm các số nguyên thỏa mãn các qua hệ đồng dư, chia hết; tính tổng phần nguyên, phần lẻ.
2. ỨNG DỤNG HỆ THẶNG DƯ CHỨNG MINH MỘT SỐ ĐỊNH LÍ CƠ BẢN CỦA SỐ HỌC
Định lí 1 (Fermat nhỏ)
Cho số nguyên tố p và số nguyên a nguyên tố cùng nhau với p. Khi đó ta luôn có .
Chứng minh:
Ta có {1, 2, 3,, p – 1} là một HTDTG modulo p. Vì (a, p)=1 nên {a, 2a, 3a,,(p – 1)a} là một HTDTG modulo p. 
Suy ra 
Nhận xét: Với cách chứng minh tương tự ta có định lí sau đây.
Định lí 2 (Euler)
Nếu số nguyên a nguyên tố cùng nhau với số nguyên dương n thì .
Định lí 3
Phương trình đông dư có nghiệm khi và chỉ khi ước chung lớn nhất d của a và n cũng là ước của b. Khi đó phương trình có đúng d nghiệm (mỗi nghiệm là một lớp thặng dư modulo n)
Chứng minh: 
	Nếu phương trình có nghiệm thì dễ thấy d | b.
	Giả sử d | b.
Trước tiên ta chứng minh trong trường hợp a và n nguyên tố cùng nhau hay (a, n) = 1. 
Thật vậy ta có: Giả sử {x1, x2, x3,, xn} là một HTDĐĐ modulo n suy ra {ax1, ax2, ax3,, axn} là một HTDĐĐ modulo n. Do đó tồn tại duy nhất x Î {x1, x2, x3,, xn} thỏa mãn .
d = (a,n) có 1 nghiệm duy nhất.
Giả sử x0 là nghiệm của Þ là nghiệm củaÞcó đúng d nghiệm.
Định lí 4 (Wilson)
Số nguyên dương p là số nguyên tố nếu và chỉ nếu .
Chứng minh: 
+ Giả sử , suy ra p không có ước dương nào ngoài 1 và p, do đó p nguyên tố.
+ Với p nguyên tố.
Nhận xét: Với mỗi luôn tồn tại duy nhất thỏa mãn . 
Do đó: {2, 3, , p – 2} chia thành cặp nghịch đảo. Suy ra .
3. ỨNG DỤNG HỆ THẶNG DƯ GIẢI MÔT SỐ BÀI TOÁN SỐ HỌC
Bài toán 1 
Cho số nguyên dương n nguyên tố cùng nhau với và là HTDTG modulo n. Chứng minh rằng: .
Lời giải: 
Từ giả thiết suy ra (2, n) = 1, do đó là HTDTG modulo n.
 (vì )
Bài toán 2
Cho số nguyên tố p thỏa mãn . Chứng minh rằng với mỗi a thuộc luôn tồn tại duy nhất b thuộc thỏa mãn 
Lời giải: 
Đặt .
Ta có: là một HTDTG modulo n.
Do nên hay .
Với a thuộc luôn tồn tại thuộc thỏa mãn .
Nếu thuộc thì lấy b là ta có:
Nếu thuộc thì lấy b là ta có:
Bài toán 3
Cho số nguyên tố p thỏa mãn . Chứng minh rằng với mỗi số nguyên n luôn tồn tại vô số số nguyên m thỏa mãn . 
Lời giải: 
Ta chứng minh: Nếu {x1, x2, x3,, xp} là một HTDĐĐ modulo p thì là một HTDĐĐ modulo p.
Thật vậy: 
+ 
+ 
Vậy . Suy ra là một HTDĐĐ modulo p.
Vì là một HTDĐĐ modulo p nên với mỗi số nguyên n luôn tồn tại vô số số nguyên m thỏa mãn .
Bài toán 4
Cho số nguyên tố p lớn hơn 3 và đa thức P(x) = 1 + 2x + 3x2 ++ pxp-1. Chứng minh rằng với mọi số nguyên m phương trình P(x) º m luôn có nghiệm nguyên.
Lời giải:
Ta chứng minh: Nếu x chạy qua một hệ thặng dư đầy đủ mod p thì P(x) cũng chạy qua một hệ thặng dư đầy đủ mod p.
Thật vậy: 
Bài toán 5
Tìm số nguyên dương a lẻ sao cho với mọi số nguyên dương k lớn hơn 2 luôn tồn tại số nguyên x thỏa mãn .
Lời giải
, a lẻ, x lẻ .
Với , suy ra tồn tại n nguyên dương sao cho a = 8n + 1.
+ k = 3: Chọn x = 1.
+ k > 3:
Nhận xét: Nếu x chạy qua một HTDĐĐ modulo 2m thì 2x2+x cũng chạy qua một HTDĐĐ đầy đủ modulo 2m (m nguyên dương).
Thật vậy: 
.
Do đó: Tồn tại t nguyên thỏa mãn:
Suy ra .
Kết luận: a thỏa mãn .
Bài toán 6
Cho số nguyên tố p lớn hơn 3. Chứng minh rằng:
a) 
b) 
Lời giải:
Nhận xét: Với mỗi luôn tồn tại duy nhất thỏa mãn . 
Do đó: hay .
2
Bài toán 7
Cho số nguyên dương n lẻ, . Chứng minh rằng: 
Lời giải: 
	Ta sẽ chứng minh với mỗi số tự nhiên x thuộc A luôn tồn tại duy nhất thuộc A thỏa mãn và khi và chỉ khi x = 1.
	Thật vậy: Giả sử là một HTDTG modulo n, . Vì là một HTDTG modulo n. Do đó tồn duy nhất thuộc thỏa mãn . 
Ta có:
.
Từ nhận xét trên suy ra lẻ và chia thành cặp nghịch đảo theo modulo n. Từ đó ta có điều phải chứng minh.
Nhận xét: Với (là các số nguyên tố phân biệt), ta có .
Bài toán 8 
Cho số nguyên tố p thỏa mãn . Chứng minh rằng:
Tồn tại số nguyên a thoả mãn 
Lời giải:
a) Vì nên p có dạng 8k + 1 (k nguyên dương).
Suy ra .
b) Nhận xét: Với mỗi luôn tồn tại duy nhất thỏa mãn . 
Nếu không tồn tại x thuộc sao cho thì được chia thành tập {x,} thỏa mãn. Suy ra , mâu thuẫn với ý a. Do đó ta có điều phải chứng minh.
Bài toán 9
Cho số nguyên tố p và số nguyên a thỏa mãn . 
Tính: 
Lời giải
Nhận xét: Với x, y nguyên thỏa mãn , (x, p) = 1 ta có 
Thật vậy: ,
Theo bài toán 2, với mỗi x thuộc luôn tồn tại duy nhất thuộc thỏa mãn . 
Suy ra 2, do đó 
4. MỘT SỐ BÀI TẬP
1. Cho đa thức Q(x) = (p – 1)xp – x – 1 (p là một số nguyên tố lẻ).Chứng minh rằng: Với mọi số nguyên m luôn tồn tai số nguyên n thỏa mãn Q(n) – m  chia hết cho pp.
2. Cho a, b là các số nguyên dương nguyên tố cùng nhau, b > 1. Chứng minh rằng với mọi số nguyên N, tồn tại duy nhất cặp số nguyên x, y thỏa mãn điều kiện N = ax + by và 0 ≤ x < b
3. Cho a, b là các số nguyên dương nguyên tố cùng nhau. Chứng minh rằng N = ab – a – b là số nguyên lớn nhất không biểu diễn được dưới dạng ax + by với x, y là các số nguyên không âm. Hơn nữa, với mọi p, q nguyên với p + q = N, có đúng một trong hai số p, q biểu diễn được dưới dạng ax + by với x, y là các số nguyên không âm (mà ta sẽ gọi tắt là biểu diễn được).
4. Cho số nguyên dương n và số nguyên tố p lớn hơn n+1. Chứng minh rằng đa thức không có nghiệm nguyên.
5. Cho dãy số (an) được xác định bởi . Chứng minh rằng dãy số (an) chứa vô hạn số nguyên chia hết cho 7.
6. Chứng minh rằng: 
7. Tìm x, y nguyên dương sao cho nguyên tố.
8. Tính tổng: 
5. TÀI LIỆU THAM KHẢO
[1] Hà Huy Khoái (2004), Số học, Nhà XB Giáo dục.
[2] Titu Andresscu and Dorin Andrica, Number Theory, Structures, Examples and Problems, Springer
III. KẾT LUẬN
	Sáng kiến đưa ra cách tiếp cận bài toán số học qua Hệ thăng dư, giúp các em học sinh dễ dàng tiếp thu hệ thống kiến thức số học, hình thành tư duy số học một cách tự nhiên.
Sáng kiến đã được các tác giả ứng dụng thực tế trong giảng dạy các lớp chuyên toán và tập huấn đội tuyển học sinh giỏi Quốc gia, đã thu được những kết quả rất tốt. Các em học sinh đã tiếp thu các kiến thức số học tốt hơn, vận dụng và giải được nhiều bài tập khó trong các kì thi. Góp phần nâng cao thành tích học sinh giỏi Quốc gia môn toán trong các năm học qua.
Các tác giả rất mong nhận được sự đóng góp ý kiến của bạn bè đồng nghiệp.
Ninh Bình, tháng 05 năm 2015
 Các tác giả