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 Đồng dư 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 ϕn . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Hàm M¨obius µ n . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.3 Hàm tổng các ước dương σn . . . . . . . . . . . . . . . . . 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

lại, nếu ab mod m thì a b. Ngoài ra, nếu c a mod m thì c b mod m .
Điều này c h ứ n g tỏ rằng a b. Hơn nữa, từ a b mod m ta suy ra b a mod m ,
hay b a. Từ đó suy ra a b.
ii Dễ thấy rằng, nếu a b Ø thì a b. Ngược lại, ta cần c h ứ n g tỏ rằng
nếu ab Ø thì a b. Thật v ậ y , giả sử a b Ø gọi c a b. Khi đó, ta có
c a mod m v à c b mod m . Điều này suy ra a b mod m . Do đó, theo i
ta suy ra a b.
iii Để c h ứ n g minh phần này, ta c h ứ n g minh tập 0, 1, 2, , m 1 là m lớp
đồng dư phân biệt theo môđun m. Thật v ậ y , giả sử tồn tại 0 k l m sao c h o
k l.Khi đó, theo i ta có k l mod m , hay m lk. Đ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 Z luôn tồn tại cặp số
nguyên q,r sao c h o a qm r , 0 r m, suy ra a r mod m hay a r.
Định nghĩa 1.1.5. T ậ p gồm m phần tử A a
1
, a
2
, , a
m
gọi là một hệ thặng
dư đầy đủ theo môđun m nếu B a
1
, a
2
, a
3
, , a
m
là tập gồm m lớ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 m là không duy

d
b a hay
a b mod
m
d
.
Mệnh đề 1.1.8. Cho a, b, m
1
, , m
k
là c á c số nguyên, m
1
, , m
k
0, a b mod m
1
,
a b mod m
2
, , a b mod m
k
. Khi đó, ta c ó
a b mod m
1
m
k
,
trong đó m
1
m

b
n 1
qn
n
2
b
n 2
q
2
n
2
n
n
q
n
n
n
n
2
b
n 1
q
n
2
b
n 2
q
2
n
n

a
p
b
p
p
1
a
p 1
b
p
p 1
a.b
p 1
.
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.1. Đồng dư thức 4
Do đó, để c h ứ n g minh mệnh đề ta c h ỉ cần c h ứ n g minh p
p
k
, 1 k p 1 . Thật
v ậ y , ta có
p
k
p!
k!p k!
,
suy ra
k
p

a a
n
.10
n
a
1
.10 a
0
, 0 a
i
9 .
Dấu hiệu chia hết cho 2
k
.
Vì 10 0 mod 2 nên 10
k
0 mod 2
k
. Từ đó suy ra
a a
k 1
.10
k 1
a
0
mod 2
k
.
Do đó, số a c h i a hết c h o 2
k

1 mod 3 . Do đó a
i
.10
k
a
i
mod 3 . Từ
đó suy ra a a
n
.10
n
a
1
.10 a
0
a
n
a
0
mod 3 . V ậ y , số a c h i a
hết c h o 3 khi tổng các c h ữ số của nó c h i a hết c h o 3.
Tương tự ta cũng có 10 1 mod 9 v à a
i
.10
k
a
i
mod 9 . V ậ y , số a c h i a
hết c h o 9 khi tổng các c h ữ số của nó c h i a hết c h o 9.
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

3
a
3
1a
3
mod 7
Từ đó, ta có bảng đồng dư theo môđun 7 tương ứng như sau
a
0
10a
1
10
2
a
2
10
3
a
3
10
4
a
4
10
5
a
5
10
6
a

2
a
3
3a
4
2a
5
a
6
3a
7
2a
8
a
9
3a
10
2a
11
2a
6t 1
Bảng 1.1:
Do đó, số a a
n
.a
n 1
a
1
a
0

a
0
c h i a hết c h o 7 khi tổng dạng
a
2
a
1
a
0
a
5
a
4
a
3
a
8
a
7
a
6
a
11
a
10
a
9
, c h i a hết c h o 7
Dấu hiệu chia hết cho 11
Tương tự dấu hiệu c h i a hết c h o 7, ta cũng có

3
mod 11
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.1. Đồng dư thức 6
a
0
10a
1
10
2
a
2
10
3
a
3
10
4
a
4
10
5
a
5
10
6
a
6
10

