SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐĂK LĂK
TRƯỜNG THPT PHAN ĐÌNH PHÙNG
*********
HÀ DUY NGHĨA
ỨNG DỤNG LÝ THUYẾT ĐỒNG DƯ
TRONG CÁC BÀI TOÁN CHIA HẾT
CHUYÊN ĐỀ BỒI DƯỠNG HSG
Đăk Lăk -2012
MỤC LỤC
Mục lục i
Chương 1 đồng dư v à áp dụng 1
1.1 Đồngdưthức .............................. 1
1.1.1 Một số khái niệm v à tính c h ấ t cơ bản . . . . . . . . . . . . . 1
1.1.2 Ứng dụng của lý thuyết đồng dư để tìm dấu hiệu c h i a hết . 4
1.2 Phương trình đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 Phương trình đồng dư bậc nhất một ẩn . . . . . . . . . . . . 10
1.2.2 Hệ phương trình đồng dư đồng dư bậc nhất một ẩn . . . . . 11
1.2.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Các hàm số học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Phi hàm Ơle ϕ
ppp
n
qqq
........................ 12
1.3.2 Hàm M¨obius µ n ........................ 15
1.3.3 Hàm tổng các ước dương σ
p
n
q
................. 15
1.3.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Bài tập tự luyện . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Chương 2 một số bài toán trong các kỳ thi học sinh giỏi 20
2.1 Các bài toán trong các kỳ thi Olympic . . . . . . . . . . . . . . . . 20
2.2 Các bài toán trong kỳ thi học sinh giỏi Quốc gia . . . . . . . . . . 22
T à i liệu tham khảo 28
Chương 1
L Ý THUYẾT ĐỒNG DƯ V À ÁP DỤNG
1.1 Đồng dư thức
1.1.1 Một số khái niệm v à tính c h ấ t cơ bản
Định nghĩa 1.1.1. Cho a, b, m là các số nguyên, m
0. Số ađược gọi là đồng dư
v ớ i btheo môđun mnếu mlà ước của
p
b
a
q
.
Nếu ađồng dư v ớ i btheo môđun mthì viết a
b
p
mod m
q
.Ngược lại, nếu a
không đồng dư v ớ i btheo môđun mthì ta viết a
b
p
mod m
q
.
Ví dụ 2
5
p
mod 3
q
vì 3
|p
5
2
q
.
Nếu a
b
p
mod m
q
thì bgọi là một thặng dư của atheo môđun m.
Nếu 0
¨
b
¨
m
1thì bgọi là một thặng dư bénhất của atheo môđun m.
Mệnh đề 1.1.2. Cho a, b, c, m là những số nguyên m
0. Khi đó, ta c ó
(i) a
a
p
mod m
q
,
(ii) Nếu a
b
p
mod m
q
thì b
a
p
mod m
q
,
(iii) Nếu a
b
p
mod m
q
và b
c
p
mod m
q
thì a
c
p
mod m
q
.
Chứng minh. Mệnh đề
p
i
q
,
p
ii
q
là hiển nhiên, ta c h ứ n g minh mệnh đề
p
iii
q
.Thật
v ậ y , ta có a
b
p
mod m
q
, b
c
p
mod m
q
suy ra m
|p
b
a
q
v à m
|p
c
b
q
. Do đó
m
|p
b
a
c
b
q
, hay m
|p
c
a
q
.V ậ y a
c
p
mod m
q
.
Tiếp theo, ký hiệu alà tâp hợp tất cả các số nguyên đồng dư v ớ i atheo môđun
m,a
t
n
P
Z
|
n
a
p
mod m
qu
.Nói cách khác, alà tập hợp các số nguyên có dạng
t
a
km
u
. Từ đó, ta có định nghĩa sau.
Định nghĩa 1.1.3. Một tập gồm các phần tử dạng a
t
a
km,k
P
Z
u
gọi là một
lớp đồng dư của atheo môđun m.
1.1. Đồng dư thức 2
Ví dụ v ớ i m
2,ta có lớp 0là tập các số nguyên c h ẵ n , lớp 1là tập các số
nguyên lẻ.
Mệnh đề 1.1.4. Cho a, b, m là những số nguyên m
0.Khi đó, ta c ó
(i) a
bkhi và chỉ khi a
b
p
mod m
q
,
(ii) a
bkhi và chỉ khi a
X
b
Ø,
(iii) Có đúng mlớp đồng dư phân biệt theo môđun m.
Chứng minh.
p
i
q
Giả sử a
b, ta xét a
P
a
b. Do đó, a
b
p
mod m
q
. Ngược
lại, nếu a
b
p
mod m
q
thì a
P
b. Ngoài ra, nếu c
a
p
mod m
q
thì c
b
ppp
mod m
qqq
.
Điều này c h ứ n g tỏ rằng a
b. Hơn nữa, từ a
b
p
mod m
q
ta suy ra b
amod m,
hay b
a. Từ đó suy ra a
b.
p
ii
q
Dễ thấy rằng, nếu a
X
b
Øthì a
b. Ngược lại, ta cần c h ứ n g tỏ rằng
nếu a
X
b
Øthì a
b. Thật v ậ y , giả sử a
X
b
Øgọi c
P
a
X
b. Khi đó, ta có
c
a
p
mod m
q
v à c
b
p
mod m
q
.Điều này suy ra a
b
p
mod m
q
.Do đó, theo
p
i
q
ta suy ra a
b.
p
iii
q
Để c h ứ n g minh phần này, ta c h ứ n g minh tập
t
0,1,2, ..., m
1
u
là mlớp
đồng dư phân biệt theo môđun m. Thật v ậ y , giả sử tồn tại 0
¨
k
l
msao c h o
k
l.Khi đó, theo
p
i
q
ta có k
l
p
mod m
q
,hay m
|p
l
k
q
.Điều này mâu thuẫn v ớ i
giả thiết 0
l
k
m. Do đó, k
l.Ngoài ra, v ớ i mỗi a
P
Zluôn tồn tại cặp số
nguyên q,rsao c h o a
qm
r , 0
¨
r
m, suy ra a
r
p
mod m
q
hay a
r.
Định nghĩa 1.1.5. T ậ p gồm mphần tử
t
A
a1
,a2
, ..., am
u
gọi là một hệ thặng
dư đầy đủ theo môđun mnếu
t
B
a1
, a2
, a3
, ..., am
u
là tập gồm mlớp đồng dư
phân biệt theo môđun m.
Từ định nghĩa ta thấy rằng, hệ thặng dư đầy đủ theo môđun mlà không duy
nhất. Ví dụ các tập
t
0,1,2,3
u
,
t
4,9,14,
1
u
,
t
0,1,
2,
1
u
là những hệ thặng dư
đầy đủ theo môđun 4.
Mệnh đề 1.1.6. Nếu a
c
p
mod m
q
và b
d
p
mod m
q
thì a
b
c
d
p
mod m
q
và ab
cd
p
mod m
q
.
Chứng minh. Dễ dàng suy ra từ định nghĩa.
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk
1.1. Đồng dư thức 3
Mệnh đề 1.1.7. Cho a, b, c, m là c á c số nguyên, m
¡
0, ac
bc
p
mod m
q
và d
p
c, m
q
.
Khi đó, ta c ó
a
b
p
mod m
d
q
.
Chứng minh. Giả sử ac
bc
p
mod m
q
.T a có m
|p
bd
ac
q
,suy ra tồn tại số nguyên
ksao c h o c
p
b
a
q
km.Khi đó, c h i a hai v ế c h o dta được c
d
p
b
a
q
k
m
d
.Ngoài
ra, theo giả thiết ta có d
p
c, m
q
,suy ra c
d
,m
d
1.Do đó, ta có m
d
|p
b
a
q
hay
a
b
p
mod m
d
q
.
Mệnh đề 1.1.8. Cho a, b, m1
, ..., mklà c á c số nguyên, m1
, ..., mk
¡
0, a
b
p
mod m1
q
,
a
b
p
mod m2
q
, ..., a
b
p
mod mk
q
.Khi đó, ta c ó
a
b
p
mod
r
m1
...mk
sq
,
trong đó
r
m1
m2
...mk
s
là b ộ i chung nhỏ nhất của m1
,m2
..., mk
.
Chứng minh. Suy ra trực tiếp từ định nghĩa.
Mệnh đề 1.1.9. Nếu a
b
p
mod n
q
thì an
bn
p
mod n2
q
.
Chứng minh. Từ a
b
p
mod n
q
suy ra a
b
nq. Do đó, theo công thức khai
triển nhị thức ta có
an
bn
p
b
nq
q
n
bn
n
1
bn
1
qn
n
2
bn
2
q
2
n2
n
n
q
n
nn
n2
bn
1
q
n
2
bn
2
q
2
n
n
q
n
nn
2
.
Từ đó suy ra an
bn
p
mod n2
q
.
Điều ngược lại không đúng, ví dụ như 34
14
p
mod 42
q
nhưng 3
1
p
mod 4
q
.
Mệnh đề 1.1.10. Nếu a, b là c á c số nguyên và plà số nguyên tố thì
p
a
b
q
p
ap
bp
p
mod p
q
Chứng minh. Theo công thức khai triển nhị thức ta có
p
a
b
q
p
ap
bp
p
1
ap
1
b
p
p
1
a.bp
1
.
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk