ĐỒNG DƯ
A. Lý thuyết
I. Định nghĩa và các điều kiện:
a. Định nghĩa:
Cho m \[\in N\]*; a,b \[\in \] Z. Nếu a và b khi chia cho m có cùng số dư ta nói: a và b đồng dư theo môđun m.
Kí hiệu: a \[\equiv \] b (mod m)
Hệ thức: a \[\equiv \] b (mod m) gọi là đồng dư thức.
Ví dụ: 19 \[\equiv \] 3 (mod 8); -25 \[\equiv \] 3 (mod 4)
b. Các điều kiện tương đương:
1- a \[\equiv \] b (mod m)
2- (a - b)\[\vdots \] m
3- \[\exists t\in Z\]sao cho: a = b + m.t.
II. Các tính chất
a. Quan hệ đồng dư là một quan hệ tương đương trên tập hợp Z có nghĩa là:
1- a \[\equiv \] a (mod m)
2- a \[\equiv \] b (mod m) => b \[\equiv \] a (mod m)
3- a \[\equiv \] b (mod m); b \[\equiv \] c (mod m) => a \[\equiv \] c (mod m)
b. Ta có thế cộng từng vế một với nhau theo cùng một môđun.
Cụ thể:
ai \[\equiv \] bi (mod m) i = \[\overline{1,n}\] => \[\sum\limits_{i=1}^{n}{{{(-1)}^{k}}{{a}_{i}}}\equiv \sum\limits_{i=1}^{n}{{{(-1)}^{k}}{{b}_{i}}}\] (mod m) \[\forall k\in N\]
c. Ta có thế nhân từng vế với nhau nhiều đồng dư thức theo cùng một môđun.
Cụ thể: ai \[\equiv \] bi (mod m);i = \[\overline{1,n}\]
=> \[\prod\limits_{i=1}^{n}{{{a}_{i}}}\equiv \prod\limits_{i=i}^{n}{{{b}_{1}}}\] (mod m); \[\forall k\in N\]
III. Các hệ quả
a. a \[\equiv \] b (mod m) => a \[\pm \] c \[\equiv \] b \[\pm \] c (mod m)
b. a + c \[\equiv \] b (mod m) => a \[\equiv \] b - c (mod m)
c. a \[\equiv \] b (mod m) => a + k.m \[\equiv \] b (mod m)
d. a \[\equiv \] b (mod m) => a.c \[\equiv \] b.c (mod m)
e. a \[\equiv \] b (mod m) => an \[\equiv \] bn (mod m) \[\forall n\in N\]
f. Cho f(x) = an xn + an-1 xn-1 + . . . +a1x + a0 \[\forall {{a}_{i}}\in Z\]. Nếu \[\alpha \]\[\] \[\equiv \]\[\beta \] (mod m) thì ta cũng có f(\[\alpha \])\[\equiv \] f(\[\beta \]) (mod m)
Đặc biệt: f(\[\alpha \]) \[\equiv \] 0 (mod m) thì ta cũng có: f(\[\alpha \] + k.m) \[\equiv \] 0 (mod m)
\[\forall k\in Z\]
g. Ta có thể chia cả hai vế của một đồng dư thức cho một ước chung của chúng nguyên tố với môđun.
Cụ thể là:
a.c \[\equiv \] b.c (mod m); ƯCLN (c; m) =1 => a \[\equiv \] b (mod m)
h.
1. Ta có thể nhân cả hai vế và môđun của một đồng dư thức với cùng một số nguyên dương.
Cụ thể là:
a \[\equiv \] b (mod m) => a.c \[\equiv \] b.c (mod m.c) \[\forall c\in {{N}^{*}}\]
2. Ta có thể chia cả hai vế và môđun của một đồng dư thức với cùng một ước dương của chúng.
Cụ thể là:
a \[\equiv \] b (mod m); 0 < c \[\in \] ƯC (a; b; m) => a/c \[\equiv \] b/c (mod m/c)
k. Nếu 2 số a và b đồng dư với nhau thêo nhiều môđun thì chúng đồng dư với nhau theo môđun là bội chung nhỏ nhất của môđun ấy.
Cụ thể là:
a \[\equiv \] b (mod mi), i = \[\overline{1,n}\] => a \[\equiv \] b (mod m).
Trong đó: m = BCNN(m1, m2 … mn)
l. Nếu a và b đồng dư với nhau theo môđun m thì chúng cũng đồng dư với nhau theo môđun là ước dương của m.
Cụ thể là:
a \[\equiv \] b (mod m); 0 < ∂ \[\in \] Ư(m) => a \[\equiv \] b (mod ∂ )
u. Nếu: a \[\equiv \] b (mod m) thì: ƯCLN( a; m) = ƯCLN( b; m).
B. Bài tập minh họa
Dạng 1: Tìm số dư của phép chia
|
Câu 1: Tìm số dư trong phép chia: 29455 – 3 chia cho 9 |
Giải:
Ta có: 2945 \[\equiv \] 2 (mod 9)
=> 29455 – 3 \[\equiv \] 25 – 3 (mod 9)
Mà 25 – 3 \[\equiv \] 2 (mod 9)
Vậy số dư của 29455 – 3 chia cho 9 là 2
|
Câu 2: Tìm số dư trong phép chia 109345 chia cho 14 |
Giải:
Ta có: 109 \[\equiv \] -3 (mod 14)
=> 109345 \[\equiv \] (-3)345 (mod 14)
Ta lại có: ( -3; 14 ) = 1
Hơn nữa: µ(14) = \[14.(1-\frac{1}{2})(1-\frac{1}{7})=6\]
Nên: (-3)6 \[\equiv \] 1 (mod 14) (theo đ ịnh l ý Ơle)
=> (-3)345 \[\equiv \] (-3)3 (mod 14)
Mặt khác: (-3)3 = -27 \[\equiv \] 1 (mod 14)
Vậy số dư trong phép chia 109345 chia cho 14 là 1
|
Câu 3: Tìm số dư trong phép chia: (19971998 + 19981999 +19992000 )10 chia cho 111 |
Giải:
Ta có: 1998 \[\equiv \] 0 (mod 111)
=> 1997 \[\equiv \] -1 (mod 111) và 1999 \[\equiv \] 1 (mod 111)
Nên ta có: 19971998 + 19981999 +19992000 \[\equiv \] 2 (mod 111)
(19971998 + 19981999 +19992000 )10 \[\equiv \] 210 (mod 111)
Mặt khác ta có: 210 = 1024 \[\equiv \] 25 (mod 111)
Vậy (19971998 + 19981999 +19992000 )10 chia cho 111 có số dư là 25
Dạng 2: Chứng minh chia hết
|
Câu 1: Chứng minh: 3100 – 3 chia hết cho 13 |
Giải:
Ta có: 33 = 27 \[\equiv \] 1 (mod 13)
=> 3100 = 3.399 \[\equiv \] 3.1 (mod 13)
=> 3100- 3 \[\equiv \] 0 (mod 13). Vậy 3100-3 chia hết cho 13
|
Câu 2: Chứng minh 62n + 1 + 5n + 2 chia hết cho 31 với mọi n là số tự nhiên |
Giải:
Ta có: 62 \[\equiv \] 5 (mod 31) => 62n \[\equiv \] 5n (mod 31)
Mặt khác: 6 \[\equiv \] - 52 (mod 31)
Nên: 62n + 1 \[\equiv \] -5n + 2 (mod 31)
Vậy 62n + 1 + 5n + 2 chia hết cho 31.
|
Câu3: Chứng minh \[{{2}^{{{3}^{4n+1}}}}+3\vdots 11\] với n là số tự nhiên |
Giải:
Ta có: µ(11) = 10; µ(10) = \[10(1-\frac{1}{2})(1-\frac{1}{5})\] = 4.
Áp dụng ĐL Ơle ta có: (3; 10) = 1 => \[{{3}^{\text{ }\!\!\mu\!\!\text{ (10)}}}\] \[\equiv \] 1 (mod 10)
<=> 34 \[\equiv \] 1 (mod 10) => 34n + 1 \[\equiv \] 3 (mod 10)
Đặt 34n + 1 = 10.k + 3 với k \[\in \] N.
Khi đó ta có: \[{{2}^{{{3}^{4n+1}}}}+3={{2}^{10.k+1}}+3\]
Áp dụng định lý Ơle ta có: (2; 11) = 1
Nên \[{{2}^{\text{ }\!\!\mu\!\!\text{ (11)}}}\] \[\equiv \] 1 (mod 11)
<=> 210 \[\equiv \] 1 (mod 11) => 210.k +3 \[\equiv \] 23 (mod 11)
=> 210.k +3 + 3 \[\equiv \] 23 +3 (mod 11) <=> \[{{2}^{{{3}^{4n+1}}}}+3\]\[\equiv \] 0 (mod 11)
Vậy \[{{2}^{{{3}^{4n+1}}}}+3\vdots 11\]
Dạng 3: Tìm chữ số tận cùng
|
Câu 1: Tìm 2 chữ số tận cùng của 20092010 |
Giải:
Ta có: 20092010 \[\equiv \] 92010 (mod 100)
Áp dụng định lý Ơle ta có: (9; 100) =1
Nên: \[{{9}^{\text{ }\!\!\mu\!\!\text{ (100)}}}\]\[\equiv \] 1 (mod 100). Mà µ(100) = \[100.(1-\frac{1}{2})(1-\frac{1}{5})=40\]
Hay: 940\[\equiv \] 1 (mod 100) => 92010 \[\equiv \] 910 (mod 100)
Mà 910 = 3486784401 \[\equiv \] 1 (mod 100).
Vậy 2 chữ số tận cùng của 20092010 là 01.
|
Câu 2: Tìm 2 chữ số tận cùng của \[{{9}^{{{9}^{9}}}}\] |
Giải:
Áp dụng định lý Ơle ta có: (9; 100) = 1; µ(100) = 40;
=> 940 \[\equiv \] 1 (mod 100). (*)
Mặt khác ta có: 92 \[\equiv \] 1 (mod 40) => 99 \[\equiv \] 9 (mod 40).
Đặt 99 = 40.k + 9 với k \[\in \] N (**)
Từ (*) và (**) suy ra: \[{{9}^{{{9}^{9}}}}\]\[\equiv \] 99 (mod 100)
Mà: 99 = 387420489 \[\equiv \] 89 (mod 100)
Vậy 2 chữ số tận cùng của \[{{9}^{{{9}^{9}}}}\] là 89
C. Bài tập rèn luyện
Bài 1 : Tìm số dư trong phép chia 20042004 cho 11
Bài 2 : Tìm số dư khi chia A = 19442005 cho 7
Bài 3 : Chứng minh rằng các số A = 61000 - 1 và B = 61001 + 1 đều là bội số của 7
Bài 4 : Tìm số dư trong phép chia 15325 - 1 cho 9
Bài 5 : Chứng minh rằng A = 7.52n + 12.6n chia hết cho 19
Bài 6 : Tìm dư trong phép chia 32003 cho 13.
Bài 7: Bạn Thắng học sinh lớp 6A đã viết một số có hai chữ số mà tổng các chữ số của nó là 14. Bạn Thắng đem số đó chia cho 8 thì được số dư là 4, nhưng khi chia cho 12 thì được số dư là 3.
a)Chứng minh rằng bạn Thắng đã làm sai ít nhất một phép tính chia.
b)Nếu phép chia thứ nhất cho 8 là đúng thì phép chia thứ hai cho 12 có ó dư là bao nhiêu ? Hãy Tìm số bị chia.
Bài 8: Tìm chữ số cuối cùng của các số :
a) 62009 , b) 92008 , c) 32009 , d) 22009