3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
a
11
a
2t 1
Bảng 1.2:
Do đó, số a a
n
.a
n 1
a
1
a
0
c h i a hết c h o 11 khi tổng dạng
a

2
a
3
a
4
a
5
a
6
a
2t 1
c h i a hết c h o 11
Dấu hiệu chia hết cho 13
T a có
a
0
a
0
mod 13 a
0
a
0
mod 13
10 3 mod 13 10a
1
3a
1
mod 13
10
2

4
a
4
10
5
a
5
10
6
a
6
10
7
a
7
10
8
a
8
10
9
a
9
10
10
a
10
10
11
a

6t 1
Bảng 1.3:
Từ bảng 1.3 ta suy ra rằng, số aa
n
.a
n 1
a
1
a
0
c h i a hết c h o 13 khi tổng
dạng
a
0
3a
1
4a
2
a
3
3a
4
4a
5
a
6t 3
3a
6t 2
4a
6t 1

a
11
a
10
a
9
c h i a hết c h o 13.
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.1. Đồng dư thức 7
Dấu hiệu chia hết cho 33
T a có
a
0
a
0
mod 33 a
0
a
0
mod 33
10 10 mod 33 10a
1
10a
1
mod 33
10
2
1 mod 33 10
2

10
5
a
5
10
6
a
6
10
7
a
7
10
8
a
8
10
9
a
9
10
10
a
10
10
11
a
11
10
2t

n
.a
n 1
a
1
a
0
c h i a hết c h o 33 khi tổng
dạng
a
0
a
2
a
2t
10 a
1
a
3
a
2t 1
0 mod 33
Ngoài ra, v ớ i mọi số x, y ta đều có
x 10y 10yx mod 33 yxmod 33.
Từ đó suy ra, số a a
n
.a
n 1
a
1

a
5
a
4
a
6
a
5
, c h i a hết c h o 11; 3.
Dấu hiệu chia hết cho 37
T a có
a
0
a
0
mod 37 a
0
a
0
mod 37
10 10 mod 37 10a
1
10a
1
mod 37
10
2
11 mod 37 10
2
a

3
11a
3
mod 37
a
0
10a
1
10
2
a
2
10
3
a
3
10
4
a
4
10
5
a
5
10
6
a
6
10
7

10a
4
11a
5
a
6
10a
7
11a
8
a
9
10a
10
a
11
11a
3t
Bảng 1.5:
Từ bảng 1.5 ta suy ra rằng, số aa
n
.a
n 1
a
1
a
0
c h i a hết c h o 37 khi tổng
dạng
a

2
a
1
a
0
a
5
a
4
a
3
a
8
a
7
a
6
, c h i a hết c h o 37.
Ví dụ 1.1.2.2. Chứng minh rằng
a 4
4021
3
2012
c h i a hết c h o 13,
b 6
2023
8
2023
c h i a hết c h o 49,
c 220

16
2008
3 3
2009
mod 13
0 mod 13 .
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.1. Đồng dư thức 9
V ậ y , 4
4021
3
2012
c h i a hết c h o 13.
b) T a có 6
2023
8
2023
68 6
2022
6
2021
86
2020
8
2
8
2022
14M,trong
đó

220
69
1 mod 2 ,
69 1 mod 2 69
220
119
1 mod 2 .
Do đó, A 220
119
69
119
69
220
69
220
119
c h i a hết c h o 2.
Tương tự ta cũng c h ứ n g minh được A c h i a hết c h o 3, 17. Vì các số 2, 3, 17 là
những số đôi một nguyên tố cùng nhau nên ta suy ra A c h i a hết c h o 102.
d) T a có 2222 3 mod 7 , 3
2
2 mod 7 , 3
3
1 mod 7 . Do đó
2222
5555
3
3.1851 2
2 mod 7 .
Tương tự, ta cũng có 5555 4 mod 7 , 4

1234356789
4
789
4
5
4
1 mod 8 .
Từ đó suy ra số dư của phép c h i a 1234356789
4
c h o 8 là 1.
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.2. Phương trình đồng dư 10
1.2 Phương trình đồng dư
1.2.1 Phương trình đồng dư bậc nhất một ẩn
Định nghĩa 1.2.1. Phương trình đồng dư tuyến tính một ẩn số là phương trình
dạng ax b mod m , trong đó a, b, m Z, m 0, a 0 mod m .
Một nghiệm của phương trình là số nguyên x
0
thỏa mãn ax
0
b mod m .
Ví dụ 3, 8, 13 là những nghiệm của phương trình 6x 3 mod 15 . Số 18 cũng
là nghiệm, nhưng 18 3 mod 15 .
Mệnh đề 1.2.2. Gọi d ƯCLN a, m . Khi đó, phương trình đồng dư ax b mod m
c ó nghiệm nếu và chỉ nếu d b. Hơn nữa, nếu x
0
là nghiệm thì phương trình c ó đúng
d nghiệm không đồng dư theo môđun m.
Chứng minh. Nếu x

Đặt c
b
d
, nhân cả hai v ế phương trình trên c h o c ta được ax
,
0
m y
,
0
c b.
Điều này suy ra x x
,
0
c là nghiệm của phương trình ax b mod m .
Tiếp theo, ta c h ứ n g minh phương trình này có đúng d nghiệm không đồng dư
theo môđun m. Thật v ậ y , giả sử x
1
, x
2
là hai nghiệm của phương trình. Khi đó,
a x
1
x
0
0 mod m suy ra m a x
1
x
0
. Hơn nữa, ta có d ƯCLN a, m
nên đặt m

đồng dư của phương trình là x
0
, x
0
m , , x
0
d 1 m .
Quay lại ví dụ xét ở trên, phương trình 6x 3 mod 15 có d ƯCLN 15, 3 3,
m 5, v à x
0
3 là nghiệm, các nghiệm tiếp theo là 8, 13.
Định nghĩa 1.2.3. Cho a, m là các số nguyên, m 1. Nghiệm của phương trình
đồng dư ax 1 mod m được gọi là nghịch đảo của a theo môđun m.
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.2. Phương trình đồng dư 11
1.2.2 Hệ phương trình đồng dư đồng dư bậc nhất một ẩn
Định nghĩa 1.2.4. Hệ phương trình dạng
x b
1
mod m
1
x b
2
mod m
2
x b
n
mod m
n

1
x b
2
mod m
2
x b
n
mod m
n
c ó nghiệm duy nhất theo môđun m.
Chứng minh. Đặt n
i
m
m
i
, ta được m
i
, n
i
1. Khi đó, tồn tại số nguyên r
i
, s
i
sao
c h o r
i
m
i
s
i

i
mod m
i
dẫn đến x
0
b
i
mod m
i
.
V ậ y x
0
là một nghiệm của hệ. Hơn nữa, giả sử x
1
là một nghiệm khác của hệ. T a có
x
1
x
0
0 mod m
i
, i 1, 2, , n hay m
1
, m
2
, , m
n
c h i a hết c h o x
1
x

i
n
i
s
i
2 578 1155 -1
3 257 770 -1
5 -277 462 3
7 -47 330 1
11 0 210 0
Bảng 1.6:
(2r 1155s 1 2r 1 1155s 2 1144s s 1, vì r nguyên nên ta chọn
s 1, , dẫn đến ta c ó c ặ p (r, s) như b ả n g (1.6).)
Áp dụng Định lý 1.2.5, ta có nghiệm của hệ trên là
x 1155 1 770 1 462 3 330 1 210.0 mod 2310 209 mod 2310 .
1.3 Các hàm số học
1.3.1 Phi hàm Ơle ϕn
Định nghĩa 1.3.1. Cho n là số nguyên dương. Phi hàm Ơle ϕ n Euler’s function ϕ n
là số các số nguyên dương không vượt quá n v à nguyên tố cùng nhau v ớ i n.
Ví dụ v ớ i n 4, ta có ϕ 4 3.
Phi hàm Ơle là hàm nhân tính, tức là v ớ i hai số m, n nguyên tố cùng nhau ta
có ϕm.n ϕ m .ϕ n . V ớ i k ế t quả này, ta có mệnh đề sau đây c h o ta cách tính
ϕ n .
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.3. Các hàm số học 13
Mệnh đề 1.3.2. Giả sử số tự nhiên n được phân tích thành tích c á c thừa số nguyên
tố np
α
1

