ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

TRỊNH THỊ KIỀU VÂN

MỘT SỐ ỨNG DỤNG CỦA ĐỒNG DƯ THỨC

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - NĂM 2015


ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

TRỊNH THỊ KIỀU VÂN

MỘT SỐ ỨNG DỤNG CỦA ĐỒNG DƯ THỨC

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60.46.01.13

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học
TS. NGUYỄN VĂN HOÀNG

THÁI NGUYÊN - NĂM 2015



.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.

3
3
6
7
11

.
.
.
.
.

16
16
22
30
33
38

Kết luận

45

Tài liệu tham khảo


Hình 1
16
2
Hình 2
17
3
Hình 3
18
4
Hình 4
18
5
Hình 5
19
6
Hình 6
19
7
Hình 7
20
8
Hình 8
20
9
Hình 9
21
10 Hình 10
21
11 Hình 11
23

đồng dư thức còn được ứng dụng to lớn trong đời sống thực tế như: Trong
lĩnh vực truyền thông phát hiện và sửa các lỗi trong thông điệp truyền đi.
Kiểm tra chữ số thường được sử dụng để phát hiện các sai sót trong chuỗi
các chữ số thập phân như kiểm tra serial của tờ tiền giấy trong ngân hàng,
nhà xuất bản sách, thư viện, và các công ty... Với những công lao, đóng góp
lớn của Gauss, tờ tiền Mark của Đức đã in hình ảnh nhà toán học Gauss và
đường cong chuẩn tắc nổi tiếng của ông ấy. Chúng ta thường không nhận
thấy quan hệ đồng dư trong cuộc sống hàng ngày. Qua luận văn này ngoài
những ứng dụng đã biết tôi muốn nêu thêm một số ứng dụng của đồng dư
thức trong thực tiễn đời sống.
Nội dung của luận văn chia thành 2 chương đề cập đến các vấn đề sau
đây:
Chương 1: Trình bày các kiến thức cơ bản của đồng dư thức và một vài
áp dụng của đồng dư thức trong số học như: Nghiên cứu dấu hiệu chia hết,
tìm số dư trong phép chia. Chương này nghiên cứu các mối quan hệ đồng


2

dư. Các mối quan hệ đồng dư có liên quan chặt chẽ, nó được sử dụng xuyên
suốt lý thuyết số.
Chương 2: Một số ứng dụng của đồng dư thức trong thực tiễn đời sống.
Các ứng dụng của đồng dư thức, là một phần của cuộc sống hàng ngày: Ứng
dụng trong thiết kế mô hình, kiểm tra mã số của sách ISBN, trong chò chơi
xếp p quân hậu trên bàn cờ pxp, sắp lịch trong giải đấu vòng tròn một lượt,
tìm ngày, tháng, năm trong lịch vạn niên.

Thái Nguyên, tháng 4 năm 2015
Tác giả



4

a + c ≡ b + c (mod m),
ac ≡ bc (mod m),

a − c ≡ b − c (mod m),
a2 ≡ b2 (mod m).

(iii) Nếu a ≡ b (mod m), thì an ≡ bn (mod m) với n là số nguyên dương.
Tính chất 1.1.5.
(i) Nếu ac ≡ bc (mod m) và (c, m) = 1, thì a ≡ b (mod m).
(ii) Nếu ac ≡ bc (mod m) và (c, m) = d, thì a ≡ b (mod

m
d ).

Chứng minh. (ii) Giả sử ac ≡ bc (mod m), và có (c, m) = d. Ta có
m|(ac − bc), vì vậy ac − bc = km (k ∈ Z) nên c(a − b) = km. Chia cả hai
vế cho d ta được dc (a − b) = k md . Biết rằng ( dc , md ) = 1, do đó md |(a − b).
Vậy a ≡ b (mod m).
Tính chất 1.1.6. Nếu a ≡ b (mod m1 ), a ≡ b (mod m2 ), ..., a ≡ b
(mod mk ), thì a ≡ b (mod [m1 , m2 , ..., mk ]).
Hệ quả 1.1.7. Nếu a ≡ b (mod m1 ), a ≡ b (mod m2 ), . . . , a ≡ b (mod mk ),
với m1 , m2 , . . . , mk đôi một nguyên tố cùng nhau. Khi đó

