Chuyên đề Đồng dư - Bồi dưỡng HSG Toán 8

 ĐỒNG DƯ THỨC
A. Kiến thức
1. Định nghĩa: Nếu hai số nguyên a và b khi chia cho số nguyên dương m có cùng số dư thì 
ta nói a đồng dư với b theo môđun m
Kí hiệu: a  b modm 
- Như vậy a  b modm a b m
- Hệ thức có dạng a  b modm gọi là một đồng dư thức
Trong đó, ta có: a là vế trái, b là vế phải, m là môđun
- Nếu a  0 modm thì am
*) Chú ý: Nếu a chia cho b dư r thì a  r modb 
2. Tính chất: Dựa vào a  b modm a b m
Với a,b,c nguyên, m là số nguyên dương, ta có: 
+) Tính chất 1: Ta có a  a(modm) (tính chất phản xạ)
+) Tính chất 2: Nếu a  b(modm) thì b  a(modm) (tính chất đối xứng)
+) Tính chất 3: Nếu a  b(modm);b  c(modm) a  c(modm) (tính chất bắc cầu)
+) Tính chất 4: Cộng hai vế của một đồng dư với cùng một số
 a c  b c modm 
Nếu a  b modm 
 a c  b c modm 
+) Tính chất 5: Cộng, trừ từng vế của nhiều đồng dư có cùng môđun
 a c  b d modm 
Nếu a  b modm ;c  d modm 
 a c  b d modm 
+) Tính chất 6: Nhân hai vế của một đồng dư với cùng một số
 ac  bc modm 
Nếu a  b modm , c Z 
 ac  bc modm.c 
+) Tính chất 7: Nhân từng vế của nhiều đồng dư có cùng môđun
Nếu a  b modm ;c  d modm ac  bd modm 
Mở rộng: Với a1,a2 ,...,an và b1,b2 ,...,bn là các số nguyên
 1 3753  3 mod13 376  3 mod13 
 12
Lại có: 26 12 mod13  1 mod13 26 1 mod13 276 16 mod13  3 mod13 
Do đó: 376 276  3 3 mod13 376 276  0 mod13 376 276 13
d) Ta có: 24  5 mod19 241917  51917 mod19 1 
Lại có: 14  5 mod19 141917  51917 mod19 2 
Từ 1 2 241917 141917  51917 51917 mod19  0 mod19 
Hay 241917 141917 chia hết cho 19
 405
e) Ta có: 25 1 mod31 25 1 mod31 22015 1 mod31 
 22015.24 1.24 mod31 22019 16 mod31 22019 15 16 15 mod31 22019 15  0 mod31 
hay 22019 15 chia hết cho 31.
f) Ta có: 2019  4 mod13 20192020  42020 mod13 
 679
Có: 43  1 mod13 ;2020 673.3 1 20192029  42020 mod13  43 .4 mod13  4 mod13 
 20192029 9  4 9 mod13  13 mod13  0 mod13 
Vậy 20192020 9 chia hết cho 13
 Bài 2: Chứng minh rằng
a) 1110 1 chia hết cho 100 b) 2015 1 chia hết cho 341
c) 19911997 19971996 chia hết cho 10 d) 29 299 chia hết cho 100
e) 13123456789 1 chia hết cho 183
f) 19791979 19811981 1982 chia hết cho 1980
 Lời giải
a) Ta có: 11  1 mod 4 1110 1 mod 4 1110 1 4 1 
 2
112  21 mod 25 112  4 mod 25 112  4 2 mod 25  9 mod 25 
 2
114.11  9.11 mod 25  99 mod 25 1 mod 25 115 1 mod 25 115 1 mod 25 
 1110 1 mod 25 1110 1 25 2 
 3 9
d) Ta có: 210 1024  1 mod 25 210  1 mod 25 290 1  0 mod 25 290 1 25 1 
mặt khác 29 4 2 
Từ 1 2 29 299 100
e) Ta có: 13 1 mod3 13123456789 1 mod3 13123456789 1 3 1 
 41152263