trong đó tổng được lấy theo mọi ước của n.
Chứng minh. Xét n số hữu tỉ
1
n
,
2
n
, ,
n
n
. Rút gọn mỗi phân số sao c h o mỗi phân số
đều tối giản. Khi đó, tất cả các mẫu số của những phân số này đều là ước của n.
Do đó, nếu d là ước của n thì có c h í n h xác ϕ d phân số có mẫu số là d. Từ đó suy
ra
d n
ϕ
n
d
n.
Định nghĩa 1.3.4. Một tập gồm ϕn số nguyên mà mỗi phần tử của tập đều
nguyên tố cùng nhau v ớ i n v à hai phần tử khác nhau của tập không đồng dư theo
môđun n được gọi là một hệ thặng dư thu gọn theo môđun n.
Định lý 1.3.5 (Euler’s theorem). Cho m là số nguyên dương và a là số nguyên
với a, m 1. Khi đó, ta c ó a
ϕ m
1 mod m .
Chứng minh. Giả sử r
1
, r
2

r
ϕ
r
1
r
2
r
ϕ
mod m .
Ngoài ra, ta có ƯCLN r
1
r
2
r
ϕ m
, m 1 nên suy ra a
ϕ m
1 mod m .
Hệ quả 1.3.6. Cho a, m là c á c số nguyên, với m0, ƯCLN a, m 1 và n, k là
hai số tự nhiên thỏa nk mod ϕ m . Khi đó
a
n
a
k
mod m .
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.3. Các hàm số học 14
Chứng minh. T a có n k mod ϕ m . n kt.ϕ m , t Z. Do đó,
a

Ngược lại, giả sử n1 ! 1 mod n . T a c h ứ n g minh n là số nguyên tố. Thật
v ậ y , giả sử n là hợp số, tức là n a.b trong đó 1 a b n. Khi đó a n 1 !.
Ngoài ra theo giả thiết, ta có n 1 ! 1 mod n tức là a n 1 !1 . Từ đó
suy ra a1. Điều này mâu thuẫn. V ậ y n là số nguyên tố.
Mệnh đề 1.3.9. Gọi p
t
là lũy thừa của số nguyên tố lẻ, m là số nguyên tố cùng
nhau với c ả p và p1 và a, b nguyên tố cùng nhau với p. Khi đó
a
m
b
m
mod p
t
nếu và chỉ nếu a b mod p
t
.
Chứng minh. Vì a b a
m
b
m
nên từ giả thiết là a b mod p
t
ta suy ra
a
m
b
m
mod p
t

.
1.3.2 Hàm M
¨
obius µ n
Định nghĩa 1.3.10. Hàm số học M¨obius µn là hàm c h o bởicông thức
µ n
1 nếu n 1,
0 nếu n không c h í n h phương,
1
k
nếu n là số c h í n h phương v à k là số các ước nguyên tố của n.
Mệnh đề 1.3.11. Nếu n1 thì
d n
µ d 0.
Chứng minh. Nếu n1 thì n được phân tích thành tích các thừa số nguyên tố
n p
α
1
1
p
α
2
2
p
α
l
l
. Khi đó,
d n
µ d

Định nghĩa 1.3.12. Hàm số học σn là hàm nhận giá trị tại n là tổng các ước
dương của n. T a có thể viết gọn định nghĩa trên như sau
σ n
d n
d.
Hàm σn là hàm nhân tính. Nếu p là số nguyên tố thì σp p1.
Nếu σn 2n thì n được gọi là số hoàn hảo (perfect), ví dụ số 6, 28 là những
số hoàn hảo.
Định lý 1.3.13. Nếu số tự nhiên n được phân tích thành tích c á c thừa số nguyên
tố np
α
1
1
p
α
2
2
p
α
l
l
thì
σ n
l
i 1
p
α
i
1
i

1
1
.
Từ đó suy ra,
σ n
l
i 1
p
α
i
1
i
1
p
i 1
.
Mệnh đề 1.3.14. Nếu m là số hoàn hảo lẻ và m c ó phân tích c ơ sở m p
α
i
i
thì
1) T ồ n tại duy nhất một chỉ số i sao cho
α
i
lẻ
p
i
1 mod 4
2) V ớ i mọi ji, α
j