a ≡ b (mod m1 m2 . . . mk ).
Hệ quả 1.1.8. Mỗi số nguyên có ít nhất 0, 1, 2, ..., (m − 1) đồng dư theo
môđun m.
Ví dụ 1.1.9 (Tìm số thứ sáu ngày mười ba trong một năm). Đồng dư có

(mod 7). Vì vậy, ngày 13 tháng 12 năm 2000 (thứ Tư), phải cộng thêm sáu
ngày để xác định ngày của 13 tháng ba năm 2001; Đó là ngày (3 + 6) =
ngày 2 = ngày thứ Ba.
Chú ý rằng nhiều giá trị khác nhau của ti theo môđun 7 là 3, 6, 6, 2, 4,
0, 2, 5, 1, 3, 6,và 1; Chúng bao gồm các thặng dư nhỏ nhất theo môđun 7.
Biết ngày 13 tháng 12, chúng ta có thể sử dụng các thặng dư nhỏ nhất để
xác định ngày mười ba của mỗi tháng Mi trong một năm không nhuận.
Bảng tóm tắt tương ứng với mỗi lựa chọn của ngày 13 tháng của mỗi
tháng trong một năm không nhuận, tương ứng với mọi lựa chọn của ngày 13
tháng 12 của năm trước. Từ bảng ta thấy có nhiều nhất ba ngày thứ Sáu
ngày 13 trong một năm không nhuận.

Đối với một năm nhuận, nhiều giá trị khác nhau của di là 3, 3, 1, 3, 2, 3, 2,
3, 3, 2, 3, và 2; Các giá trị tương ứng của ti là 3, 6, 0, 3, 5, 1, 3, 6, 2, 4, 0, và
2. Từ đây chúng ta cũng có thể xây dựng một bảng tương tự cho một năm
nhuận.


6

