Bồi dưỡng học sinh giỏi môn Toán Lớp 6 - Chuyên đề: Ứng dụng đồng dư thức vào giải một số dạng toán chia hết (Có đáp án)

Nội dung text: Bồi dưỡng học sinh giỏi môn Toán Lớp 6 - Chuyên đề: Ứng dụng đồng dư thức vào giải một số dạng toán chia hết (Có đáp án)

1. CHUYÊN ĐỀ: ỨNG DỤNG ĐỒNG DƯ THỨC VÀO GIẢI MỘT SỐ DẠNG TOÁN CHIA HẾT PHẦN I: NỘI DUNG I. NỘI DUNG. 1. Kiến thức cơ bản 1.1. Định nghĩa: - Nếu hai số nguyên a và b khi chia cho c (c 0) mà có cùng số dư thì ta nói a đồng dư với b theo môđun c; kí hiệu là a  b (mod c). - Như vậy: a  b (mod c) a – b chia hết cho c. - Hệ thức có dạng: a  b (mod c) gọi là một đồng dư thức, a gọi là vế trái của đồng dư thức, b gọi là vế phải còn c gọi là môđun. 1.2. Một số tính chất: Với a; b; c; d; m; là các số nguyên dương (Z+), ta luôn có: 1.2.1. Tính chất 1: + a  a (mod m). + a  b (mod m) b  a (mod m). + a  b (mod m) và b  c (mod m) thì a  c(mod m). 1.2.2. Tính chất 2: Nếu a  b (mod m) và c  d (mod m) thì: + a c  b d (mod m). + ac  bc (mod m).( c>0) + ac  bd (mod m). + an  bn (mod m). + (a+b)n  bn (mod a). + an +bn  ( a+b) (mod m).( n là số lẻ) a b m + Nếu d là một ước chung của a; b; m thì:  (mod ); d d d 1
2. 1.2.3. Tính chất 3: + Nếu a  b (mod m) và c Z+ thì ac  bc (mod mc). 1.3. Một số kiến thức liên quan: Trong khi làm bài tập sử dụng đồng dư thức, ta nên chú ý tới các tính chất hay dùng sau đây: + Với mọi a, b Z+ (a b) và n là số tự nhiên: an – bn  a – b. + Trong n số nguyên liên tiếp (n 1) có một và chỉ một số chia hết cho n. + Lấy n + 1 số nguyên bất kì (n 1) đem chia cho n thì phải có hai số khi chia cho n có cùng số dư; (Theo nguyên lí Đirichlet). + Tìm m chữ số tận cùng của số A là tìm số dư khi chia A cho 10m. 2. ỨNG DỤNG ĐỒNG DƯ THỨC VÀO GIẢI TOÁN. 2.1 DẠNG 1: CHỨNG MINH CHIA HẾT. Bài 1: Chứng minh rằng: A = 7.52n +12.6n chia hết cho 19 HD: Cách 1: Thêm bớt 7.6n, ta được A = 7.25n - 7.6n +19.6n = 7.(25n - 6n) +19.6n Vậy A 19 Ta có: A = 7.25n +12.6n Vì 25n  6n (mod19). => A  7.6n +12.6n (mod19) => A  19.6n (mod19) => A  0 (mod19) Đối với một số bài toán lớp 8 nếu ta sử dụng đến hằng đẳng thức: an bn a b với n N an bn a b với ( n N ; n lẻ) Thì ta có thể giải được một cách dễ dàng, tuy nhiên với học sinh lớp 6 thì chưa thể sử dụng những hằng đẳng thức đó. Vì vậy, ta có thể sử dụng Đồng dư thức để có được lời giải phù hợp với trình độ của học sinh lớp 6. Bài 2: ( Sách Phát triển toán 8 tập 1).Chứng minh rằng: a) A = 22225555 + 55552222 chia hết cho 7. 2
3. b) B 19611962 19631964 19651966 2 chia hết cho 7. HD: Cách 1: a) Ta có A 55552222 42222 22225555 45555 45555 42222 Mà 55552222 42222  5555 4 55552222 42222 7 Tương tự: 22225555 45555 7 1111 1111 45555 42222 45 42  45 42 45555 42222 7 Vậy A = 22225555 + 55552222 chia hết cho 7. b) B 19611962 19631964 19651966 27 Sử dụng tính chất: a b n khi chia cho a có số dư là b. Ta có B (1960 1)1962 (1960 3)1964 (1965 2)1966 2 B (7m 1)1962 (7n 3)1964 (7 p 2)1966 2 B 7q 1 31964 21966 2 B 7q 9.27654 2.23.655 3 B 7r 9 2 3 B 7r 147 Cách 2: a) Xét số dư của 22225555 khi chia cho 7. Ta có: 2222  3 (mod 7) (1) => 22224  34 (mod 7) => 22224  81 (mod 7) Mà 81  4 (mod 7) => 22224  4 (mod 7) (2) Nhân vế với vế (1) và (2) ta được 22225  3.4 (mod 7) => 22225  5 (mod 7) =>22225555  51111 (mod 7) (3) + Tương tự: 55552222  21111 (mod 7) (4) Cộng vế với vế (3) và (4) ta có: A  21111 + 51111 (mod 7) (5) 3
4. Mặt khác: 21111 + 51111  (2 + 5) (mod 7)  0 (mod 7) ( Tính chất 2) (6) Từ (5) và (6) ta được: A  0 (mod 7) Vậy: A = 22225555 + 55552222 chia hết cho 7 b) Ta có: Ta có: 1961  1 (mod 7) => 19611962  1 (mod 7) 654 Tương tự:19631964  31964 mod 7  9. 33 mod 7  9.27654 mod 7  2 mod 7 655 19651966  2 1966 mod 7  2. 23 mod 7  2.8655 mod 7  2 mod 7 B 1 2 2 2 mod 7  0 mod 7 Vậy: B 19611962 19631964 19651966 27 Bài 3: Chứng minh rằng: Với mọi số tự nhiên n thì số B = 42n+1 + 3n+2 luôn chia hết cho 13. HD: Cách 1: Ta có: B 4.16n 9.3n 4.16n 9.3n 4.3n 4.3n 4.(16n 3n ) 13.3n 16n 3n 13 Vì B13 n 13.3 13 Cách 2: Với bài toán trên ta có thể sử dụng kỹ thuật thêm bớt để chứng minh, nhưng đối với học sinh lớp 6 thì chưa được học kỹ thuật đó. Nên ta có thể sử dụng Đồng dư thức để chứng minh. + Ta xét số dư của 42n+1 khi chia cho 13 Ta có: 42 = 16  3 (mod 13) => 42n  3n (mod 13) => 42n+1  4.3n (mod 13) Hay 42n+1  4.3n (mod 13) (1) + Ta xét số dư của 3n+2 khi chia cho 13 4
5. Ta có: 32 = 9  - 4(mod 13) Mà 3n  3n (mod 13) => 32.3n  - 4.3n (mod 13) => 3n+2  - 4.3n (mod 13) (2) Từ (1) và (2), cộng vế với vế, ta được B  0 (mod 13). Vậy B = 42n+1 + 3n+2 luôn chia hết cho 13 với mọi n N. Bài 4: Chứng minh rằng với mọi n N. a) A = 52n+1 + 2n+4 + 2n+1 chia hết cho 23 b) B = 11n+2 + 122n+1 chia hết cho 133 HD: Cách 1: a) Ta có: A 5.25n 16.2n 2.2n 5.25n 18.2n 5 25n 2n 23.2n 25n 2n 23 Vì A23 n 23.2 23 b) B 121.11n 12.144n 12 144n 11n 133.11n Từ đây ta có được B133 Cách 2: a) A = 52n+1 + 2n+4 + 2n+1 chia hết cho 23 Ta có: A = 25n .5 + 2n.16 + 2n.2 Vì 5.25n  5.2n (mod23) => A  5.2n + 2n.16 + 2n.2 (mod23)  23.2n (mod23)  0 (mod23) Vậy A = 52n+1 + 2n+4 + 2n+1 chia hết cho 23. b) B = 11n+2 + 122n+1 chia hết cho 133 Tương tự câu a) ta có: B  121.11n + 12.144n (mod133) 121.11n + 12.11n (mod133)  0(mod133) Vây B = 11n+2 + 122n+1 chia hết cho 133. 5
6. Bài 5: ( lớp 8). Chứng minh rằng với mọi số nguyên n > 1: A = nn – n2 + n – 1 luôn chia hết cho đa thức B = (n – 1)2 HD: Ta có: Với n = 2 thì A = 1, B = 1, rõ ràng A chia hết cho B. Với n > 2, ta biến đổi A như sau: A = nn – n2 + n – 1 = n2(nn-2 - 1) + (n - 1) = n2(n - 1)(nn-3 + nn-4 + + 1) + (n - 1) = (n – 1)(nn-1 + nn – 2 + + n2 + 1) Mặt khác: n  1 (mod n – 1) nk  1 (mod n – 1),  k N Từ đó: nn-1 + nn-2 + + n2  n – 2 (mod n – 1) Nên: nn-1 + nn – 2 + + n2 + 1  n – 1 (mod n – 1) => nn-1 + nn – 2 + + n2 + 1  0 (mod n – 1) (1) => (n – 1)(nn-1 + nn – 2 + + n2 + 1)  0 (mod (n – 1)2) => A = (n – 1)(nn-1 + nn – 2 + + n2 + 1) chia hết cho (n – 1)2. Vậy: A = nn – n2 + n – 1 luôn chia hết cho đa thức B = (n – 1)2. Với một số bài toán có luỹ thừa tầng thì khi chúng ta sử dụng Đồng dư thức thì sẽ giúp cho học sinh có được cách giải tổng quát cho dạng toán đó. Chẳng hạn Bài 6: Chứng minh rằng: 2n a)A 22 57 n 0 2004n b)A 19242003 1920124 n 0 4n 1 4n 1 c)A 32 23 522 n 0 2n d) A = 22 1013 HD: a) Vì 23 8 1 mod 7 . Nên ta đi tìm số dư của 22n cho 3. Thật vậy: 22n 4n 1 mod3 22n 3k 1 => A 23k 1 5 2.8k 5  2 5 mod 7  0 mod 7 . 2n => A 22 57 n 0 6
7. b) Ta có 124 = 4.31 Dễ thấy B4 . Ta chứng minh A31 1924  2 mod31 n 20032004 Vì nên B  2 2 mod31 1920  2 mod31 Vì 25 32 1 mod31 n Từ đây ta xét M 20032004 chia cho 5 có số dư là bao nhiêu n Vì 20044 nên ta đặt 2004n 4k và M 20032004 20034k Mà 2003  3 mod5 => 20034k  34k mod5  81k mod5 1 mod5 => M = 5m+1 => B  25m 1 2 mod31  2.32m 2 mod31  2 2 mod31  0 mod31 Vậy B124 4n 1 4n 1 c) C 32 23 522 n 0 Vì 22 = 2.11 và C2 nên ta chứng minh A11 Ta có 310 1 mod11 (Định lý Fecma) Từ đây ta xét N 24n 1 và P 34n 1 chia cho 10 có số dư là bao nhiêu. * N 24n 1 2.16n  2.6n mod10  2. ...6 mod10  2 mod10 => N 24n 1 10k 2 4n 1 2k => 32 310k 2  9. 35 mod11  9 mod11 ( vì 35 1 mod11 ) Tương tự: P 34n 1 10m 3 4n 1 23 210k 3  8.322k mod11  8. 1 2k mod11  8 mod11 Vậy C  (9 8 5) mod 22  0 mod 22 . 2n d) D=22 1013 Ta có 212 1(mod 13) (Định lý Fecma) Từ đó bài toán được đưa về tìm số dư khi chia 22n cho 12 Ta có: 22n 0(mod 4) => 22n =4k ( k N) => 22n = 4n  1(mod 3) => 22n =3m+1 ( m N) => 22n = 12m+4 => D = 212m+4 +10 = 16.(26)2m + 10  3+10(mod 13) 7
8.  0(mod 13). Vậy D chia hết cho 13 với mọi n. Sau khi đã hình thành cho các em một số kỹ năng nhất định qua dạng toán chứng minh trên thì với cách biến đổi tương tự các em sẽ không gặp quá nhiều không khi gặp một số dạng toán sau: 2.2 DẠNG 2: TÌM SỐ TỰ NHIÊN TRONG PHÉP CHIA Bài 1: Tìm số dư trong phép chia số A = 19932014 cho 3. HD: Cách 1: Nếu thêm bớt 1 vào số 19932014 thì ta có lời giải bài toán một cách dễ dàng: A= 19932014-1+1 Vì A = 19932014 11992 19932014 13 Suy ra A chia cho 3 dư 1. Cách 2: Ta có: 1993  1 (mod 3) => 19932014  12014 (mod 3)  1 (mod 3) Vậy số 19932014 khi chia cho 3 thì dư 1. Bài 2: Tìm số dư của A = 776776 + 777777 +778778 khi chia cho 3 và cho 5 HD: Cách 1: Ta có: A 776776 2776 777777 778778 1 2776 1 776776 2776 3 Vì 777777 3 nên ta phải tìm số dự khi chia 2776 1 cho 3 778778 13 Thật vậy: 2776 1 2.2775 2 1 2 2775 1 3 2 Vì 2 2775 1 33 nên A chia 3 dư 2 Tương tự: A chia 5 dư 1 Cách 2: + Trường hợp 1: Tìm số dư của A = 776776 + 777777 +778778 khi chia cho 3. Ta có: 776  2 (mod 3) => 776776  2776 (mod 3)  4338 (mod 3)  1338 (mod 3)  1 (mod 3) 8
9. Tương tự: 777777 0 (mod 3) 778778 1(mod 3) => A = 776776 + 777777 +778778 1+0+1(mod 3)  2 (mod 3) Vậy A = 776776 + 777777 +778778 chia cho 3 dư 2. + Trường hợp 2: Tìm số dư của A = 776776 + 777777 +778778 khi chia cho 5. Ta có: 776  1 (mod 5) => 776776  1776 (mod 5)  1(mod 5). Ta có : 777 2 (mod 5) 777777  2777(mod 5) (24)194.2(mod 5) 16 194.2(mod 5)2(mod 5) 778778 3(mod 5) => A = 776776 + 777777 +778778 1+2+3(mod 5)  1 (mod 5) Vậy A = 776776 + 777777 +778778 chia cho 5 dư 1. Bài 3: Tìm số tự nhiên nhỏ nhất khi chia cho 5 dư 1, chia cho 7 dư 5. HD: Cách 1: Gọi n là số tự nhiên chia 5 dư 1 và chia 7 dư 5. Vì n không chia hết cho 35 nên n = 35k + r ( k, r N, r < 35). Trong đó r chia 5 dư 1, chia 7 dư 5. Số nhỏ hơn 35 chia 7 dư 5 và chia 5 dư 1 là 5; 12; 19; 26; 33. Trong các số trên chỉ có 26 là số chia cho 5 dư 1. Vậy r = 26. Cách 2: Ta có: n 15 n 1 105 n 95 n 935 n 57 n 5 147 n 97 Số n nhỏ nhất có tính chất trên là n = 26. Cách 3: Gọi số tự nhiên cần tìm là A, ta có: A  1 (mod 5); A  5 (mod 7) Từ A  5 (mod 7) => A = 7k+5 ( k N). (1) => 7k+5  1 (mod 5) => 2k  1 (mod 5) => 2k+4 1+4(mod 5) => 2k + 4  0(mod 5) => k + 2  0(mod5) => k = 5m -2 ( m N) (2) 9
10. Thay (2) vào (1), ta được: A = 7(5m-2)+5 = 35m - 9 => A  -9 (mod 35)  26 (mod 35) Vậy số A =26. Nhận xét: Nếu sử dụng Đồng dư thức cho loại toán này thì ta có thể giải được các bài toán có nhiều số chia hơn, hoặc các số chia có giá trị lớn một cách dễ dàng hơn, đồng thời ta có được cách giải rõ ràng cho dạng toán này. Bài 4: Tìm số tự nhiên n có bốn chữ số sao cho chia n cho 131 thì dư 112, chia n cho 132 thì dư 98. HD: Cách 1: Ta có 131x+112 = 132y+98 => 131x = 131y +y-14 =>y - 14131 => y = 131k + 14 k N => n = 132(131k+14)+98 = 132.131k+1946 Vì n có 4 chữ số nên n = 1946. Cách 2: Từ 131x = 131y + y -14 => 131(x-y) = y-14. Nếu x > y thì y- 14 131 => y 145 => n có nhiều hơn 4 chữ số. Do đó x = y, suy ra n = 1946 Cách 3: Ta có n = 131x+112 nên 132n = 132.131x +132.112 (1) Mặt khác n = 132y + 98 131n = 131.132y + 131.98 (2) Từ (1) và (2) suy ra: 132n -131n = 131.132(x –y) + 1946 => n =1946. Cách 4: Gọi số tự nhiên cần tìm là n, ta có n  112(mod 131); n  98 (mod 132) Từ n  98 (mod132) => n = 132k+98 (k N) (1) => 132k+98  112 (mod 131) => k + 98 + 33 112+33(mod 131) => k  14(mod 131) => k = 131m +14 ( m N) (2) Thay (2) vào (1), ta được: n = 132(131m + 14) + 98 = 131.132m +1946 10