α
j
j
. Khi đó từ
σ p
α
j
j
là số lẻ nên α
j
phải c h i a hết c h o 2.
Mệnh đề 1.3.15. n là số hoàn hảo chẵn khi và chỉ khi n2
m 1
2
m
1 , trong
đó 2
m
1 là số nguyên tố Mersene.
Chứng minh. Giả sử n 2
s
q,s 1, q 2t1, ta có
2
s 1
q σ2
s
q 2
s 1
1 σq.
Suy ra q c h i a hết c h o 2

1 là số nguyên tố. Khi đó,
σ n σ2
m 1
σ2
m
1 2
m 1
2
m
2n.
V ậ y n là số hoàn hảo.
Hà Duy Nghĩa -THPT Phan Đình Phùng-Đăk Lăk

1.3. Các hàm số học 17
1.3.4 Ứng dụng
Ví dụ 1.3.4.1. Tìm số dư trong các phép c h i a sau
a 123
345
c h i a c h o 14,
b 35
150
c h i a c h o 425, (Chọn HSGQG-Daklak-2011).
L ờ i giải: a) T a có 123 3 mod 14 , 345 3 mod 6 v à ƯCLN 123, 14 1,
ϕ 14 6 nên áp dụng Hệ quả 1.3.6 ta có
123
345
123
3
3
3

2 4
2
4
1 mod 17 .
Từ đó suy ra 5
158
.7
150
2 15 mod 17 hay 35
150
375 mod 425 .
V ậ y số dư khi c h i a 35
150
c h o 425 là 375.
Ví dụ 1.3.4.2. Chứng minh rằng nếu ƯCLN a, 5 1 thì a
8n
3a
4n
4 c h i a hết
c h o 100.
L ờ i giải: Đặt Aa
8n
3a
4n
4 a
4n
1 a
4n
4 . Theo công thức Euler ta
có a

. 4 suy ra B
. . .
. 4
a lẻ, tức là a 2k1 ta có
a
4n
3 2k1
4n
3
4n
k 0
4n
k
2k
4n k
.1
k
3
. . .
. 4
Từ đó suy ra a
8n
3a
4n
4 c h i a hết c h o 100.
Ví dụ 1.3.4.3. Tìm số tự nhiên n sao c h o hai số n 1 v à
n n 1
2
là hai số số hoàn
hảo.

2 nên q 2 hoặc p 2 suy ra
n 7.
b) n 4k 1 suy ra
n n 1
2
là số hoàn hảo lẻ v à n 1 là số hoàn hảo c h ẵ n . Do đó,
n 1 2
p 1
2
p
1
n n1
2
2
2p 2
2
p 2
1 2
2p 1
2
p 1
1 .
Suy ra 2
2p 2
2
p 2
1 , hoặc 2
2p 1
2
p 1

c h i a c h o 41.
Bài tập 1.4.3. Chứng minh rằng 0, 3. 1983
1983
1917
1917
là số nguyên.
Bài tập 1.4.4. Chứng minh rằng
26
k 1
k.10
3k
, k N c h i a hết c h o 13.
Bài tập 1.4.5. Tìm các số tự nhiên n để n
n 1
n1
n
c h i a hết c h o 5.
HD: Xét n 5kr , r 0, 1, 2, 3, 4 .
Bài tập 1.4.6. Cho số nguyên a, c h ứ n g minh rằng a
2
1 không có ước nguyên tố
dạng 4k 3, từ đó suy ra các phương trình sau không có nghiệm nguyên dương.
a 4xy x y z
2
,
b x
2
y
3
7.

