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

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là 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ả.
Nội dung trích xuất từ tài liệu:
Sáng kiến kinh nghiệm THPT: Ứ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: 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 1I. ĐẶ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ệntư 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ânquen 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ứctạ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, OlympicQuố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ọccó 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ủaToá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 emhọ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ệctiế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 khigiả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ếpcậ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. 22. 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ừ khimớ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àitoá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ếtcho 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 3phầ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 đíchnghiê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 địnhlí 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 trunghọ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ọcsinh 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 3quố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… 4II. 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 nlà {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ợpcá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ôngtin 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ủamộ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ùngsố 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ấtsau: 5 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, x 2, x3,…, x n} 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, bthỏa mãn (a, n) = 1, khi đó:{ax1+b, ax2+b, ax3+b,…, axn+b} là một HTDĐĐmodulo n. Cho f (x 1 , x 2 ,..., x n ) 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ó: f (a1 ,a 2 ,...,a n )  f (b1 ,b 2 ,..., b n )(mod n) . Khi chỉ nghiên cứu các số nguyên tố cùng nhau với số nguyên dương nta 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 (n) là số các số nguyên k  1dương nguyên tố cùng nhau với n và nhỏ hơn n. Ta có: (n)  n  1   i 1  pi trong đó {p1 ,p 2 ,...,p k ...