Lại có: 133 1 mod61 133 1 mod61 13123456789 1 61 2 
Mà 3,61 1 13123456789 1 183.
f) Ta có: 1979  1 mod1980 19791979  1 mod1980 1 
1981 1 mod1980 19811981 1 mod1980 2 ; 1982  2 mod1980 3 
Từ 1 2 3 19791979 19811981 1982  1 1 2 mod1982  0 mod1980 
Vậy 19791979 19811981 1982 chia hết cho 1980.
 Bài 3: Chứng minh rằng
a) 22002 4 chia hết cho 31
b) 22225555 55552222 chia hết cho 7
c) 2014200 256 chia hết cho 2016
 Lời giải
a) Ta có: 25 1(mod31);2002 5.400 2 22002 (25 )400.22 ;25 1(mod31)
 (25 )400 1400 (mod31)
 (25 )400.22 1.22 (mod31) 22002  4(mod31) 22002 4 chia hết cho 31 
b) Ta có: 2222  3(mod7) 22225  35 (mod7)  5(mod7) 22225555  51111(mod7) (1) 
Lại có: 5555  4(mod7) 55552  42  2(mod7) 55552222  51111(mod7) (2)
Từ (1)(2) 22225555 55552222  51111 21111(mod7) (3)
Mặt khác: 5  2(mod7) 51111  ( 2)1111  21111(mod7) 51111 21111  0(mod7) (4)
Từ (3)(4) 22225555 55552222 7
c) Ta có: 
 20143  2008(mod 2016);20142  4(mod 2016) 20145  20143.20142  2008.4 1984(mod 2016) 
 5 c) 555  2(mod7) 555222  2222 (mod7);23 1(mod7) (23 )74 1(mod7) 555222 1(mod7)
 222  2(mod7) 222555  ( 2)555 (mod7)
 3 3 185 555
Có: ( 2)  1(mod7) ( 2)  1(mod7) 222  ( 1)(mod7)
 A 1 1(mod7)  0(mod7)
d) Ta có: 123430  778(mod 2014) 12349  7783 1500(mod 2014)
 12347 15003 1234(mod 2014) 12343.123427  778.1234(mod 2014)
 123430 1234.1234.778 1388(mod 2014) (123430 1388)2014
 Bài 7: Sử dụng định lí Fermat nhỏ
 2 3 10
Chứng minh rằng: A 1010 1010 1010 ... 1010 57
 Lời giải
Vì 7 là số nguyên tố nên 7,10 1 nên theo định lý Fermat nhỏ ta có:
106 1(mod7) 106k 1k 1(mod7)
 n n n
 Với mọi số tự nhiên n khác 0 thì: 10 2 1000....022,3 (10 2)6 10  4(mod6)
 n 1
 n
Đặt 10n 6k 4(k N) 1010 106k 4 106k.104 1.14 (mod7) 104 (mod7) 1010 104 (mod7)
 2 3 10
1010 104 (mod7);1010 104 (mod7).......;1010 104 (mod7) A 10.104 5  0(mod7) A7
 Bài 8: Sử dụng định lí Fermat nhỏ
Chứng minh rằng: A 11331 21331 31331 ... 1331133111
 Lời giải
Vì 11 là số nguyên tố nên theo định lý Fermat nhỏ ta có: a11 11(mod11),a Z
 a121 (a11)11  a11  a(mod11) a1331 (a121)11  a11(mod11)  a(mod11) 
Áp dụng kết quả trên ta được: 
11331 21331 .... 13311331 1 2 .... 1331  886446  0(mod11) A11
 Bài 9:
 22
Chứng minh rằng: A (2222 22)3234
 Lời giải
 7 30 2.3.5 6.5;a5 a a(a4 1) a(a2 1)(a2 1) a(a 1)(a 1)(a2 1)
Ta có: 
 6