Định nghĩa 1.1.10 (Các lớp đồng dư). Tập thương của tập hợp số nguyên
Z trên quan hệ đồng dư theo môđun m được gọi là tập hợp các lớp thặng dư
môđun m, kí hiệu là Zm . Mỗi phần tử của Zm được gọi là một lớp thặng dư
môđun m. Ứng với mỗi A ∈ Zm , tồn tại a ∈ Z để ta có A = a; Mỗi x ∈ A
được gọi là một thặng dư (mod m).
Tính chất 1.1.11.
(i) Zm = {0, 1, . . . , m − 1}.
(ii) Mỗi phần tử của Zm là hợp của k phần tử phân biệt của Zkm (với k > 1).
Định nghĩa 1.1.12 (Hệ thặng dư đầy đủ). Tập hợp A, gồm những số nguyên
được lấy ra từ mỗi lớp thặng dư môđun m của Zm (có một và chỉ một số


1.2.1

Nghiên cứu dấu hiệu chia hết

Dấu hiệu chia hết là một trong những áp dụng trực tiếp của đồng dư thức.
Cho số nguyên dương n khác 0 được viết trong hệ thập phân

n = nk nk−1 ...n1 n0 = nk 10k + nk−1 10k−1 + ...n1 10 + n0 .
Để kiểm tra xem số nguyên n chia hết cho 10, 5, 2i , 3, 9 và 11 hay không?
Ta đi tìm điều kiện ràng buộc giữa các chữ số n0 , n1 , ..., nk−1 , nk ? Mở đầu ta
đi tìm hiểu dấu hiệu chia hết cho 10.

Dấu hiệu chia hết cho 10
Cho số

n = nk nk−1 ...n1 n0 = nk 10k + nk−1 10k−1 + ...n1 10 + n0
trong đó 1 ≤ nk ≤ 9, 0 ≤ ni ≤ 9 với mọi i = 0, 1, 2, ..., k − 1.
Ta có 10 ≡ 0 (mod 10) nên ni 10i ≡ 0 (mod 10) (với i = 0, 1, 2, ..., k −1).
Khi đó

n = nk 10k + nk−1 10k−1 + ...n1 10 + n0 ≡ n0

(mod 10).

Như vậy ta suy được n ≡ 0 (mod 10) khi và chỉ khi n0 ≡ 0 (mod 10) hay
n0 = 0. Vậy một số nguyên chia hết cho 10 khi và chỉ khi chữ số đơn vị của
nó là số 0.

Dấu hiệu chia hết cho 5

Ví dụ 1.2.1. Số n chia hết cho 2 khi và chỉ khi chữ số n0 là chia hết cho 2;
n chia hết cho 4 nếu số có hai chữ số n1 n0 là chia hết cho 4; n chia hết cho
8 nếu số có ba chữ số n2 n1 n0 là chia hết cho 8.
Cụ thể xét số n = 343.506.076. Vì 2 | 6 ⇒ 2 | n; Lại vì 4 | 76 ⇒ 4 | n;
Nhưng vì 076 không chia hết cho 8 ⇒ n không chia hết cho 8.

Dấu hiệu chia hết cho 3 và chia hết cho 9
Ta có 10 ≡ 1 (mod 3), nên 10i ≡ 1 (mod 3) với mọi số nguyên dương i.
Do đó ni 10i ≡ ni (mod 3) với mọi i = 0, 1, . . . , k . Khi đó

n = nk 10k + nk−1 10k−1 + . . . + n1 10 + n0 ≡ nk + nk−1 + . . . + n1 + n0

(mod 3).

Từ đó ta suy ra được n ≡ 0 (mod 3) khi và chỉ khi nk + nk−1 + ...n1 + n0 ≡
0 (mod 3).
Vậy một số nguyên dương chia hết cho 3 khi và chỉ khi tổng các chữ số
của nó chia hết cho 3.
Tương tự, ta có 10 ≡ 1 (mod 9) nên 10i ≡ 1 (mod 9) và ni 10i ≡ ni
(mod 9) với mọi i = 0, 1, 2, . . . , k . Khi đó

n = nk 10k + nk−1 10k−1 + . . . + n1 10 + n0 ≡ nk + nk−1 + . . . + n1 + n0

(mod 9).

Từ đó ta được n ≡ 0 (mod 9) nếu và chỉ nếu nk + nk−1 + . . . + n1 + n0 ≡ 0
(mod 9).


9

Phương pháp kiểm tra theo môđun 9
Trong thực tế cuộc sống đồng dư thức còn được các kế toán sử dụng trong
việc kiểm tra phát hiện các tính toán lỗi. Kỹ thuật này dựa trên thực tế là
mỗi số nguyên là đồng dư với tổng các chữ số của nó theo môđun 9.
Ví dụ 1.2.4. Hãy kiểm tra tính đúng sai của kết quả sau đây:
1) 35897+750971+908085=1684953
2) 4556 × 3444 = 15745014


10

Bài giải. 1) Ta có

35897 ≡ 3 + 5 + 8 + 9 + 7 ≡ 5

(mod 9)

750971 ≡ 7 + 5 + 0 + 9 + 7 + 1 ≡ 2

(mod 9)

908085 ≡ 9 + 0 + 8 + 0 + 8 + 5 ≡ 3

(mod 9)

≡ 5+2+3
≡ 1

(mod 9)


(mod 9).

