Năm học 2009 - 2010
CHUYÊN ĐỀ SỐ HỌC
CHUYÊN ĐỀ I :
PHÉP CHIA CÓ DƯ – ĐỒNG DƯ THỨC
I. Phép chia hết, phép chia có dư
1. Cho a, b
∈
Z, b > 0 ; khi chia a cho b ta có:
a) a
M
b (hay a \ b) khi và chỉ khi có số nguyên q sao cho a = b.q
b) a không chia hết cho b : khi đó chia a cho b ta được thương gần đúng là q và số dư r (0 < r
< b) ; ta viết : a = b.q + r (với 0 < r < b)
Chú ý :
- Khi chia một số nguyên a cho một số nguyên b > 0 thì số dư là một trong b số từ 0 đến b – 1.
- Trong trường hợp a không chia hết cho b (r ≠ 0). Ta có thể lấy số dư là số âm r’ với r’ = r – b (do
đó
r '
< b).
Ví dụ : Chia 23 cho 3, ta có thể viết :
23 = 3.7 + 2 (7 gọi là thương gần đúng thiếu, vì 3.7 = 21 < 23)
23 = 3.8 + (–1) (8 gọi là thương gần đúng thừa, vì 3.8 = 24 > 23)
- Coi số dư có thể là số âm như trên, thì mọi số nguyên a khi chia cho 2, 3, 4, … , b có dạng :
a = 2k ; a = 2k + 1 hoặc a = 2k ; a = 2k – 1 (k
∈
Z)
a = 3k ; a = 3k ± 1 (k
∈
Z)
a = 4k ; a = 4k ± 1 ; a = 4k + 2 hoặc a = 4k ; a = 4k ± 1 ; a = 4k – 2 (k
∈

a và m
M
b
⇔
m
M

[ ]
a, b
Hai số được gọi là nguyên tố cùng nhau khi và chỉ khi (a,b) = 1
Ta chứng minh được :
[ ]
a, b
=
ab
(a,b)

Từ đó :
[ ]
a, b
= ab nếu (a,b) = 1
3. Thuật toán Ơclit (Tìm ƯCLN dựa vào định lí phép chia có dư) :
Năm học 2009 - 2010
Thuật toán Ơclit dựa vào hai mệnh đề sau :
1) a = bq
⇒
(a,b) = b
2) a = bq + r (r ≠ 0)
⇒
(a,b) = (b,r)

+
+
không thể giản ước được.
(Đề thi học sinh giỏi toán cấp II toàn quốc năm 1970)
Giải : 21n + 4 = (14n + 3).1 + 7n + 1
⇒
(21n + 4,14n +3) = (14n + 3,7n + 1)
14n + 3 = (7n + 1).2 + 1
⇒
(14n + 3,7n + 1) = (7n +1,1) = 1
Vậy : (21n + 4,14n +3) = 1
Hai số 21n + 4 và 14n + 3 có ước chung lớn nhất bằng 1 nên phân thức
21n 4
14n 3
+
+
không thể giản ước
được.
4. Một số tính chất, định lí quan trọng thường được dùng để giải một số bài toán chia hết :
4.1) Mọi số nguyên a ≠ 0 đều chia hết cho chính nó (a
∈
Z ; a ≠ 0
⇒
a
M
a)
4.2) a
M
b và b
M

4.8) a
M
b và a ≠ b
⇒
b không chia hết cho a
4.9) a
M
c và b
M
c
⇒
(a + b)
M
c ; (a – b)
M
c
4.10) a
M
c và b
M
c
⇒
(am + bn)
M
c
4.11) S = (a + b + c + d)
M
m và a,b, c
M
m thì d

b
Năm học 2009 - 2010
4.15) (ca,cb) = c(a,b) ;
a b (a, b)
,
c c c
 
=
 ÷
 
4.16) c
M
a và c
M
b ; (a,b) = 1
⇒
c
M
ab
4.17) Với hai số nguyên a, b và b > 0 thì bao giờ cũng tìm được cặp số nguyên duy nhất (q;
r) sao cho a = bq + r (0 ≤ r < b).
5. Các bài toán chia hết và phương hướng tìm lời giải :
Cho biểu thức A(n), phụ thuộc vào số n (n
∈
Z hay n
∈
Z’ một tập con của Z)
5.1) Để chứng minh A(n) chia hết cho một số nguyên tố p, có thể xét mọi trường hợp về số dư
khi chia n cho p (0,
±

M
5
⇒
A(n)
M
5
Với r = ±2 thì (n
2
+ 1) = [(5k ± 2)
2
± 1] = 25k
2
± 10k + 5
M
5
⇒
A(n)
M
5
5.2) Để chứng minh A(n) chia hết cho hợp số m, nói chung ta nên phân tích m ra thừa số. Giả
sử
m = p.q
Nếu p,q là số nguyên tố hay (p,q) = 1 thì ta tìm cách chứng minh A(n)
M
p và A(n)
M
q. Từ đó
suy ra A(n)
M
pq = m.

