Tài liệu Skkn ứ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 2) AN VĂN TÂN TỔ: TOÁN – TIN PHÒNG: KT&KĐCL SỞ GDĐT TỈNH NINH BÌNH NINH BÌNH NĂM 2015 1 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 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 3 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… 4 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: 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, 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 f (x1 , 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 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 (n) là số các số nguyên k � 1� 1 � dương nguyên tố cùng nhau với n và nhỏ hơn n. Ta có: (n)  n �� pi � i 1 � trong đó {p1 ,p 2 ,...,p k } là tập hợp các ước nguyên tố của n. 6 Định nghĩa: Tập hợp các số nguyên {x 1, x2, x3,…, x(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,…, x(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,…, x(n)} thỏa mãn x  xi (modn). Cho {x1, x2, x3,…, x(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,…, x(n)} là một HTDĐĐ modulo n. Khi đó với mọi thuộc {x1, x2, x3,…, x(n)} luôn tồn tại duy nhất x thuộc {x1 , x 2 ,..., x  (n ) } thỏa mãn xx �1(mod n) (x, x gọi là nghịch đảo modunlo n) và nếu x �y thì x �y . Chứng minh: Vì x {x1, x2, x3,…, x(n)} nên x nguyên tố cùng nhau với n, do đó {xx 1, xx2, xx3,…, xx(n)} là một HTDĐĐ modulo n. Suy ra tồn tại duy nhất i {1, 2, …, x(n)} thỏa mãn xxi  1 (modn). Trong nhận xét trên có thể tổng quát hơn: Cho {x 1, x2, x3,…, x(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 7 thuộc {x1, x2, x3,…, x(n)} luôn tồn tại duy nhất x thuộc {x1 , x 2 ,..., x (n ) } thỏa mãn xx �a(mod n) và nếu x �y thì x �y . 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 p 1 luôn có a �1(mod p) . 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. p 1 p 1 k 1 k 1 Suy ra �ka ��k(mod p)  � (p�1)!a p1 (p 1)!(mod p) a p1 1(mod p) Nhận xét: Với cách chứng minh tương tự ta có định lí sau đây. Định lí 2 (Euler) 8 Nếu số nguyên a nguyên tố cùng nhau với số nguyên dương n thì a  (n ) �1(mod n) . Định lí 3 Phương trình đông dư ax �b(mod n) 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ử {x 1, 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 ax �b(mod n) . ax � ��� b(mod n) a x d b n (mod ) d d a �a n � d = (a,n) � � ; � 1  x d �d d � Giả sử x0 là nghiệm của b n (mod ) có 1 nghiệm duy nhất. d d a b n kn x � (mod )  x 0  (0 �k �d) là nghiệm d d d d của ax �b(mod n)  ax �b(mod n) có đúng d nghiệm. 9 Định lí 4 (Wilson) Số nguyên dương p là số nguyên tố nếu và chỉ nếu (p  1)! �1(mod p) . Chứng minh: + Giả sử (p  1)! �1(mod p) , 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 x �{1,2,3,...,p  1} luôn tồn tại duy nhất x �{1,2,3,...,p  1} thỏa mãn xx �1(mod p) . x �1(mod p) x  p 1 � � x 2 �1(mod p) � � �� x �1(mod p) x 1 � � Do đó: {2, 3, …, p – 2} chia thành p3 cặp nghịch đảo. Suy ra 2 (p  1)! �1(mod p) . 10 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 (22016  2) và {x1 , x 2 ,..., x  (n ) } là HTDTG modulo n. Chứng minh rằng: x12015  x 2015  ...  x 2015 n. 2 (n ) M Lời giải: Từ giả thiết suy ra (2, n) = 1, do đó {2x1 , 2x 2 ,..., 2x (n ) } là HTDTG modulo n.  2x1  2015   2x 2  2015  ...   2x (n)  2015 �x12015  x 22015  ...  x 2015 (n) (mod n) 2015 2015 �  x12015  x 2015  ...  x 2015  1 Mn � x12015  x 2015  ...  x 2015  1, n)  1 ) 2 (n )   2 2  (n ) (vì (2 Bài toán 2 11 Cho số nguyên tố p thỏa mãn p �1(mod4) . Chứng minh rằng với mỗi a thuộc {1;2;...; p 1 p 1 } luôn tồn tại duy nhất b thuộc {1;2;...; } thỏa mãn 2 2 a 2  b 2 �0(mod p) Lời giải: �p  1 � !. Đặt x  � � �2 � Ta có: { p 1 p  3 p 1 , ,..., 1,1, 2,..., } là một HTDTG modulo n. 2 2 2 p 1� p 1 � p 3�  ...  1 .1.2... �(p  1)! �1(mod p) � � � 2 � 2 � � 2 � � 2 Do p �1(mod4) nên x  � hay x 2  1 �0(mod p) . Với a thuộc {1;2;...; p 1 } luôn tồn tại a thuộc {1, 2,3,..., p  1} thỏa mãn 2 a �ax(mod p) . Nếu a thuộc {1;2;...; p 1 } thì lấy b là a ta có: 2 a 2  b 2 �a 2   ax  (mod p) �a 2 (x 2  1) �0(mod p) 2 Nếu a thuộc {   2 p 1 ,..., p  1} thì lấy b là p  a ta có: 2 b 2 � a (mod p) � a 2  b 2 �a 2   ax  (mod p) �a 2 (x 2  1) �0(mod p) 2 Bài toán 3 Cho số nguyên tố p thỏa mãn p �2(mod3) . 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 n �m3 (mod p) . 12 Lời giải: Ta chứng minh: Nếu {x1, x2, x3,…, xp} là một HTDĐĐ modulo p thì {x13 , x 32 , x 33 ,..., x 3p } là một HTDĐĐ modulo p. 3 Thật vậy: x 3  y� (mod p) (x 3 ) p2 3 (y3 ) p2 3 (mod p) x p 2 y p 2 (mod p) + x Mp � y Mp y Mp + x Mp  � x p 1 y3 (mod p) Vậy x 3 � y p 1 (mod p) x x y(mod p) 3 3 3 3 y(mod p) . Suy ra {x1 , x 2 , x 3 ,..., x p } là một HTDĐĐ modulo p. 3 3 3 3 Vì {x1 , x 2 , x 3 ,..., x p } 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 n �m3 (mod p) . Bài toán 4 Cho số nguyên tố p lớn hơn 3 và đa thức P(x) = 1 + 2x + 3x 2 +…+ 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: 13 P(x)  1  2x  3x 2  ...  px p 1 � (x  1)P(x)  x p  1  x(x p 1  1)  ...  x p 1 (p  1)  px p  (1  x  x 2 ...  x p 1 ) � (x  1)2 P(x)  px p (x  1)  x p  1 � (x  1) 2 P  x  �1  x(mod p)  P(1)  p(p  1) �0(mod p) 2 � x  1(mod p) P(x) 0(mod p)  x, y �1(mod p) � (1  x)P(x) �(1  y)P (y)(mod p) P(x) � P(y)(mod p) x y(mod p) 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 a �x 2 (mod 2k ) . Lời giải  a �x 2 (mod 2k ) , a lẻ, k �3 � x lẻ �a  Với a �1(mod 8) , suy ra tồn tại n nguyên dương sao cho a = 8n + 1. x2 1(mod 8) . + k = 3: Chọn x = 1. + k > 3: Nhận xét: Nếu x chạy qua một HTDĐĐ modulo 2 m thì 2x2+x cũng chạy qua một HTDĐĐ đầy đủ modulo 2m (m nguyên dương). Thật vậy: 2x 2  x �2y 2  y(mod 2m ) � (x  y)(2x  2y  1) �0(mod 2 m ) � ���x � y 0(mod 2m ) x y(mod 2 m ) . 14 Do đó: Tồn tại t nguyên thỏa mãn: n �2t 2  t(mod 2k 3 ) � 8n  1 �(4t  1)2 (mod 2k ) Suy ra a �x 2 (mod 2k )(x  4t  1) . Kết luận: a thỏa mãn a �1(mod 8) . Bài toán 6 Cho số nguyên tố p lớn hơn 3. Chứng minh rằng: p 1 1 a)  (p-1)! � 2 Mp i 2 i 1 p 1 1 i 1 i 2 b) (p-1)!� Mp Lời giải: Nhận xét: Với mỗi x �{1,2,3,...,p  1} luôn tồn tại duy nhất x �{1,2,3,...,p  1} thỏa mãn xx �1(mod p) . p 1 p 1 Do đó:  (p-1)! �2 �� i  i 2 i 1 p 1 1 i 1 i 1 i 1 2 p 1  �i 2 �0(mod p) hay  (p-1)! i 1 2 p 1 1 �i i 1 2 Mp . p 1 p 1 � 1 1 � 1  p(p-1)! � � i p i� i 1 � i 1 i(p  i) 2 (p-1)!�  (p-1)!��  p 1 p 1 p 1 p 1 1 1 (p-1)!� ��i(p  i) ��i 2 �0(mod p) � (p-1)!� Mp 2 i 1 i(p  i) i 1 i 1 i 1 i Bài toán 7 15 Cho số nguyên dương n lẻ, A  {k Σ N|1 k  n, (n, k)  (n, k  1)  1} . Chứng minh rằng: �a �1(mod n) a�A 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 x thuộc A thỏa mãn xx �1(mod n) và x  x khi và chỉ khi x = 1. Thật vậy: Giả sử {x1 , x 2 ,..., x ( n ) } là một HTDTG modulo n, 0  x i  ni  1, n . Vì x �A � (x, n)  1 � {xx1 , xx 2 ,..., xx (n ) } là một HTDTG modulo n. Do đó tồn duy nhất x thuộc {x1 , x 2 ,..., x (n ) } thỏa mãn xx �1(mod n) . Ta có: xx �1(mod n) � (x  1)x �x  1(mod n) � (x  1, n)  1 � x �A x  x � (x  1)(x  1) �0(mod n) � x  1 �0(mod n) � x  1 . A 1 Từ nhận xét trên suy ra A lẻ và A \ {1} chia thành cặp nghịch đảo theo 2 modulo n. Từ đó ta có điều phải chứng minh.    Nhận xét: Với n  p1 p2 ...p k ( pi là các số nguyên tố phân biệt), ta có 1 k A  n �(1  i 1 2 k 2 ). pi Bài toán 8 Cho số nguyên tố p thỏa mãn p �1(mod8) . Chứng minh rằng: a) 2 p 1 2 �1(modp) b) Tồn tại số nguyên a thoả mãn a 2 �2(modp) 16 Lời giải: a) Vì p �1(mod8) nên p có dạng 8k + 1 (k nguyên dương). �p  1 � !  (2.4...4k)(1.3...(4k  1)) �(2.4...4k)  (1  p)(3  p)...(4k  1  p)  � � �2 � �(1) 2k 2.4...(8k)  24k .1.2...(4k)  2 Suy ra 2 p 1 2 p 1 2 �p  1 � !(mod p) � � �2 � �1(modp) . b) Nhận xét: Với mỗi x �{1,2,3,...,p  1} luôn tồn tại duy nhất x �{1,2,3,...,p  1} thỏa mãn xx �2(mod p) . Nếu không tồn tại x thuộc {1,2,3,...,p  1} sao cho x 2 �2(modp) thì {1,2,3,...,p  1} được chia thành 2 p 1 2 p 1 tập {x, x } thỏa mãn xx �2(mod p) . Suy ra 2 �(p  1)! �1(modp) , 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 p �1(mod 4), (a,p)  1 . Tính: p 1 2 �ak 2 � � � � k 1 �p Lời giải Nhận xét: Với x, y nguyên thỏa mãn x 2  y 2 �0(mod p) , (x, p) = 1 ta có �x 2 � �y 2 � � � � � 1 p p �� �x 2 ��y 2 � 0  , Thật vậy: � �� � 1 , p p �� 17 �x 2 � �y 2 � x 2  y 2 �x 2 � �y 2 � �x 2 � �y 2 � �x 2 � �y 2 �     �  � Z � � � � � � � � � 1 �p � �p � �p � �p � p p p p p ���������� Theo bài toán 2, với mỗi x thuộc {1;2;...; thuộc {1;2;...; p 1 } thỏa mãn x 2  x 2   p 1 2 Suy ra 2 p 1 2 p 1 } luôn tồn tại duy nhất x 2 �0(mod p) .   � 2 �a k 2 �� �ak � �ak � � �� p  1 � 2 �� � �� , � � � �� p p 2 k 1 �� k 1 � p � �� � � � 2 do đó p 1 2 �ak 2 � p  1 � � � 4 k 1 � p 18 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 P(x)  1  x x2 xp   ...  không có nghiệm nguyên. n  1 2n  1 pn  1 19 5. Cho dãy số (an) được xác định bởi a1  1, a n  a n 1  a �n �, n �N* � 2� � � . Chứng minh rằng dãy số (an) chứa vô hạn số nguyên chia hết cho 7. n n 1 6. Chứng minh rằng: C22n 1  C 22n M23n , M23n 1 � x� � 2x � � (p  1)x � �nguyên tố. � 7. Tìm x, y nguyên dương sao cho � � � � ...  � �y � �y � � y � 17 k � � �11 � i 1 � � 2015 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 20