Trang 1
§3. Lớp thặng dư và hệ thặng dư. Các định lí cơ bản về đồng dư
Bài học này có ba nội dung chính được trình bày lồng ghép với nhau. Phần thứ nhất của
bài học tập trung làm rõ các khái niệm lớp thặng dư và hệ thặng dư, khái niệm nghịch đảo modulo
và cách vận dụng các khái niệm này trong các bài toán số học. Phần thứ hai trong bài học trình
bày các định lí cơ bản về đồng dư, bao gồm định lí Fermat, định lí Euler, định lí Wilson và định lí
Wolstenholme. Phần cuối cùng dành thời lượng để giới thiệu về quan hệ đồng dư trên
.
Cần chú ý rằng vì mục đích sư phạm mà nhiều nội dung (đặc biệt là phần khái niệm) trong
tài liệu này được phát biểu một cách hết sức nôm na (nhưng vẫn giữ được bản chất của khái niệm).
Tài liệu tham khảo: Các bài giảng về số học, Nguyễn Vũ Lương (Chủ biên).
Lectures of Modulo Arithmetic, Yufei Zhao.
I. Nội dung bài học
1. Lớp thặng dư và hệ thặng dư
Cho trước một số nguyên dương
m
. Ta biết rằng có vô hạn số nguyên, nhưng khi chia các
số nguyên cho
m
thì các số dư thu được chỉ có thể là
0
,
1
, … và
1
m
. Do đó tập các số nguyên
có thể được phân hoạch thành
m
tập hợp:
Tập
0
gồm các số chia hết cho
m
,
Tập
1
A
gồm các số chia
m
dư
1
,
…
Tập
1
m
A
gồm các số chia
m
dư
1
m
.
Để cho tiện, ta kí hiệu các tập hợp trên lần lượt là
0
m
,
1
m
, … và
1
m
m
.
Mỗi tập hợp trên được gọi là một lớp thặng dư modulo
m
.
Nếu không có nhầm lẫn gì, đôi khi ta kí hiệu các lớp thặng dư trên là
0
,
1
, … và
1
m
hoặc thậm
chí đơn giản hơn nữa là
0
,
1
, … và
1
m
.
Ví dụ 1.1. Ta có
5
3,2,7 2
vì
3 7 2 (mod5)
.
Định nghĩa. Cho m
. Một tập hợp
m
số nguyên
1 2
, ,...,
a a a
được gọi là một hệ thặng dư
đầy đủ modulo
m
(hay hệ đầy đủ modulo
m
) nếu
m
số này thuộc đúng
m
lớp thặng dư phân
biệt modulo
m
.
Nói cách khác, khi đem
m
số 1 2
, ,...,
m
a a a
chia cho
m
ta thu được đúng
m
số dư là
0,1,..., 1
m
.
Ví dụ 1.2.
(a)
0,1,2,3,4
và
12,8, 1,5, 4
là các hệ thặng dư đầy đủ modulo
5
.
(b)
3;12; 9;8; 5
không là hệ thặng dư đầy đủ modulo
5
vì
3 8 (mod5)
.
Nhận xét 1. Từ Ví dụ 1.2 ta rút ra điều kiện cần và đủ để tập hợp
m
số nguyên
1 2
, ,...,
a a a
là
một hệ thặng dư đầy đủ modulo
m
là
(mod )
i j
a a m
với mọi
i j
.
Trang 2
Mệnh đề 1. Cho m
. Giả sử
1 2
, ,...,
a a a
là một hệ thặng dư đầy đủ mod
m
. Khi đó
(a) Với mọi b
thì
1 2
, ,..., n
a b a b a b
là một hệ thặng dư đầy đủ mod
m
.
(b) Với mọi a
,
( , ) 1
a m
thì
1 2
, ,...,
aa aa aa
là một hệ thặng dư đầy đủ mod
m
.
Chứng minh
(a) Áp dụng Nhận xét 1 ta chỉ cần chứng minh
(mod )
i j
a b a b m
với mọi
i j
, tức là
(mod )
i j
a a m
với mọi
i j
. Tuy nhiên đây là điều hiển nhiên đúng do
1
m
i
i
a
là một hệ thặng
dư đầy đủ mod
m
.
(b) Giả sử
1
m
i
i
aa
không là một hệ thặng dư đầy đủ mod
m
, khi đó tồn tại
, 1,2,...,
i j m
,
i j
sao cho
(mod )
i j
aa aa m
. Do đó ( )
i j
a a a m
, mà
( , ) 1
a m
nên ta có
i j
a a m
,
mâu thuẫn với giả thiết
1
m
i
i
a
là một hệ thặng dư đầy đủ mod
m
.
Lưu ý. Giả thiết
a
và
m
nguyên tố cùng nhau ở kết quả (b) đóng vai trò then chốt, nếu thiếu giả
thiết này thì
1
m
i
i
aa
không thể là hệ thặng dư đầy đủ mod
m
. Để dễ hình dung, ta có ví dụ sau.
Ví dụ 1.3. Xét hệ thặng dư đầy đủ mod
12
0,1,2,3,4,5,6,7,8,9,10,11
.
Khi “nhân” hệ thặng dư trên với
8
ta được
0,8,16,24,32,40,48,56,64,72,80,88 0,4,8 (m
od12)
.
Rõ ràng hệ mới không là hệ thặng dư đầy đủ mod
12
.
Nhận xét 2.
(a) Từ kết quả của Mệnh đề 1 ta rút ra hệ quả dưới đây
“Cho ,a b
,
( , ) 1
a m
. Nếu
x
chạy khắp một hệ thặng dư đầy mod
m
thì
ax b
cũng chạy
khắp một hệ thặng dư đầy đủ mod
m
”.
(b) Cho m
, a
và
( , ) 1
a m
. Do
1, 2,...,
m
là một hệ đầy đủ mod
m
nên theo Mệnh
đề 1 (b) ta thấy
.1, .2,..., .
a a a m
là một hệ thặng dư đầy đủ mod
m
, do đó trong tập hợp này phải
chứa một số nguyên có dạng
ax
, với
1, 2,...,
x m
, sao cho
1 (mod )
ax m
.
Số nguyên dương
x
như vậy được gọi là một nghịch đảo của
a
modulo
m
.
Nghịch đảo của
a
modulo
m
không là duy nhất, chẳng hạn
2
và
7
đều là nghịch đảo của
3
modulo
5
vì
3.2 3.7 1 (mod5)
.
Tuy nhiên tất cả các nghịch đảo của
a
modulo
m
đều đồng dư với nhau theo mod
m
(như trong
ví dụ trên ta có
2 7 (mod 5)
). Do đó nghịch đảo của
a
modulo
m
là duy nhất theo modulo
m
.
Bởi vậy ta có thể kí hiệu chung các nghịch đảo của
a
modulo
m
là
1
a
.
Ví dụ 1.4. Ta có 1
5 3 (mod7)
và 1
6 2 (mod13)
.
Cũng cần phải chú ý thêm rằng chỉ có các số
a
nguyên tố cùng nhau với
m
mới có nghịch
đảo modulo
m
. Ví dụ 1.3 là một minh chứng cho khẳng định này khi 1
8 mod12
không tồn tại.
Trang 3
Sau đây ta cùng xem xét một số bài toán mà việc vận dụng khái niệm hệ thặng dư đầy đủ
đóng vai trò then chốt.
Ví dụ 1.5. Tìm tất cả các số nguyên tố
p
sao cho
2
p
và
4
p
cũng là các số nguyên tố.
Hướng dẫn giải
Dễ thấy
, 2, 4 , 1, 2 (mod3)
p p p p p p
nên
, 2, 4
p p p
là một hệ đầy đủ mod
3
.
Do đó trong ba số
, 2, 4
p p p
phải có đúng một số chia hết cho
3
, mà chúng đều là các số
nguyên tố nên
3
p
. Với
3
p
thử lại ta thấy
2 5
p
,
4 7
p
là các số nguyên tố.
Ví dụ 1.6. [Định lí Bézout] Cho các số nguyên dương
a
và
b
. Khi đó
(a) Nếu
gcd( , ) 1
a b
thì tồn tại ,x y
sao cho
1
ax by
.
(b) Nếu gcd( , )
a b d
thì tồn tại ,x y
sao cho
ax by d
.
Chứng minh
(a) Thực ra yêu cầu bài toán tương đương với việc chứng minh sự tồn tại của x
sao cho
1 (mod )
ax b
.
Tuy nhiên theo Nhận xét 2 (b) thì số
x
cần chọn chính là nghịch đảo của
a
mod
b
.
Khi đó ta đặt 1
ax
y
b
thì y
và
1
ax by
.
(b) Đặt
1
a a d
và
1
b b d
thì 1 1
gcd( , ) 1
a b
. Khi đó tồn tại nghịch đảo
x
của
1
a
mod
1
b
.
Đặt
1
1
1
a x
y
b
thì y
và 1 1
1
a x b y
, do đó
ax by d
.
Lưu ý. Hãy chỉnh sửa chứng minh (a) để thu được khẳng định sau
“Nếu
gcd( , ) 1
a b
thì tồn tại ,x y
sao cho
1
ax by
”.
Ví dụ 1.7. Cho
, ,
abc
là các số nguyên dương thỏa mãn
2
1 ( )( 2 )
c a a b a b
.
Chứng minh rằng
b
chia hết cho
12
.
Hướng dẫn giải
Dễ thấy nếu
b
không chia hết cho
3
thì
, , 2
a a b a b
là một hệ thặng dư đầy đủ modulo
3
,
khi đó
( )( 2 ) 3
a a b a b
. Bởi vậy theo giả thiết ta có 2
1 3
c
, vô lí vì 2
0,1 (mod3)
c
.
Giả sử
a
chẵn, khi đó ( 2 )
4
a a b
, thành ra 21
4
c
, vô lí vì 2
0,1 (mod 4)
c
.
Do đó
a
phải là số lẻ.
Theo kết quả Bài 3.10 (a) (§1) thì 2
1
c
không có ước nguyên tố dạng
4 3
k
nên hai ước lẻ
a
và
2
a b
của 2
1
c
phải có dạng
4 1
k
, tức là
2 1 (mod 4)
a a b
.
Từ đó suy ra
2 0 (mod 4)
b
nên
b
chẵn. Nhưng khi đó thì
a b
là ước lẻ của 2
1
c
nên
a b
cũng phải có dạng
4 1
k
, nghĩa là
1 (mod 4)
a b
, kéo theo
0 (mod 4)
b
, hay
4
b
.
Trang 4
BÀI TẬP ĐỀ XUẤT
Bài 1.1. Cho
p
là một số nguyên tố lẻ. Chứng minh
(a)
1
0, 1, 2,...,
2
p
là một hệ thặng dư đầy đủ mod
p
.
(b)
2
2 2
1
1 ,2 ,..., 2
p
là một hệ gồm các thặng dư phân biệt mod
p
.
(c)
2 2 2 2
1 ,2 ,...,( 1) ,
p p
không là một hệ thặng dư đầy đủ mod
p
.
Bài 1.2. [May Olympiad 2021] Theo quan niệm của nhiều người, Thứ Sáu ngày
13
được cho là
ngày xui xẻo và thường đem lại tai họa bất ngờ cho họ.
(a) Chứng minh rằng trong một năm dương lịch có ít nhất một ngày là Thứ Sáu ngày
13
.
(b) Trong một năm có thể có bao nhiêu ngày là Thứ Sáu ngày
13
?
Bài 1.3. Cho
p
là một số nguyên tố lẻ và 1 2
, ,...,
p
a a a
là các số nguyên. Chứng minh nếu
1
p
i
i
a
là một hệ đầy đủ mod
p
thì
(a) 1 2
... 0 (mod )
p
a a a p
.
(b) 2 2 2
1 2
... 0 (mod )
p
a a a p
, với
3
p
.
Bài 1.4. Tìm tất cả các số nguyên dương
n
sao cho số
36 6
n
là tích của các số nguyên dương
liên tiếp.
Bài 1.5. Cho
,
x y
là các số nguyên và
p
là một số nguyên tố. Giả sử tồn tại các số nguyên dương
,
m n
nguyên tố cùng nhau thỏa mãn
(mod )
mx ny p
. Chứng minh rằng tồn tại một số nguyên
z
sao cho
(mod )
x nz p
và
(mod )
y mz p
.
Bài 1.6. [Putnam MC 2017] Giả sử
S
là tập con nhỏ nhất của
thỏa mãn các điều kiện
(i) 2
S
.
(ii) Với mọi n
, nếu 2
n S
thì
n S
.
(iii) Với mọi n
, nếu
n S
thì 2
( 5)
n S
.
(a) Chứng minh rằng 3,4,6
S
.
(b) Tìm tập hợp
S
.
2. Định lí Fermat nhỏ1
Định lí 2.1. [Định lí Fermat] Cho
p
là một số nguyên tố. Khi đó
(a) Nếu x
và
x
không chia hết cho
p
thì 1
1 (mod )
p
x p
.
(b) Nếu x
thì
(mod )
p
x x p
.
Chứng minh
Nếu để ý kĩ ta sẽ thấy hai mệnh đề (a) và (b) là tương đương, nên ta chỉ cần chứng minh (a).
Do
gcd( , ) 1
x p
nên theo Mệnh đề 1 (b) thì
.0, .1,..., .( 1)
x x x p
là một hệ đầy đủ mod
p
.
1 Định lí này được gọi là định lí Fermat nhỏ (Fermat’s little theorem) để phân biệt với định lí Fermat lớn hay định lí
cuối cùng của Fermat (Fermat’s last theorem) – một bài toán kinh điển gây khó dễ cho nhân loại trong suốt ba thế kỉ.
Trang 5
Bởi vậy
.1, .2,..., .( 1) 1, 2,..., 1 (mod )
x x x p p p
.
Khi đó
( .1)( .2)...( .( 1)) 1.2...( 1) (mod )
x x x p p p
,
hay
1
( 1)! ( 1)! (mod )
p
p x p p
.
Do
( 1)! 1.2...( 1)
p p
nguyên tố cùng nhau với
p
nên ta có
1
1 (mod )
p
x p
.
Ví dụ 2.1. Cho n
. Chứng minh 12 6
11 1
n
chia hết cho
13
.
Hướng dẫn giải
Theo định lí Fermat nhỏ ta có 12
11 1 (mod13)
. Do đó
12 6 12 6 6 6
11 1 (11 ) .11 1 11 1 ( 2) 1 65 0 (mod13)
n n
.
Ví dụ 2.2.
(a) Chứng minh nếu
p
là số nguyên tố dạng
4 3
k
thì 2
1 (mod )
x p
.
Từ đó chứng minh “Nếu
p
là số nguyên tố dạng
4 3
k
, ,x y
và 2 2
x y p
thì ,
x y p
”.
(b) Chứng minh nếu
p
là số nguyên tố dạng
8 5
k
thì 4
1 (mod )
x p
.
(c) Tìm tất cả các cặp số nguyên dương
( , )
x y
sao cho 4 4
1997 1999
x y
.
Hướng dẫn giải
(a) Khẳng định thứ nhất đã được chứng minh trong Bài 3.10 (a) (§1).
Bây giờ ta chứng minh khẳng định thứ hai. Giả sử
x
không chia hết cho
p
.
Theo giả thiết thì 2 2
x y p
nên
2 2
(mod )
y x p
(1)
.
Mà
gcd( , ) 1
x p
nên tồn tại nghịch đảo
1
:
a x
của
x
mod
p
.
Từ
(1)
ta có
2 2
( ) ( ) 1 (mod )
ay ax p
.
Điều này dẫn tới mâu thuẫn với khẳng định thứ nhất. Vậy
x p
, do đó
y p
.
(b) Giả sử trái lại 4
1 (mod )
x p
. Đặt
8 5
p k
thì
1 8 4 4 2 1 2 1
( ) ( 1) 1 (mod )
p k k k
x x x p
,
mâu thuẫn với định lí Fermat nhỏ.
(c) Từ kết quả (b) ta có thể chứng minh nếu
p
là số nguyên tố dạng
8 5
k
,
x
và
y
là các số
nguyên thỏa mãn 4 4
x y p
thì ,
x y p
.
Để ý rằng
1997
là số nguyên tố dạng
8 5
k
nên 4 4
1997 , 1997
x y x y
.
Lại vì
1999
là số nguyên tố dạng
4 3
k
nên 4 4
1999 , 1999
x y x y
Vậy tất cả các cặp số cần tìm là các cặp bội nguyên dương của số
1997 1999
.