Xemtailieu Tải về Skkn sử dụng hệ thặng dư đầy đủ, thặng dư thu gọn, thặng dư trung hoa để giải toán số học.
SỞ GIÁO DỤC VÀ ĐÀO TẠO VĨNH PHÚC TRƯỜNG THPT CHUYÊN VĨNH PHÚC BÁO CÁO KẾT QUẢ SÁNG KIẾN KINH NGHIỆM TÊN SÁNG KIẾN KINH NGHIỆM: SỬ DỤNG HỆ THẶNG DƯ ĐẦY ĐỦ, THẶNG DƯ THU GỌN, THẶNG DƯ TRUNG HOA ĐỂ GIẢI TOÁN SỐ HỌC. MÔN : TOÁN HỌC TỔ BỘ MÔN : TOÁNTIN MÃ : 55 NGƯỜI THỰC HIỆN : NGUYỄN DUY LIÊN ĐIỆN THOẠI : 01233045361 E mail : [email protected] Bài viết này của thầy Nguyễn Duy Liên đã được đăng trong Tạp chí Toán Học và Tuổi Trẻ trong hai số tháng 8 và 9 năm 2013. Cảm ơn thầy gửi đến chia sẻ với www.laisac.page.tl 1 LỜI NÓI ĐẦU Ngạn ngữ Pháp có câu: "Le Mathématique est le Roi des Sciences mais L’Arithmétique est la Reine",dịch nghĩa:"Toán học là vua của các khoa học nhưng Số học là Nữ hoàng". Điều này nói lên tầm quan trọng của Số học trong đời sống và khoa học. Số học giúp con người ta có cái nhìn tổng quát, sâu rộng hơn, suy luận chặt chẽ và tư duy sáng tạo. Trong các kì thi chọn học sinh giỏi các cấp THCS, THPT cấp tỉnh, cấp Quốc gia,cấp khu vực, cấp quốc tế, các bài toán về Số học thường đóng vai trò quan trọng. Chúng ta có thể làm quen nhiều dạng bài toán Số học, biết nhiều phương pháp giải, nhưng cũng có bài chỉ có một cách giải duy nhất. Mỗi khi gặp một bài toán mới chúng ta lại phải suy nghĩ tìm cách giải mới. Sự phong phú đa dạng của các bài toán Số học luôn là sự hấp dẫn đối với mỗi giáoviên, học sinh giỏi yêu toán. Xuất phát từ những ý nghĩ đó tôi đã sưu tầm và hệ thống lại một số bài toán để viết lên chuyên đề "Sử dụng hệ thặng dư đầy đủ, hệ thặng dư thu gọn,thặng dư Trung Hoa để giải toán Số học ". Chuyên đề gồm các phần : Phần I: Kiến thức cơ bản. Phần II:Ứng dụng hệ thặng dư để giải toán · Ứng dụng 1: Sử dụng hệ thặng dư để tính tổng · Ứng dụng 2: Sử dụng hệ thặng dư trong các bài toán đa thức, dãy số nguyên. · Ứng dụng 3: Sử dụng hệ thặng dư trong tập con tập số nguyên dương, bài toán số học chia hết · Ứng dụng 4: Sử dụng hệ thặng dư trong phương trình Đi Ô Phăng bậc nhất. Phần III: Bài tập tương tự. Mục tiêu ở đây là một số bài mẫu, một số bài khác biệt căn bản đã nói lên được phần chính yếu của chuyên đề. Tuy vậy, những thiếu sót nhầm lẫn cũng không thể tránh khỏi được tất cả , về phương diện chuyên môn cũng như phương diện sư phạm. Lối trình bày bài giải của tôi không phải là một lối duy nhất. Tôi đã cố gắng áp dụng cách giải cho phù hợp với chuyên đề, học sinh có thể theo mà không lạc hướng. Ngoài ra lúc viết tôi luôn luôn chú ý đến các bạn vì nhiều lí do phải tự học, vì vậy giản dị và đầy đủ là phương châm của tôi khi viết chuyên đề này. Tôi xin trân thành cảm ơn các thầy cô giáo,các em học sinh góp ý thêm cho những chỗ thô lâu và phê bình chân thành để có dịp tôi sửa chữa chuyên đề này hoàn thiện hơn. Vĩnh Yên, Trung Thu, năm 2012 NGUYỄN DUY LIÊN 2 PHẦN I. KIẾN THỨC CƠ BẢN 1.Hệ thặng dư đầy đủ Cho tập A = {a 1 ,a 2 ,...,a n } . Giả sử ri ,0 £ ri £ n - 1 là số dư khi chia a i cho r . i Nếu tập số dư {r1 ,r2 ,..., r n } trùng với tập {0,1,..., n - 1} thì ta nói A là một hệ thặng dư đầy đủ (gọi tắt là HĐĐ) modun n. Dễ thấy: Tập A lập thành một HĐĐ(modun n) nếu và chỉ nếu: i ¹ j Þ a i ¹ a j ( mod n ) . Nếu A = {a1 ,a 2 ,...,a n } là HĐĐ mod n thì từ định nghĩa dễ suy ra · Với mọi m Î Z tồn tại duy nhất a i Î A sao cho a i º m ( mod n ) . · Với mọi a Î Z tập a + A = {a + a1 ,a + a 2 ,...,a + a n } là HĐĐ mod n · Với mọi cÎ Z , ( c, n ) = 1 , tập cA = {ca 1 ,ca 2 ,...,ca n } là HĐĐ mod n. Tập A * = {0,1,2,...,n - 1} là HĐĐ mod n không âm nhỏ nhất. Số phần tử của tập A bằng A = n 2. Hệ thặng dư thu gọn. Cho tập B = {b1 , b 2 ,...,b k } là một tập hợp k số nguyên và ( bi ,n ) = 1với mọi i = 1, 2,..., k .Giả sử b i = q i n + ri ,1 £ ri