Kết quả trên cho ta thấy khi xét đồng dư môđun 9 thì tích đưa ra là chính
xác, điều đó chỉ cho phép ta dự đoán rằng tích trên tương đối là đúng mà
thôi. Điều này đúng vì sự thay đổi lại thứ tự các chữ số trong một số nguyên
đều dẫn đến cùng kết quả khi lấy môđun 9. Câu trả lời cho kết quả trên phải
là 6.833.008 (đảo hai số cuối). Vậy phương pháp kiểm tra theo môđun 9 chỉ
ra rằng "kết quả" hoặc là chắc chắn sai, hoặc là có lẽ đúng.
Chú ý 1.2.5. Mỗi số nguyên có dạng n = 9k + r, (0 ≤ r < 9), nên
n ≡ r (mod 9); Do đó n2 ≡ r2 (mod 9). Mà r ≡ r − 9 (mod 9), 02 ≡ 0
(mod 9), (±1)2 ≡ 1 (mod 9), (±2)2 ≡ 4 (mod 9), (±3)2 ≡ 0 (mod 9),
(±4)2 ≡ 7 (mod 9). Như vậy, n2 chỉ có thể là đồng dư với 0, 1, 4, hoặc 7
(theo môđun 9). Vậy một số a muốn là số chính phương thì tổng các chữ số
của nó phải đồng dư với một trong các số 0,1,4,7 (theo môđun 9). Điều ngược


11

lại của lập luận trước là sai nếu một số N có kết quả đồng dư với 1 hoặc 4,
hoặc 7, hoặc 9 theo môđun 9 thì N chưa chắc là chính phương. Chẳng hạn,
số 43 đồng dư với 7 môđun 9, nhưng số 43 không phải là số chính phương.
Ví dụ 1.2.6. Chứng minh rằng N = 54.893.534.046 không là số chính
phương.
Bài giải. Ta có N = 54893534046
≡ 5 + 4 + 8 + 9 + 3 + 5 + 3 + 4 + 0 + 4 + 6 (mod 9)
≡ 51 (mod 9)
≡ 5 + 1 (mod 9)
≡ 6 (mod 9).
Vì số dư của N theo môđun 9 là 6, nên N không phải là số chính phương.
Ví dụ 1.2.7. Chứng minh rằng N = 22000 + 22001 + 22003 + 22008 không phải

hợp. Sử dụng đồng dư thức trong bài toán tìm số dư trong phép chia, chứng
minh sự chia hết đã làm giảm bớt các tính toán phức tạp, bài toán trở nên
đơn giản, dễ dàng hơn rất nhiều. Sau đây ta sẽ đi tìm hiểu một số phương
pháp được sử dụng tìm số dư.


12

Ví dụ 1.2.8. Tìm số dư khi chia 1! + 2! + 3! + . . . + 1000! cho 12.
Bài giải. Ta có 4! = 4.3.2.1 ≡ 0 (mod 12). Vậy với mọi k ≥ 4, thì k! ≡ 0
(mod 12). Khi đó:

1! + 2! + 3! + .... + 1000! ≡ 1! + 2! + 3! + 0 + 0 + 0 + ... + 0
≡ 1+2+6
≡ 9

(mod 12)

(mod 12)

(mod 12).

Vậy số dư cần tìm khi chia 1! + 2! + 3! + . . . + 1000! cho 12 là 9.

Số mũ modular
Số mũ modular là một phương pháp hiệu quả để xác định xem số bn có
chia được cho m không? Phương pháp được dựa trên biểu diễn nhị phân của
số n = (nk nk−1 ...n1 n0 )2 bằng cách thực hiện bình phương liên tiếp số dư bé
nhất của bni khi chia cho m (trong đó 0 ≤ i ≤ k ). Khi đó ta có
k

3247 = 31.2 .31.2 .31.2 .31.2 .31.2 .31.2 .31
= 3128+64+32+16+4+2+1
= 3128 .364 .332 .316 .34 .32 .31 .
Bây giờ, ta sẽ đi tìm số dư của 32 (theo môđun 25) và của các bình phương
liên tiếp của nó (theo môđun 25):

32 ≡ 9

(mod 25)

34 ≡ 92 ≡ 6

38 ≡ 62 ≡ 11

(mod 25)

316 ≡ 112 ≡ 21

332 ≡ 212 ≡ 16

(mod 25)

364 ≡ 162 ≡ 6

3128 ≡ 62 ≡ 11

(mod 25)