hạng và chứng minh mỗi số hạng chia hết cho m.
Ví dụ : Chứng minh rằng lập phương của một số nguyên bất kì (n > 1) trừ đi 13 lần số nguyên
đó thì luôn chia hết cho 6. (Đề thi học sinh giỏi toán cấp II toàn quốc năm 1970)
Giải : Ta cần chứng minh : A(n) = n
3
– 13n
M
6
Ta có A(n) = n
3
– 13n = n
3
– n – 12n = n(n
2
– 1) – 12n = n(n – 1)(n + 1) – 12n.
Vì n(n – 1)(n + 1) là tích của ba số nguyên liên tiếp nên chia hết cho 6 và 12n chia hết cho 6
nên : A(n) = n
3
– 13n
M
6.
Năm học 2009 - 2010
5.4) Để chứng minh một tổng nào đó không chia hết cho m, có thể chứng minh một số hạng
nào đó của tổng không chia hết cho m còn tất cả các số hạng còn lại chia hết cho m.
Ví dụ : Chứng minh rằng với mọi số n lẻ : n
2
+ 4n + 5 không chia hết cho 8.
Giải : Đặt n = 2k + 1 (n lẻ) ta có :
n
2

+ 1)(n
2
+ 4)
M
5 với mọi số nguyên n.
Giải : n chia cho 5 dư 0
⇒
n
M
5
n chia cho 5 dư ±1
⇒
n
2
chia cho 5 dư (±1)
2
= 1
⇒
n
2
+ 4
M
5
n chia cho 5 dư ±2
⇒
n
2
chia cho 5 dư (±2)
2
= 4

3
– 1 là bội của 7.
5.6) Có thể dùng các công thức sau :
Ta đã biết : a
2
– b
2
= (a – b)(a + b)
a
3
– b
3
= (a – b)(a
2
+ ab + b
2
)
a
3
+ b
3
= (a + b)(a
2
– ab + b
2
)
Một cách tổng quát :
a
n
– b

n – 1
Do đó, theo (1) và (2) :
a
n
– b
n
chia hết cho a – b (nếu a ≠ b) với n bất kì.
a
n
– b
n
chia hết cho a + b (nếu a ≠ -b) với n chẵn.
Theo (3) : a
n
+ b
n
chia hết cho a + b (nếu a ≠ -b) với n lẻ.
Ví dụ : a) Chứng minh rằng 2
4n
– 1
M
15
Giải : Ta có : 2
4
= 16, do đó : 2
4n
– 1 = 16
n
– 1 = (16 – 1).M = 15.M
b) Chứng minh rằng 2

o
)
Bước 2 : Giả sử mệnh đề đúng với n = k > 1 (hoặc k > n
o
) ; (Ta gọi là giả thiết quy nạp). Rồi
chứng minh mệnh đề đúng với n = k + 1.
Bước 3 : Kết luận mệnh đề đúng với mọi số tự nhiên n.
Ví dụ : Chứng minh rằng 16
n
– 15n – 1
M
225.
Giải : Với n = 1 thì 16
n
– 15n – 1 = 16 – 15 – 1 = 0
M
225 (đúng)
Giả sử 16
k
– 15k – 1
M
225
Ta chứng minh : 16
k+1
– 15(k + 1) – 1
M
225.
Thật vậy : 16
k+1
– 15(k + 1) – 1 = 16.16

Ví dụ : Chứng minh rằng trong n + 1 số nguyên bất kì có 2 số mà hiệu chia hết cho n.
Giải : Lấy n + 1 số nguyên bất kì chia cho n thì có n + 1 số dư. Nhưng khi chia một số cho n thì sẽ có
n số dư từ 0 đến n – 1. Vậy trong n + 1 phép chia trên sẽ có 2 số có cùng số dư. Khi đó hiệu hai số
này chia hết cho n.
Bài tập áp dụng :
1) Chứng minh rằng : A = 75(4
1975
+ 4
1974
+ 4
1973
+ … + 4 + 5) + 25 chia hết cho 4
1976
.
Giải : A = 25.3(4
1975
+ 4
1974
+ 4
1973
+ … + 4
2
+ 4 + 1) + 25
A = 25.(4 – 1) (4
1975
+ 4
1974
+ 4
1973
+ … + 4

+ 50x
2
+ 24x
= x(x
4
+ 10x
3
+ 35x
2
+ 50x + 24)
= x[(x
4
+ 5x
3
+ 4x
2
) + (5x
3
+ 25x
2
+ 20x) + (6x
2
+ 30x + 24)]
= x[x
2
(x
2
+ 5x + 4) + 5x(x
2
+ 5x + 4) + 6(x