L ờ i giải: Dễ thấy rằng n là số lẻ. Gọi x là 3 c h ữ số tận cùng của n. Khi đó
n x mod 1000 . Vì 15, 35, 55 là 3 số hạng trong tích (2.1) nên n c h i a hết c h o
125, v à 1000=125.8 ta suy ra x cũng c h i a hết c h o 125. Do đó, x c h ỉ có thể là những
số 125, 375, 625, 875.
Từ đó suy ra, 1000 n x 8 n x n x mod 8 . Tiếp theo lấy môđun
8 các số hạng của n ta được
n 3 4.13 4.23 4.502 3 3.7 3.7 3.7 3
251 cặp
.3 5.5 5
251 cặp
.3 mod 8
1.1 1
125 cặp
.5.3 7 mod 8
Hơn nữa, trong các số 125, 375, 625, 875 c h ỉ có duy nhất số 375 là đồng dư v ớ i
7 theo môđun 8 nên 375 là 3 c h ữ số tận cùng của n.
Bài toán 2.1.2. (IMO-1964). a) Tìm tất cả các số nguyên dương n sao c h o 2
n
1
c h i a hết c h o 7.
b) Chứng minh rằng không có số tự nhiên n nào để 2
n
1 c h i a hết c h o 7.
L ờ i giải: Vì n là số nguyên dương nên ta xét các trường hợp của n như sau:
V ớ i n 3k,k Z ta có
2
n
1 2
3 k
1 1

Hướng dẫn: Xét số tự nhiên n dạng n 6kr , k Z, 0 r k.
Bài toán 2.1.4. (Olympic10-30/4-2008) Tìm tất cả các số nguyên dương m thỏa
điều kiện
a, b Z, a
2
b
2
mod m a mod m (2.2)
L ờ i giải: T r ư ớ c hết, nhận thấy rằng nếu m1 hoặc m là số nguyên tố thì v ớ i
mọi a, b Z, a
2
b
2
mod m a b mod m . Thật v ậ y ,
Nếu m 1 thì (2.2 ) đúng.
Xét m là số nguyên tố, v ớ i a, b Z thỏa a
2
b
2
mod m . T a có
a b ab a
2
b
2
0 mod m ,
điều này suy ra a b
. . .
. m hoặc ab
. . .
. m. Do đó, a b mod m .

.p. Do đó a b
. . .
. 2p, ab
. . .
. 2p
hay a b mod m .
V ậ y v ớ i m 1, m 2p hoặc m nguyên tố là những giá trị cần tìm.
2.2 Các bài toán trong kỳ thi học sinh giỏi Quốc gia
Bài toán 2.2.1. (HSGQG-1975) Tìm tất cả các số hạng của cấp số cộng 1, 18, 37, ,
có các c h ữ số đều là c h ữ số 5.
L ờ i giải: T a có số hạng đầu của cấp số cộng là a
1
1 v à công sai d 19 nên số
hạng tổng quát là a
n
19n 20, n 1. Do đó, bài toán trở thành tìm tất cả số n
thỏa
19n 20 55 5
k số
5.
10
k
1
9
, k 1
Điều này tương đương v ớ i 5.10
k
4 mod 19 , hay
5.10
k

k
19s 4 5. 10
k
1 19s 9, v ớ i mỗi số nguyên s. Từ đây, nhận
thấy rằng v ế trái của biểu thức trên c h i a hết c h o 9, do đó v ế phải của nó cũng c h i a
hết c h o 9, tức là s 9r . Khi đó ta có
19r 1 5.
10
k
1
9
55 5
k số
.
Từ đó suy ra, các số hạng cần tìm của dãy có dạng 55 5
18l 5 số
v ớ i mỗi số tự nhiên l.
Bài toán 2.2.2. (HSGQG-1987) Cho hai dãy x
n
, y
n
xác định bởi
x
0
365, x
n 1
x
n
x
1986

4
0
1952 63584 32.1987 do đó, y
1
y
0
mod 1987 . Ngoài
ra, ta có y
2
y
1
y
4
1
1952 y
4
0
1952 mod 1987 0 mod 1987 nên suy ra
y
2
y
1
mod 1987 . Tương tự, ta c h ứ n g minh được
y
k
y
0
mod 1987 , k 1.
Mặt khác, đối v ớ i dãy x
n

1622 0 mod 1987.
Do đó,
x
2
x
0
mod 1987 .
Tương tự, ta c h ứ n g minh được
x
n
x
0
mod 1987 365 mod 1987 , n 1.
Từ đó suy ra, v ớ i mọi k,n 1 ta luôn có y
k
x
n
0. (Vì 365 v à 16 không đồng
dư theo môđun 1987).
Bài toán 2.2.3. (HSGQG-1999B) Cho hai dãy x
n
, y
n
xác định bởi:
x
1
1, y
1
2, x
n 1