(mod 25)
(mod 25)

1

22015 = 21.2 .21.2 .21.2 .21.2 .21.2 .21.2 .21.2 .21.2 .21.2 .21
= 21024 .2512 .2256 .2128 .264 .216 .28 .24 .22 .21 .
Bây giờ, ta sẽ đi tìm dư của 22 theo môđun 7 rồi thực hiện bình phương liên
tiếp số dư bé nhất
22 ≡ −3 (mod 7)
24 ≡ (−3)2 ≡ 2 (mod 7)
28 ≡ 22 ≡ −3 (mod 7)
216 ≡ (−3)2 ≡ 2 (mod 7)
232 ≡ 22 ≡ −3 (mod 7)
264 ≡ (−3)2 ≡ 2 (mod 7)
2128 ≡ 22 ≡ −3 (mod 7)
2256 ≡ (−3)2 ≡ 2 (mod 7)
2512 ≡ 22 ≡ −3 (mod 7)
21024 ≡ (−3)2 ≡ 2 (mod 7).
Suy ra 22015 ≡ (−3)4 .25 ≡ (−6)4 .2 ≡ 14 .2 ≡ 2 (mod 7) (vì khuyết 232 ).
Vậy số dư cần tìm của 22015 khi chia cho 7 là 2.

Tháp lũy thừa
Việc sử dụng đồng dư thức khi tìm số dư, hay tìm chữ số tận cùng còn
được mở rộng cho số có nhiều số mũ, đó là phương pháp sử dụng tháp lũy
thừa. Ví dụ sau đây sẽ cho ta thấy tìm chữ số tận cùng một cách nhanh
chóng, sự hiệu quả khi sử dụng phương pháp.
1999

Ví dụ 1.2.11. Tìm chữ số tận cùng của số N = 19971998
c

c

(mod
(mod
(mod

10)
10)
10)
10)

khi
khi
khi
khi

a ≡ 0 (mod 4)
a ≡ 1 (mod 4)
a ≡ 2 (mod 4)
a ≡ 3 (mod 4).

Ta xét số 1998, ta thấy rằng 1998 ≡ 2 (mod 4), vậy 1998n ≡ 2n (mod 4).
Do đó nếu n ≥ 2 thì 1998n ≡ 0 (mod 4). Vì 1999 ≥ 2, nên 19981999 ≡ 0
(mod 4).
Do đó N ≡ 1 (mod 10). Vậy chữ số tận cùng của N là 1.
Ví dụ 1.2.12. Chứng minh rằng 11.14n + 1 là hợp số với mọi số tự nhiên n.
Bài giải. Đặt N = 11.14n + 1. Giả sử n là số chẵn. Ta có, vì 14 ≡ −1
(mod 3), nên 14n ≡ 1 (mod 3). Khi đó N = 2.1 + 1 ≡ 0 (mod 3), nên
3 | N . Lưu ý rằng N ≥ 12, do đó N có nhiều hơn hoặc bằng hai ước thực sự
là 3 và một số nữa. Chứng tỏ N là hợp số khi n chẵn.
Xét khi n là số lẻ, ta có 14 ≡ −1 (mod 5), 14n ≡ −1 (mod 5). Khi đó
N = 1.(−1) + 1 ≡ 0 (mod 5), nên ta có 5 | N . Như vậy N có nhiều hơn

a) 327.723
b) 639.576
c) 2.197.584
1.4. Trong các số sau đây, số nào chia hết cho 11?
a) 43.979
b) 502.458
c) 1.928.388
1.5. Tìm số dư trong phép chia:
a) 531 cho 12.
b) 235 cho 7.
c) 231001 cho 17.
d) 191976 cho 23.
1.6. Kiểm tra kết quả của các tính toán trên

a)

58807
83291
+601756

b)

7958036

c)

2076

−2309859


2.1

Thiết kế mô hình

Trong thực tế cuộc sống số học Modular được sử dụng để tạo ra những
thiết kế đẹp. Chúng ta sẽ khám phá ba mẫu thiết: Ngôi sao m-cánh, thiết kế
(m, n)-thặng dư, và thiết kế hoa văn trên chăn, màn và gối.