Ta cần chứng minh : a5  a(mod5)
+) Nếu a  0(mod5) a5  0  a(mod5)
+) Nếu a  1(mod5) a5  ( 1)5  a(mod5)
+) Nếu a  2(mod5) a5  ( 2)5  32  2  a(mod5)
Vậy a5  a(mod5) a p  a(mod p)
 Bài 13:
Chứng minh rằng: A 1n 2n 3n 4n 5 n 4(n N * )
 Lời giải
+) n 4k A 1 16k 81k ( 1)4k
+) n 4k 1 A 1 16k.2 81k.3 ( 1)4k .4 1 2 3 4 10  0(mod5)
+) n 4k 2 A 1 16k.22 81k.32 ( 1)4k .42 1 4 9 16  30  0(mod5)
+) n 4k 3 A 1 16k.23 81k.33 ( 1)4k .43 13 43 22 32  0(mod5)
Vậy A luôn chia hết cho 5 khi n không chia hết cho 4
 Bài 14:
Chứng minh rằng: A (25n 3 3n 2.5n )17,n N *
 Lời giải
Ta có: A 32n.8 9.3 n.5n 15n.8 9.15n 17.5n  0(mod17)
 Bài 15:
Chứng minh rằng: A nn n2 n 1B (n 1)2 ,n N,n 1
 Lời giải
Ta có: A nn n2 n 1 n2 (nn 2 1) (n 1)
+) Với n 2 luôn đúng
+) Xét với n 2
 9 b) Ta có: 189079 7 189079  0 mod7 1 
19456 mod7 19452015  62015 mod7  1 2015 mod7  1 mod7 2 
 2017 1 mod7 20172018 1 mod7 3 
Cộng 1 2 3 theo vế ta được: 
189079 19452015 20172018  0 1 1 mod7  0 mod7 189079 19452015 20172018 7
c) Ta có: 1961 1 mod7 19611962 1 mod7 1 
 654
1963  3 mod7 19631964  31964 mod7  33 .32 mod7  2 mod7 2 
 655
1965  5 mod7 19651966  51966 mod7  53 .5 mod7  5 mod7 3 
Cộng 1 2 3 theo vế ta được: 
1 2 5 mod7  2 mod7 19611962 19631964 19651966 2 chia hết cho 7.
 11 Chia hết cho 183.
f) Ta có: 22n 1  32n 1 mod5 22n 1 32n 1  32n 1 32n 1 mod5  0 mod5 
g) Ta có: 7.52n 7.25 n  7.6n mod19 7.52n 12.6n  7.6n 12.6n mod19 
 7.52n 12.6n 19.6n mod19  0 mod19 7.52n 12.6n chia hết cho 19.
 Bài 2:
 2004n
Chứng minh rằng 19242003 1920 chia hết cho 124 với mọi n là số nguyên dương
 Lời giải
 2004n
Đặt 19242003 1920 . Khi đó chứng minh được A chia hết cho 4
 2004n
Ta có 1924  2 mod31 A  22003 2 mod31 
 n
Mặt khác ta có 2004n 4 2004n 4k và 20032004 20034k với k là số nguyên dương.
Vì 2003  3 mod5 20034k  34k  81k 1 mod5 
 n n
Do đó 20032004 1 mod5 hay 20032004 5m 1 với m là số nguyên dương
 2004n m
Như vậy ta có 22003 25m 1 2. 25  2 mod31 
Điều này có nghĩa A  0 mod31 
Mà ta có 4,31 1 A chia hết cho 124 với mọi số nguyên dương n .
 13 Ta có n 1 mod n 1 nk 1 mod n 1 
Như vậy ta có nn 1 nn 2 ... n2  n 2 mod n 1 nn 1 nn 2 ... n2 1  n 1  0 mod n 1 
Điều này dẫn đến n 1 nn 3 nn 4 ... n 1  0 mod n 1 2 
Hay ta được A luôn chia hết cho B
 15