Nguyn Văn Tho Chuyên ñ S Hc  Phn I
1
Li nói ñu
S hc là mt phn r#t quan trng trong chương trình Toán ph* thông. Trong hu
h-t các ñ thi hc sinh gi0i thì bài S hc thư2ng xuyên xu#t hi4n và luôn là mt thách
th6c l7n ñi v7i hc sinh.
Hi4n nay, không còn h4 chuyên c#p Trung hc cơ s; nên các em hc sinh chuyên
Toán cũng không ñư>c hc nhiu v phn này nên thư2ng g?p r#t nhiu khó khăn khi gii
các bài toán ñó. Vì vAy, tôi biên soBn tài li4u này nhCm gii quy-t phn nào nhDng khó
khăn ñó cho các em hc sinh chuyên Toán.
Chuyên ñ gEm ba chương:
Chương I. Các bài toán chia h-t
Chương II. Các bài toán ñEng dư
Chương III. Các bài toán khác.
H mIi bài ñu ñư>c trình bày ba phn: H4 thng lí thuy-t; h4 thng các ví dL và
cui cùng là h4 thng các bài tAp tN gii. Các ví dL và bài tAp luôn ñư>c sOp x-p v7i ñ
khó tăng dn  theo quan ñiPm cQa tác gi.
Tuy nhiên, do trình ñ có hBn nên không thP tránh kh0i nhiu thi-u sót, r#t mong
ñư>c các thy cô ñóng góp ñP hoàn thi4n hơn. Xin chân thành cm ơn!
NGUYXN VĂN THZO
Nguyn Văn Tho Chuyên ñ S Hc  Phn I
2
Chương I
CÁC BÀI TOÁN V CHIA HT
I.1 Chia ht
I.1.1 Lí thuyt
I.1.1.1 ð#nh nghĩa
Cho m và n là hai s nguyên , n ≠ 0. Ta nói rCng m chia h-t cho n (hay n chia h-t
m) n-u tEn tBi mt s nguyên k sao cho m = kn.
Kí hi4u: m
⋮
n, (ñc là m chia h-t cho n) hay n | m, (ñc là n chia h-t m).
I.1.1.2 Các tính ch(t cơ b*n
Cho các s nguyên x, y, z. Ta có:
a) x
⋮
x, x ≠ 0.
b) N-u x
⋮
y và x ≠ 0 thì |x| ≥ |y|.
c) N-u x
⋮
z, y
⋮
z thì ax + by
⋮
z v7i mi s nguyên a, b.
d) N-u x
⋮
z và x
∓
y
⋮
z thì y
⋮
z
e) N-u x
⋮
y và y
⋮
x thì |x| = |y|.
f) N-u x
⋮
y và y
⋮
z thì x
⋮
z.
g) N-u x | y và y ≠ 0 thì
|
y
x
.
Ch6ng minh
a)x = 1.x nên x
⋮
x v7i mi x ≠ 0.
b)N-u x
⋮
y , x ≠ 0 thì tEn tBi k ∈ Z sao cho x = ky, k ≠ 0
⇒
|x| = |k||y| ≥ |y| do |k| ≥ 1.
Các phn còn lBi cũng khá ñơn gin, vi4c ch6ng minh xin như2ng lBi cho bBn ñc.
I.1.2 Các ví d-
Ví d- 1. Cho n là mt s tN nhiên l7n hơn 1. Ch6ng minh rCng
a)2
n
là t*ng cQa hai s le liên ti-p.
b)3
n
là t*ng cQa ba s tN nhiên liên ti-p.
Li gi*i
a)Ta có 2
n
= (2
n1
 1) + (2
n1
+1) suy ra ñpcm.
b)Ta có 3
n
= (3
n1
 1) + (3
n1
) + (3
n1
+ 1) suy ra ñpcm.
Ví d- 2. Ch6ng minh rCng:
Nguyn Văn Tho Chuyên ñ S Hc  Phn I
3
a)n-u m – n chia h-t mp + nq thì m – n cũng chia h-t mq + np.
b)n-u m – n chia h-t mp thì m – n cũng chia h-t np.
Li gi*i
Nh.n xét: Hai biu thc (mp + nq) và (mq + np) là hai biu thc có hình thc gi!ng như
“ñ!i xng lo&i hai” vì v(y khi xét các biu thc lo&i này thư+ng ngư+i ta kim tra hi-u
c.a chúng.
a) Ta có (mp + nq) – (mq + np) = (m 0 n)(p 0 q)
⋮
(m 0 n)
Nên n-u (mp + nq)
⋮
(m 0 n) thì hiPn nhiên (mq + np)
⋮
(m 0 n).
b) Ch6ng minh tương tN.
Ví d- 3. Ch6ng minh rCng n-u a
3
+ b
3
+ c
3
chia h-t cho 9 thì mt trong ba s a, b, c
phi chia h-t cho 3.
Li gi*i
Nh.n xét: V2i nh3ng bài toán chng minh a chia h4t cho m5t s! c7 th luôn khá ñơn
gi:n! Ta có th xét h4t các trư+ng h=p x:y ra c.a s! dư khi a chia cho s! ñó. ( Công viêc
ñó chính là xét vC h- thDng dư ñEy ñ. 0 ñây là t(p h3u h&n nên có th thG trHc ti4p)
Gi sj không có s nào trong ba sa, b, c chia h-t cho 3. Khi ñó
a = 3m
±
1; b = 3n
±
1; c = 3p
±
1
Do ñó a
3
+ b
3
+ c
3
= (3m
±
1)
3
+ (3n
±
1)
3
+ (3p
±
1)
3
=
9 3
9 1
9 3
9 1
A
a
a
A
+
+
−
−
không thP chia h-t cho 9.
Tl ñó suy ra ñpcm.
Ví d- 4.
Ch6ng minh rCng n-u a
2
+ b
2
chia h-t cho 3 thì c a và b ñu chia h-t cho 3.
Li gi*i
TH1: có 1 s không chia h-t cho 3, gi sj là a
Khi ñó a = 3k
±
1; b = 3q suy ra a
2
+ b
2
= (3k
±
1)
2
+ (3q)
2
= 3(3k
2
±
2k + 3q
2
) + 1 không chia h-t cho 3.
TH2: c hai s không chia h-t cho 3.
Khi ñó a = 3k
±
1; b = 3q
±
1 suy ra a
2
+ b
2
= 3A +2
Do ñó c a và b phi chia h-t cho 3.
Ví d- 5. Ch6ng minh rCng v7i mi s tN nhiên chmn n và mi s tN nhiên le k thì
Nguyn Văn Tho Chuyên ñ S Hc  Phn I
4
S = 1
k
+ 2
k
+ … + n
k
luôn chia h-t cho n + 1.
Li gi*i
Ta có 2S = (1
k
+ n
k
) + (2
k
+ (n  1)
k
) + …
⋮
n + 1
Mà n chmn nên n + 1 le nên (2, n+ 1) = 1
Do ñó S
⋮
n + 1.
Ví d- 6. Cho p là s  nguyên t, p > 3 v à
3
12
2
−
=
p
n
.Ch6ng minh rCng
n
2
2
⋮
−
n
.
Li gi*i
Vì p là s nguyên t và p>3 ⇒
)3(mod12
1
≡
−p
M?t khác (2, p) = 1 nên theo ñrnh lí Fermat ta có
)(mod12
1
p
p
≡
−
Do ñó
p
p
312
1
⋮
−
−
Ta có
n. 22 n 12n 12
3
12
n Vi
12 12 2p 1n rasuy
3
)12)(12(4
3
44
1
3
12
1
n1n2p
2p
2p1n
112
⋮⋮⋮
⋮⋮
−⇒−⇒−⇒
−
=
−−⇒
−+
=
−
=−
−
=−
−− pppp
n
Tl ñó suy ra ñiu phi ch6ng minh.
Ví d- 7. Cho x, y là hai s nguyên khác 1 sao cho
1
1
1
1
33
+
+
+
+
+
x
y
y
x
là mt s nguyên
Ch6ng minh rCng 1
2004
−x chia h-t cho y+1.
Li gi*i
Trư7c h-t ta ñ?t
d
c
xb
a
y
x=
+
+
=
+
+
1
1y
;
1
1
33
v7i a, b, c, d nguyên và b > 0, d > 0, (a,b) = 1, (c,d) = 1.
Ta có
bd
bcad
d
c
b
a
+
=+
nguyên
Do ñó
Nguyn Văn Tho Chuyên ñ S Hc  Phn I
5
b
d
b
ad
b
bc
ad
bd
⋮
⋮
⋮
⋮
⇒
⇒
+
⇒
+
bc
ad
vì (a,b)=1 (1)
M?t khác
(2) da dac bd ac
)1)(1(
1
1
.
1
1
.
22
33
⋮
⋮
⋮
⇒⇒⇒
∈+−+−=
+
+
+
+
=Zyyxx
x
y
y
x
d
c
b
a
Vì (c,d)=1 nên tl (1) và (2) suy ra
a
⋮
b suy ra b = 1 vì (a,b) = 1
Vì
(3) 1y 1 x )1(1 x
1
1
33
3
++⇒+=+⇒=
+
+⋮ya
b
a
y
x
Mà
1 x 1)(x 1
366432004
+=−
⋮
x
K-t h>p v7i (3) suy ra ñiu phi ch6ng minh.
Ví d- 8. Cho n
5
≥
là s tN nhiên .Ch6ng minh rCng
−
n
n)!1(
⋮
n1 .
Li gi*i
a) Trư2ng h>p 1. n là s nguyên t
Theo ñrnh lý Winson (n1)!
≡
1(mod n) suy ra ((n1)!+1
⋮
n
Ta có
1
1)!1(11)!1()!1( −
+−
=
−
+−
=
−
n
n
nn
n
n
n
(vì
1
1
0<<
n
)
=
1)(n
)1()!1(
⋮
n
nn
−
−
−
vì (n, n  1) = 1
b) Trư2ng h>p 2. n là h>p s
+) n không là bình phương cQa mt s nguyên t.
Khi ñó n = rs v7i 1< r < s < n.
Do (n,n1)=1 suy ra s < n1 ⇒ (n1)! = kn(n1)
suy ra
)1()1(
)!1( −−=
−nnk
n
n⋮
.
+) n = p
2
v7i p là mt s nguyên t.