Thiết kế ngôi sao m-cánh
Để xây dựng một ngôi sao m-cánh, ta đánh dấu m điểm cách đều nhau
trên một đường tròn lớn, và đặt tên cho các điểm đó lần lượt bởi các số
0, 1, . . . , m − 1 (thuộc hệ thặng dư không âm nhỏ nhất) môđun m. Chọn
một thặng dư i (mod m) sao cho (i, m) = 1. Nối mỗi điểm x với điểm x + i
(mod m). Bây giờ ta tô màu vào các miền khác nhau bên trong đường tròn
với một số màu khác. Bạn sẽ nhận được một ngôi sao m−cánh đẹp đẽ. Hình
1 dưới đây thể hiện một ngôi sao 7-cánh và một ngôi sao 12-cánh.

Hình 1. Sao 7-cánh và sao 12-cánh.


17

Thiết kế (m, n)-thặng dư
Để xây dựng một thiết kế (m, n)-thặng dư với 1 ≤ n < m và (m, n) = 1,
ta chọn m − 1 điểm cách đều nhau trên một đường tròn, đặt tên cho các
điểm đó bởi các số từ 1 đến m − 1, và nối mỗi điểm x với điểm nx (mod m).
Sau đó tô màu vào các miền khác nhau đó theo cách có hệ thống để tạo được
một thiết kế vui nhộn.
Ví dụ 2.1.1. Để xây dựng một thiết kế (19, 9)−thặng dư, ta chia đường
tròn lớn thành 18 phần bằng nhau và đánh dấu điểm chia lần lượt bởi các số

18

Hình 3. Hoa văn (17,6)-thặng dư và (17,7)-thặng dư.

Hình 4. Hoa văn (17,8)-thặng dư và (17,16)-thặng dư.

Thiết kế hoa văn
Ta có thể sử dụng các bảng toán cộng và nhân cho tập các các lớp thặng
dư nhỏ nhất môđun m để sinh ra các thiết kế hoa văn nghệ thuật và thú vị.
Ví dụ 2.1.2. Chọn m = 9. Xây dựng bảng cộng cho tập các thặng dư nhỏ
nhất từ 0 đến 8 (môđun 9), như bảng dưới đây.


19

+
0
1
2
3
4
5
6
7
8

0
0
1
2

3
4
5
6
7
8
0
1
2

4
4
5
6
7
8
0
1
2
3

5
5
6
7
8
0
1
2
3

4
5
6
7

Ta gán cho mỗi số từ 0 đến 8 một hình cơ bản, như vậy ta có 9 hình cơ bản
biểu diễn cho các số từ 0 đến 8 như sau.

Hình 5. Các hình thiết kế cơ bản.
Bây giờ ta thay thế mỗi phần tử trong bảng toán cộng bởi phần tử thiết kế
tương ứng của nó. Từ đó ta thu được một hình mẫu thiết kế đẹp.

Hình 6. Hoa văn tạo bởi bảng toán của nhóm Z9 .
Từ hoa văn trên bằng cách sử dụng các phép quay các góc 90, 180, 270 độ,


20

ta tạo ra thêm ba hoa văn mới; Sau đó ghép chúng lại với nhau ta thu được
mẫu hoa văn mới như hình sau.

Hình 7. Thiết kế hoa văn dựa trên các phần tử môđun 9.
Ví dụ 2.1.3. Thay vì sử dụng lưới các hình vuông, ta có thể sử dụng lưới
các hình chữ nhật, chẳng hạn như ở hình

Hình 8. Lưới hình chữ nhật của bảng toán (môđun 5).
và sử dụng các hình thiết kế cơ bản như hình sau để phát triển thiết kế cơ
bản cho môđun 5 (khi đưa các hình cơ bản vào lưới ta có thể kéo hoặc co
các chiều cho phù hợp kích thước hình chữ nhật).