Luận án tiến sĩ lý thuyết đồng dư và ứng dụng trong mã sửa sai
- 93 trang
- file .pdf
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
––––––––––––––––––
NGUYỄN TRỌNG NAM
LÝ THUYẾT ĐỒNG DƢ
VÀ ỨNG DỤNG TRONG MÃ SỬA SAI
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2009
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
––––––––––––––––––
NGUYỄN TRỌNG NAM
LÝ THUYẾT ĐỒNG DƢ
VÀ ỨNG DỤNG TRONG MÃ SỬA SAI
Chuyên ngành: TOÁN SƠ CẤP
Mã số: 60.46.40
LUẬN VĂN THẠC SĨ TOÁN HỌC
Ngƣời hƣớng dẫn khoa học: PGS.TS TẠ DUY PHƢỢNG
THÁI NGUYÊN - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
MỤC LỤC
LỜI NÓI ĐẦU .............................................................................................. 1
Chƣơng 1: LÝ THUYẾT ĐỒNG DƢ .......................................................... 3
§ 1. Quan hệ đồng dƣ ................................................................................... 3
1.1. Định nghĩa đồng dư ................................................................................. 3
1.2. Các tính chất của quan hệ đồng dư .......................................................... 4
§ 2. Thặng dƣ ................................................................................................ 7
2.1. Tập các lớp thặng dư ............................................................................... 7
2.2. Các tính chất của lớp thặng dư................................................................. 7
2.3. Tập các lớp thặng dư nguyên tố với môđun ............................................. 9
2.4. Vành các lớp thặng dư ............................................................................. 9
§ 3. Hệ thặng dƣ đầy đủ - Hệ thặng dƣ thu gọn........................................ 11
3.1. Hệ thặng dư đầy đủ................................................................................ 11
3.2. Hệ thặng dư thu gọn .............................................................................. 13
3.3. Các định lí quan trọng ........................................................................... 16
§ 4. Phƣơng trình đồng dƣ ......................................................................... 17
4.1. Các khái niệm chung ............................................................................. 17
4.2. Phương trình và hệ phương trình đồng dư bậc nhất một ẩn .................... 23
4.2.1. Phương trình đồng dư bậc nhất một ẩn ............................................... 23
4.2.2. Hệ phương trình đồng dư bậc nhất một ẩn .......................................... 26
4.3. Phương trình đồng dư bậc cao theo môđun nguyên tố .......................... 31
4.3.1. Nhận xét ............................................................................................. 31
4.3.2. Phương trình bậc cao theo môđun nguyên tố ...................................... 32
Chƣơng 2: ỨNG DỤNG CỦA LÝ THUYẾT ĐỒNG DƢ TRONG
MÃ SỬA SAI ...................................................................................... 36
§ 1. Khái niệm mã ....................................................................................... 36
§ 2. Những ví dụ về mã ............................................................................... 39
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
2.1. Mã lặp ................................................................................................... 39
2.2. Mã chẵn lẻ ............................................................................................. 41
2.3. Mã vạch ................................................................................................ 44
§ 3. Khoảng cách Hamming ...................................................................... 48
§ 4. Mã tuyến tính ....................................................................................... 53
4.1. Mã nhị phân tuyến tính .......................................................................... 53
4.2. Biểu diễn ma trận của các mã nhị phân .................................................. 55
4.3. Thuật toán hội chứng giải mã cho các mã nhị phân ............................... 65
4.4. Mã nhị phân Hamming .......................................................................... 67
4.5. Các tính chất của mã nhị phân Hamming [n,k] ...................................... 70
4.6. Các p-mã Hamming ............................................................................... 71
4.7. Các tính chất của p-mã Hamming [n,k] ................................................. 74
§ 5. Mã thập phân...................................................................................... 77
5.1. Mã số sách tiêu chuẩn quốc tế (ISBN) ................................................... 77
5.2. Mã sửa lỗi đơn ....................................................................................... 82
5.3. Mã sửa lỗi kép ....................................................................................... 84
KẾT LUẬN ................................................................................................. 88
TÀI LIỆU THAM KHẢO.......................................................................... 89
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
1
LỜI NÓI ĐẦU
Có thể nói, số học, lý thuyết số là một trong những kiến thức toán học
lâu đời nhất. Từ trước tới nay, người ta thường coi lý thuyết số như một lĩnh
vực đẹp, nhưng thuần túy lý thuyết, của toán học. Với sự phát triển của khoa
học máy tính và công nghệ thông tin, lý thuyết số đã đóng góp những ứng
dụng thực tế bất ngờ và quan trọng, đặc biệt trong lĩnh vực mã hóa thông tin.
Nhiều khía cạnh khác nhau của mã hóa thông tin được các nhà toán học
và tin học quan tâm. Thường thường thông tin được mã hóa qua dãy các chữ
số trong hệ đếm cơ số 2, cơ số 10, hoặc cơ số p nào đó. Trong quá trình
truyền tin hoặc nhận tin, vì nhiều lý do, thông tin có thể bị sai lệch. Thí dụ,
một tin nhắn được mã hóa trong cơ số 2 khi truyền đi bị sai một lỗi (lỗi đơn)
thì điều này có nghĩa là chữ số 1 tại vị trí nào đó đã bị đổi thành chữ số 0 hoặc
ngược lại. Một trong những vấn đề cần giải quyết là phát hiện ra các lỗi sai và
sửa chúng.
Vì yêu cầu thực tiễn đó, lý thuyết mã sửa sai đã ra đời, phát triển và có
những ứng dụng thực tiễn quan trọng. Để xây dựng lý thuyết mã sửa sai, các
nhà toán học và khoa học máy tính đã sử dụng nhiều thành tựu của toán học
hiện đại (số học, toán rời rạc, đại số tuyến tính,...,) đặc biệt là số học trên tập
số nguyên, trong đó có lý thuyết đồng dư.
Luận văn này có mục đích tìm hiểu và trình bày những kiến thức cơ
bản nhất của lý thuyết mã sửa sai trên cơ sở lý thuyết đồng dư và lý thuyết
trường hữu hạn.
Luận văn gồm hai chương.
Chương 1 trình bày các kiến thức cơ bản nhất của lý thuyết đồng dư
và lý thuyết trường hữu hạn, chủ yếu dựa theo tài liệu [2], có tham khảo thêm
các tài liệu [4] và [6].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
2
Chương 2 trình bày một số vấn đề cơ bản của mã sửa sai: khoảng cách
Hamming; phát hiện và sửa lỗi; các thuật toán giải mã; mã hoàn hảo; mã
tuyến tính và ma trận kiểm tra, xây dựng mã tuyến tính,...
Nội dung của Chương 2 trình bày chủ yếu dựa theo tài liệu [6], có tham
khảo thêm các tài liệu [1] và [7]. Ngoài ra, chúng tôi cũng quan tâm đến khía
cạnh thực tế của vấn đề: mã vạch, mã hàng hóa, mã sách tiêu chuẩn quốc
tế,.... Chúng tôi cũng cố gắng tìm hiểu, tuy chưa được đầy đủ, các mã hàng
hóa, mã văn hóa phẩm của Việt Nam và kiểm nghiệm các tiêu chuẩn giải mã
cho các ví dụ cụ thể của các mã này.
Luận văn được hoàn thành dưới sự hướng dẫn khoa học của PGS TS Tạ
Duy Phượng. Xin được tỏ lòng cám ơn chân thành nhất tới Thầy.
Tác giả xin cám ơn chân thành tới Trường Đại học Khoa học Thái
Nguyên, nơi tác giả đã nhận được một học vấn sau đại học căn bản.
Và cuối cùng, xin cám ơn gia đình, bạn bè, đồng nghiệp đã cảm thông,
ủng hộ và giúp đỡ trong suốt thời gian tác giả học Cao học và viết luận văn.
Hà Nội, ngày 19 tháng 9 năm 2009
Tác giả
Nguyễn Trọng Nam
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
3
Chƣơng 1
LÝ THUYẾT ĐỒNG DƢ
§1. Quan hệ đồng dƣ
1.1. Định nghĩa đồng dƣ
Kí hiệu là tập hợp các số nguyên.
Định nghĩa
Cho m là một số nguyên dương, a và b là hai số nguyên. Ta nói a và b
đồng dư với nhau theo môđun m nếu trong phép chia a và b cho m ta được
cùng một số dư, nghĩa là có các số nguyên q1 , q2 , r với 0 r m sao cho
a mq1 r và b mq2 r .
Khi a và b đồng dư với nhau theo môđun m, ta viết a ≡ b mod m .
Nếu a không đồng dư với b theo môđun m thì ta viết a b mod m .
Định lý
Các mệnh đề sau là tương đương.
i. a và b đồng dư với nhau theo môđun m;
ii. a – b chia hết cho m (kí hiệu là m a b );
iii. Tồn tại số nguyên t sao cho a = b+mt.
Chứng minh
i ii. Ta có a ≡ b mod m a mq1 r , b mq2 r với
q1 , q2 , r , 0 r m . Suy ra a b m q1 q2 . Do q1 q2 nên
m a b .
ii iii. Giả sử m a b . Khi ấy tồn tại số t sao cho a b mt ,
tức là a = b + mt.
iii i. Giả sử có số t sao cho a = b + mt. Gọi r là số dư trong phép
chia a cho m, nghĩa là a = m q1 + r với q1 , r , 0 r m . Khi ấy:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
4
b mt a mq1 r hay b m q1 t r , trong đó q1 t , 0 r m .
Chứng tỏ số dư trong phép chia b cho m cũng là r, tức là a b mod m .
1.2. Các tính chất của quan hệ đồng dƣ
a. Quan hệ đồng dư là một quan hệ tương đương trên tập :
i. Với mọi a : a ≡ a mod m ;
ii. Với mọi a, b : a≡ b mod m khi và chỉ khi b ≡ a mod m ;
iii. Với mọi a, b, c : a b mod m , b c mod m suy ra
a c mod m .
Chứng minh
i. Vì a a chia hết cho m nên a a mod m .
ii. Từ a b mod m ta có m a b . Do đó m b a b ≡
a mod m .
iii. Ta có a ≡ b mod m và b ≡ c mod m nên m a b và m b c .
Khi đó m a b b c hay m a c . Vậy a ≡ c mod m .
b. Ta có thể cộng hoặc trừ từng vế của nhiều đồng dư thức theo cùng
một môđun. Cụ thể là, nếu a1 b1 mod m và a2 b2 mod m thì ta có:
a1 a2 b1 b2 mod m .
Chứng minh
Từ a1 b1 mod m , a2 b2 mod m suy ra tồn tại t1 , t2 sao cho
a1 b1 mt1 , a2 b2 mt2 . Do đó a1 a2 b1 b2 m t1 t2 với t1 t2 .
Vậy a1 a2 b1 b2 mod m .
c. Ta có thể nhân từng vế của nhiều đồng dư thức theo cùng một môđun.
Cụ thể là, nếu a1 b1 mod m , a2 b2 mod m thì a1a2 bb
1 2
mod m .
Chứng minh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
5
Từ a1 b1 mod m , a2 b2 mod m suy ra tồn tại t1 , t2 sao cho
a1 b1 mt1 , a2 b2 mt2 .
Do đó a1a2 bb
1 2
m b2t1 bt1 2 mt1t2 , b2t1 bt
1 2
mt1t2 .
1 2
Vậy a1a2 bb
1 2
chia hết cho m hay a1a2 bb mod m .
d. Hệ quả
1. a ≡ b mod m khi và chỉ khi a ± c ≡ b ± c mod m .
Thật vậy, ta có a ≡ b mod m và c≡c mod m .
Vậy a± c ≡ b ± c mod m .
2. a + c ≡ b mod m khi và chỉ khi a b c mod m .
Thật vậy, ta có a ≡ b mod m , c ≡ c mod m . Vậy a b c mod m .
3. a b mod m khi và chỉ khi a ± km ≡ b mod m với mọi k .
Thật vậy, a ≡ b mod m , km ≡ 0 mod m . Vậy a ± km ≡ b mod m .
4. a b mod m khi và chỉ khi ac ≡ bc mod m .
Ta có a b mod m , c c mod m . Vậy ac bc mod m .
5. a b mod m a n b n mod m n , n > 0.
Ta có a b mod m ; a b mod m ; ...; a b mod m
Suy ra a n bn mod m .
6. Giả sử f(x) là một đa thức với hệ số nguyên và mod m . Khi ấy
f(α) ≡ f(β) mod m
Đặc biệt, nếu f(α) ≡ 0 mod m thì f(α + km) ≡ 0 mod m với mọi k .
Chứng minh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
6
Thật vậy, giả sử f(x) = a0 a1 x ... an xn . Từ giả thiết α ≡ β mod m
suy ra ai i ai i mod m , i = 1, 2,...., n. Do đó
+ ... + ≡ + ... + mod m ,
nghĩa là f(α) ≡ f(β) mod m .
Đặc biệt, vì km mod m k nên f(α)≡ f(α + km) mod m .
Nhưng f(α) ≡ 0 mod m nên ta có f(α + km) ≡0 mod m với mọi k .
e. Ta có thể chia hai vế của một đồng dư thức cho một ước chung của
chúng nguyên tố với môđun m:
ac ≡ bc mod m và UCLN c, m 1 a ≡ b mod m .
Chứng minh
Ta có ac ≡ bc mod m m (ac - bc) hay m|c(a - b). Nhưng m, c 1
nên ta có m a b a ≡ b mod m .
f. Có thể chia hai vế và môđun của một đồng dư thức cho một ước
chung dương của chúng:
a b m
a b mod m , 0 , UCLN a, b, m mod .
Chứng minh
Từ giả thiết δ|(a, b, m), ta đặt a = δ a1 , b = δ b1 , m = δ m1 với a1 , b1 ,
m1 , m1 0 . Mặt khác, a ≡ b mod m a = b + mt, t . Ta có:
a b m
a1 b1 m1 a1 b1 m1t a1 b1 mod m1 hay mod .
g. Nếu hai số đồng dư với nhau theo một môđun thì chúng cũng đồng
dư theo môđun là ước của môđun ấy:
a ≡ b mod m , δ|m, δ > 0 a ≡ b mod m .
Chứng minh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
7
Từ a ≡ b mod m m|(a - b), mà δ|m δ|(a - b) a ≡ b(mod δ).
h. Nếu hai số đồng dư với nhau theo nhiều môđun thì chúng đồng dư
với nhau theo môđun là bội chung nhỏ nhất của các môđun ấy:
a ≡ b(mod mi ), i 1,..., k a≡ b mod m với m BCNN( m1 , m2 ,…, mk ).
i. Nếu hai số đồng dư với nhau theo một môđun thì chúng có cùng
UCLN với môđun ấy:
a ≡ b mod m thì UCLN(a, m) = UCLN(b, m).
§2. Thặng dƣ
2.1. Tập các lớp thặng dƣ
Cho m là số nguyên dương. Theo tính chất của đồng dư thức, quan hệ
đồng dư là quan hệ tương đương trong tập trong tập số nguyên . Ta nói, các
số nguyên a và b cùng thuộc lớp tương đương A nếu chúng đồng dư với
nhau. Như vậy, có thể được phân thành các lớp theo quan hệ tương đương.
Nói cách khác, tồn tại tập thương trên quan hệ tương đương. Ta có
Định nghĩa
Tập thương của tập hợp số nguyên 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à m
.
Mỗi phần tử A của m
được gọi là một lớp thặng dư môđun m.
Từ định nghĩa, hai lớp thặng dư môđun m hoặc bằng nhau hoặc không
giao nhau và m
là hợp của tất cả các lớp thặng dư môđun m rời nhau.
Giả sử A m và a A , Khi ấy A x : x a mod m .
Phần tử a được gọi là đại diện của lớp thặng dư A và cũng được gọi là
một thặng dư môđun m.
Nhiều khi ta cũng viết A a x : x a mod m để thể hiện a là
đại diện cho lớp thặng dư A a .
2.2. Các tính chất của lớp thặng dƣ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
8
Tính chất 1
Tập m
có m phần tử.
Chứng minh
Xét các lớp thặng dư môđun m: 0, 1, ..., m 1 . Ta sẽ chứng minh
chúng gồm: m lớp phân biệt của m
và mỗi lớp x của m
phải trùng với một
trong m lớp đã nêu, do đó m
= 0, 1, ..., m 1 .
Thật vậy, với i j 0 i, j m 1 thì 0 i j m 1 nên i j 0 ,
nghĩa là i j mod m hay i j mod m . Như vậy 0, 1, ..., m 1 là m lớp
thặng dư phân biệt, chúng tạo nên một tập con X gồm m phần tử của m
.
Giả sử x m
và x mq i , i, q , 0 i m 1 thì x i mod m
nên x i ∈ 0, 1, ..., m 1 X . Vậy m
= X = 0, 1, ..., m 1 có m phần tử.
Tính chất 2
Mỗi lớp phần tử của m
là tập hợp của k phần tử phân biệt của km ,
k > 1.
Chứng minh
Giả sử A a m
. Ta sẽ chứng minh A là hợp của k phần tử (k > 1)
đôi một không giao nhau của km xác định như sau:
A0 a mod km , A1 = a m mod km , ..., Ak 1 = a k 1 m mod km .
Trước hết, với i ≠ j, (0 ≤ i, j ≤ k-1) ta có 0 < a im a jm km
nên a + im a + jm mod km . Suy ra Ai Aj . Do đó Ai Aj .
k 1
Ta có A = Ai .
i 0
Thật vậy, giả sử x A a mod m . Ta có x a mod m nên x a mt , t .
Chia t cho k, giả sử t = kq + i (q,i Z , 0 i k 1 ). Ta có:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
9
k 1
x a mi mqk a mi mod km nên x a im Ai Ai .
i 0
k 1
Ngược lại, giả sử x Ai . Khi ấy tồn tại số nguyên i (0 ≤ i ≤ k - 1) sao
i 0
cho x Ai , tức là x a mi mod km nên x ≡ (a + mi) mod m . Do đó
k 1
x ≡ a mod m , tức là x A. Vậy A Ai và ta có điều phải chứng minh.
i 0
2.3. Tập các lớp thặng dƣ nguyên tố với môđun
Nhận xét
Tất cả các thặng dư của cùng một lớp thặng dư có cùng ước chung lớn
nhất với môđun.
Thật vậy, giả sử A m
và a, b A. Khi ấy a ≡ b mod m nên theo tính
chất i. của đồng dư thức ta có UCLN(a, m) = UCLN (b, m). Từ đây ta có
Định nghĩa
Ước chung lớn nhất của một lớp với môđun m là ước chung lớn nhất
của một thặng dư tùy ý của lớp đó với môđun m.
Với A = a modm , ta đặt UCLN (A, m) = d nếu UCLN (a, m) = d.
Khi d =1 ta nói lớp thặng dư A là lớp nguyên tố với môđun m.
Tập hợp các lớp m
nguyên tố với môđun được kí hiệu bởi *
m
. Ta có:
*
m = A m
UCLN A, m 1 = A m
UCLN a, m 1, a A .
Số các phần tử của tập *
m được kí hiệu là (m) .
Vì m
= 0, 1, ..., m 1 nên *
m = a m
0 a m 1, UCLN a, m 1 .
Vậy (m) chính là số các số tự nhiên không vượt quá m 1 và nguyên
tố cùng nhau với m.
2.4. Vành các lớp thặng dƣ
Phép toán trong m
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
10
Trong m
, ta định nghĩa phép cộng và phép nhân như sau:
Giả sử a , b m
, ta đặt a b a b và a. b ab .
Dễ kiểm tra được các phép toán trên là hoàn toàn xác định.
Định lý
Tập hợp m
các lớp thặng dư môđun m cùng với phép cộng và phép
nhân xác định theo qui tắc trên là một vành giao hoán.
Phần tử khả nghịch
Lớp thặng dư A môđun m là phần tử khả nghịch của vành m
khi và chỉ
khi A là lớp nguyên tố với môđun m.
Chứng minh
Giả sử A a là khả nghịch, khi ấy tồn tại B m
sao cho
A.B E 1 mod m , tức là a.b 1 mod m . Nếu A là lớp không nguyên tố
với môđun m, tức là a, m 1 thì tồn tại các số q 1 , a1, m1 nguyên sao cho
a qa1 và m qm1 . Khi ấy ab qa1b và ab, m q 1 . Vô lý. Vậy (A, m) =
(a, m) = 1.
Ngược lại, giả sử (A, m) = 1 và A = a , tức là (a, m) = 1.
Không giảm tổng quát, có thể coi 0 a m 1.
Tập 0, a,2a,..., m 1 a chứa phần tử ab sao cho ab 1 mod m .
Thật vậy, nếu với mọi 0 b m ta có ab 1 mod m thì theo nguyên
lý Dirichlet phải có hai phần tử ab1 và ab2 ( 0 b1 b2 m ) cùng có số dư khi
chia cho m, nghĩa là ab1 ab2 a b1 b2 km . Nhưng 0 b1 b2 m nên
a, m 1, vô lý. Nghĩa là tồn tại 0 b m sao cho ab 1 mod m .
Đặt B = b , ta có ab a. b 1 hay AB = E, nghĩa là A khả nghịch.
Tính chất của phần tử khả nghịch
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
11
Giả sử A, B là những lớp thặng dư của vành m
và A khả nghịch. Khi
X chạy qua tất cả các lớp thặng dư của vành m
thì AX B cũng chạy qua tất
cả các phần tử của m
và AX cũng chạy qua tất cả các phần tử khả nghịch của
m
, tức là:
m
= AX B X m và *
m
AX X *
m .
Kí hiệu (m) là số các phần tử khả nghịch của vành m
các lớp thặng
dư môđun m, hay (m) = card( *
m
).
Ta biết rằng m
= 0, 1, 2, ..., m 1 , từ đó ta có
*
m
= n m
0 n m 1,(n, m) 1 .
Như vậy ta được (m) card( *m ) 1, nghĩa là (m) là hàm số
0 n m 1
( n , m ) 1
biểu thị các số tự nhiên không lớn hơn m 1 và nguyên tố cùng nhau với m.
Ta cũng có thể viết m
= 1, 2,...,m , khi ấy
*
m = n m
1 n m,(n, m) 1 .
Như vậy ta được (m) card( Z m* ) 1 , nghĩa là (m) là hàm số
1 n m
( n , m ) 1
biểu thị các số tự nhiên khác không, không lớn hơn m và nguyên tố với m.
Hệ quả
(1) 1 và nếu p là số nguyên tố thì ta có thì ta có (m) p 1.
§3. Hệ thặng dƣ đầy đủ - Hệ thặng dƣ thu gọn
3.1. Hệ thặng dƣ đầy đủ
Cho m là một số nguyên dương. Tập H gồm nhũng số nguyên lấy ra ở
mỗi lớp thặng dư của m
một và chỉ một số được gọi là một hệ thặng dư đầy
đủ môđun m.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
12
Như vậy: Tập hợp H gồm những số nguyên là một hệ thặng dư đầy đủ
môđun m khi và chỉ khi:
- Các phần tử của H đôi một không đồng dư với nhau theo môđun m.
- Mỗi số nguyên đều đồng dư theo môđun m với một số nào đó thuộc H.
Mỗi một số nguyên của H được gọi là một thặng dư.
Ví dụ với m = 8 ta có: Z8 0, 1, 2, 3, 4, 5, 6, 7 là một hệ thặng dư đầy
đủ môđun 8, nó được gọi là hệ thặng dư đầy đủ không âm nhỏ nhất. Còn hệ
3, 2, 1, 0, 1, 2, 3 là một hệ thặng dư môđun 8, hệ này được gọi là hệ
thặng dư đầy đủ giá trị tuyệt đối nhỏ nhất.
Tổng quát
+) H ={0, 1, ....., m - 1} là một hệ thặng dư đầy đủ môđun m và nó là hệ
thặng dư đầy đủ không âm nhỏ nhất.
+) Với m là một số lẻ, ta có
m 1 m 1 m 1
H= ; 1; ...;
2 2 2
là một hệ thặng dư đầy đủ môđun m được gọi là hệ thặng dư đầy đủ giá trị
tuyệt đối nhỏ nhất.
+) Với m là một số chẵn, ta có
m m m m m m
H = ; 1; ...; hay H = 1; 2; ...;
2 2 2 2 2 2
là hệ thặng dư đầy đủ giá trị tuyệt đối nhỏ nhất.
Tính chất 1
Mỗi hệ thặng dư đầy đủ môđum m đều gồm m phần tử.
Chứng minh
Hiển nhiên vì tập m
có m phần tử.
Tính chất 2
Mỗi hệ gồm m số nguyên đôi một không đồng dư với nhau theo môđun
m đều là một hệ thặng dư đầy đủ môđun m.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
13
Chứng minh
Giả sử H a1 , a2 ,..., an là một hệ gồm m số nguyên đôi một không
đồng dư với nhau theo môđun m. Khi ấy tập các lớp thặng dư theo môđun m
a , a ,..., a gồm m phần tử đôi một phân biệt và là tập con của
1 2 m m
. Nhưng
vì m
có m phần tử và tập con a1 , a2 ,..., an cũng có m phần tử đôi một phân
biệt nên ta có a1 , a2 ,..., an m
.
Từ m
a1 , a2 ,..., an ta được H a1 , a2 ,..., an là một hệ thặng dư đầy đủ
môđun m.
Tính chất 3
Giả sử a là một số nguyên tố với m và b là một số nguyên tùy ý. Khi
ấy xét x chạy qua một hệ thặng dư đầy đủ môđun m thì ax b cũng chạy qua
một hệ thặng dư đầy đủ môđun m.
Chứng minh
Giả sử x chạy qua một hệ thặng dư môđun m là x1 , x2 ,..., xm . Ta chứng
minh ax1 b, ax2 b,..., axm b cũng là một hệ thặng dư đầy đủ môđun m.
Theo Tính chất 2 ở trên ta chỉ cần chứng minh rằng với 1 i j m
thì axi b ax j b mod m . Thật vậy, nếu axi b ax j b mod m thì
axi ax j mod m . Vì a nguyên tố với m nên xi x j mod m . Vô lý vì xi và
x j là 2 thặng dư khác nhau của một hệ thặng dư đầy đủ môđun m.
Vậy ax1 b, ax2 b,..., axm b cũng là một hệ thặng dư đầy đủ
môđun m.
3.2. Hệ thặng dƣ thu gọn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
14
Cho m là một số nguyên dương. Tập hợp K gồm những số nguyên được
lấy ra ở mỗi lớp nguyên tố với môđun m một và chỉ một số được gọi là một hệ
thặng dư thu gọn môđun m.
Vậy một tập hợp K gồm những số nguyên được gọi là một hệ thặng dư
thu gọn môđun m nếu và chỉ nếu:
- Các phần tử thuộc K đôi một không đồng dư với nhau theo môđun m.
- Các phần tử thuộc K nguyên tố với môđun m.
- Mỗi số nguyên tùy ý nguyên tố với môđun m đều đồng dư với một số
nào đó thuộc K.
Nhận xét
Mỗi hệ thặng dư đầy đủ đều chứa duy nhất một hệ thặng dư thu gọn.
Hệ thặng dư thu gọn không âm nhỏ nhất r1 , r2 , ..., r m là hệ thặng dư
thu gọn gồm các phần tử 0 ri m, i 1,2,..., m nguyên tố cùng nhau với m.
Ta có khái niệm hệ thặng dư thu gọn môđun m có trị tuyệt đối nhỏ nhất.
Ví dụ
Khi m = 8 ta có 1, 3, 5,7 là một hệ thặng dư thu gọn không âm nhỏ nhất.
Hệ 3, , 1, 0, 1, 3 là một hệ thặng dư thu gọn giá trị tuyệt đối nhỏ nhất.
Nếu m p là một số nguyên tố thì 1, 2, ..., p 1 là hệ thặng dư thu
p 1 p 1
gọn không âm nhỏ nhất và nếu p 2 thì , ..., 2, 1, 0, 1, 2, ...,
2 2
là hệ thặng dư thu gọn giá trị tuyệt đối nhỏ nhất.
Tính chất của hệ thặng dƣ thu gọn
Tính chất 1
Mỗi hệ thặng dư thu gọn môđun m gồm φ(m) phần tử.
Chứng minh
Hiển nhiên vì tập hợp *
m có φ(m) phần tử.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
15
Tính chất 2
Mỗi hệ gồm m số nguyên tố với m và đôi một không đồng dư với
nhau theo môđun m đều lập nên một hệ thặng dư thu gọn môđun m.
Chứng minh
Giả sử K a1 , a2 ,..., a m là một hệ gồm m số nguyên nguyên tố
với m và đôi một không đồng dư với nhau theo môđun m.
Vì a1 , a2 ,..., a m nguyên tố với m nên ta có tập hợp a1 , a2 ,..., a m các
lớp theo môđun m là một tập con của *
m
gồm m phần tử, nghĩa là có số
phần tử bằng số phần tử của *
m a , a ,..., a = Z .
, do đó ta có 1 2 m
*
m
Từ *
m
= a , a ,..., a ta được K a , a ,..., a là một hệ thặng
1 2 m 1 2 m
dư thu gọn môđum m.
Tính chất 3
Giả sử a là một số nguyên tố với m. Khi ấy nếu x chạy qua một hệ
thặng dư thu gọn môđun m thì ax cũng chạy qua một hệ thặng dư thu gọn
môđun m.
Chứng minh
Giả sử x chạy qua hệ thặng dư thu gọn x1 , x2 ,..., x m môđun m. Khi
ấy ax1 , ax2 ,..., ax m cũng là một hệ thặng dư thu gọn môđun m.
Thật vậy, ax1 , ax2 ,..., ax m là một hệ gồm (m) số nguyên nguyên tố
với m vì UCLN(a, m) = 1 và UCLN xi , m = 1, (i = 1, 2, ..., φ(m)). Theo tính
chất 2 ở trên, ta chỉ cần chứng minh rằng với i j, 1 i, j m thì
axi ax j (mod m). Giả sử ngược lại, axi ax j (mod m). Do UCLN a, m 1 ta
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
16
có xi x j (mod m), 1 i, j m . Điều này mâu thuẫn với giả thiết với xi , x j
là hai thặng dư khác nhau của một hệ thặng dư thu gọn.
Vậy ax1 , ax2 ,..., ax m cũng là một hệ thặng dư thu gọn môđun m.
3.3. Các định lí quan trọng
Định lý Euler
Giả sử m là một số tự nhiên lớn hơn 1 và a là một số nguyên tố cùng
nhau với m. Khi ấy ta có
a m 1 mod m .
Chứng minh
Ta cho x chạy qua hệ thặng dư thu gọn môđun m không âm nhỏ nhất
r , r , ..., r . Khi ấy theo tính chất 3, tập hợp ar , a r , ..., ar cũng là
1 2 m 1 2 m
một hệ thặng dư thu gọn môđun m.
Giả sử s1 , s2 , ..., s m là các thặng dư không âm nhỏ nhất tương ứng
cùng lớp với ar1 , a r2 , ..., ar m , tức là 0 si m,1 i m và
ar1 s1 (mod m); ar2 s2 (mod m); …; ar m s m mod m . (3.1)
Khi ấy s1 , s2 , ..., s m cũng là hệ thặng dư thu gọn môđun m không âm
nhỏ nhất.
Vì r , r , ..., r và s , s , ..., s cùng là hệ thặng dư thu gọn
1 2 m 1 2 m
môđun m không âm nhỏ nhất nên ta có rr
1 2
...r m s1s2 ...s m .
Nhân vế với vế m đồng dư thức (3.1) ta được
a m rr
1 2
...r m s1s2 ...s m mod m .
Vì ri , m 1 , (i = 1, 2, ..., φ(m)), nên a 1 mod m .
m
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
TRƢỜNG ĐẠI HỌC KHOA HỌC
––––––––––––––––––
NGUYỄN TRỌNG NAM
LÝ THUYẾT ĐỒNG DƢ
VÀ ỨNG DỤNG TRONG MÃ SỬA SAI
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2009
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
––––––––––––––––––
NGUYỄN TRỌNG NAM
LÝ THUYẾT ĐỒNG DƢ
VÀ ỨNG DỤNG TRONG MÃ SỬA SAI
Chuyên ngành: TOÁN SƠ CẤP
Mã số: 60.46.40
LUẬN VĂN THẠC SĨ TOÁN HỌC
Ngƣời hƣớng dẫn khoa học: PGS.TS TẠ DUY PHƢỢNG
THÁI NGUYÊN - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
MỤC LỤC
LỜI NÓI ĐẦU .............................................................................................. 1
Chƣơng 1: LÝ THUYẾT ĐỒNG DƢ .......................................................... 3
§ 1. Quan hệ đồng dƣ ................................................................................... 3
1.1. Định nghĩa đồng dư ................................................................................. 3
1.2. Các tính chất của quan hệ đồng dư .......................................................... 4
§ 2. Thặng dƣ ................................................................................................ 7
2.1. Tập các lớp thặng dư ............................................................................... 7
2.2. Các tính chất của lớp thặng dư................................................................. 7
2.3. Tập các lớp thặng dư nguyên tố với môđun ............................................. 9
2.4. Vành các lớp thặng dư ............................................................................. 9
§ 3. Hệ thặng dƣ đầy đủ - Hệ thặng dƣ thu gọn........................................ 11
3.1. Hệ thặng dư đầy đủ................................................................................ 11
3.2. Hệ thặng dư thu gọn .............................................................................. 13
3.3. Các định lí quan trọng ........................................................................... 16
§ 4. Phƣơng trình đồng dƣ ......................................................................... 17
4.1. Các khái niệm chung ............................................................................. 17
4.2. Phương trình và hệ phương trình đồng dư bậc nhất một ẩn .................... 23
4.2.1. Phương trình đồng dư bậc nhất một ẩn ............................................... 23
4.2.2. Hệ phương trình đồng dư bậc nhất một ẩn .......................................... 26
4.3. Phương trình đồng dư bậc cao theo môđun nguyên tố .......................... 31
4.3.1. Nhận xét ............................................................................................. 31
4.3.2. Phương trình bậc cao theo môđun nguyên tố ...................................... 32
Chƣơng 2: ỨNG DỤNG CỦA LÝ THUYẾT ĐỒNG DƢ TRONG
MÃ SỬA SAI ...................................................................................... 36
§ 1. Khái niệm mã ....................................................................................... 36
§ 2. Những ví dụ về mã ............................................................................... 39
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
2.1. Mã lặp ................................................................................................... 39
2.2. Mã chẵn lẻ ............................................................................................. 41
2.3. Mã vạch ................................................................................................ 44
§ 3. Khoảng cách Hamming ...................................................................... 48
§ 4. Mã tuyến tính ....................................................................................... 53
4.1. Mã nhị phân tuyến tính .......................................................................... 53
4.2. Biểu diễn ma trận của các mã nhị phân .................................................. 55
4.3. Thuật toán hội chứng giải mã cho các mã nhị phân ............................... 65
4.4. Mã nhị phân Hamming .......................................................................... 67
4.5. Các tính chất của mã nhị phân Hamming [n,k] ...................................... 70
4.6. Các p-mã Hamming ............................................................................... 71
4.7. Các tính chất của p-mã Hamming [n,k] ................................................. 74
§ 5. Mã thập phân...................................................................................... 77
5.1. Mã số sách tiêu chuẩn quốc tế (ISBN) ................................................... 77
5.2. Mã sửa lỗi đơn ....................................................................................... 82
5.3. Mã sửa lỗi kép ....................................................................................... 84
KẾT LUẬN ................................................................................................. 88
TÀI LIỆU THAM KHẢO.......................................................................... 89
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
1
LỜI NÓI ĐẦU
Có thể nói, số học, lý thuyết số là một trong những kiến thức toán học
lâu đời nhất. Từ trước tới nay, người ta thường coi lý thuyết số như một lĩnh
vực đẹp, nhưng thuần túy lý thuyết, của toán học. Với sự phát triển của khoa
học máy tính và công nghệ thông tin, lý thuyết số đã đóng góp những ứng
dụng thực tế bất ngờ và quan trọng, đặc biệt trong lĩnh vực mã hóa thông tin.
Nhiều khía cạnh khác nhau của mã hóa thông tin được các nhà toán học
và tin học quan tâm. Thường thường thông tin được mã hóa qua dãy các chữ
số trong hệ đếm cơ số 2, cơ số 10, hoặc cơ số p nào đó. Trong quá trình
truyền tin hoặc nhận tin, vì nhiều lý do, thông tin có thể bị sai lệch. Thí dụ,
một tin nhắn được mã hóa trong cơ số 2 khi truyền đi bị sai một lỗi (lỗi đơn)
thì điều này có nghĩa là chữ số 1 tại vị trí nào đó đã bị đổi thành chữ số 0 hoặc
ngược lại. Một trong những vấn đề cần giải quyết là phát hiện ra các lỗi sai và
sửa chúng.
Vì yêu cầu thực tiễn đó, lý thuyết mã sửa sai đã ra đời, phát triển và có
những ứng dụng thực tiễn quan trọng. Để xây dựng lý thuyết mã sửa sai, các
nhà toán học và khoa học máy tính đã sử dụng nhiều thành tựu của toán học
hiện đại (số học, toán rời rạc, đại số tuyến tính,...,) đặc biệt là số học trên tập
số nguyên, trong đó có lý thuyết đồng dư.
Luận văn này có mục đích tìm hiểu và trình bày những kiến thức cơ
bản nhất của lý thuyết mã sửa sai trên cơ sở lý thuyết đồng dư và lý thuyết
trường hữu hạn.
Luận văn gồm hai chương.
Chương 1 trình bày các kiến thức cơ bản nhất của lý thuyết đồng dư
và lý thuyết trường hữu hạn, chủ yếu dựa theo tài liệu [2], có tham khảo thêm
các tài liệu [4] và [6].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
2
Chương 2 trình bày một số vấn đề cơ bản của mã sửa sai: khoảng cách
Hamming; phát hiện và sửa lỗi; các thuật toán giải mã; mã hoàn hảo; mã
tuyến tính và ma trận kiểm tra, xây dựng mã tuyến tính,...
Nội dung của Chương 2 trình bày chủ yếu dựa theo tài liệu [6], có tham
khảo thêm các tài liệu [1] và [7]. Ngoài ra, chúng tôi cũng quan tâm đến khía
cạnh thực tế của vấn đề: mã vạch, mã hàng hóa, mã sách tiêu chuẩn quốc
tế,.... Chúng tôi cũng cố gắng tìm hiểu, tuy chưa được đầy đủ, các mã hàng
hóa, mã văn hóa phẩm của Việt Nam và kiểm nghiệm các tiêu chuẩn giải mã
cho các ví dụ cụ thể của các mã này.
Luận văn được hoàn thành dưới sự hướng dẫn khoa học của PGS TS Tạ
Duy Phượng. Xin được tỏ lòng cám ơn chân thành nhất tới Thầy.
Tác giả xin cám ơn chân thành tới Trường Đại học Khoa học Thái
Nguyên, nơi tác giả đã nhận được một học vấn sau đại học căn bản.
Và cuối cùng, xin cám ơn gia đình, bạn bè, đồng nghiệp đã cảm thông,
ủng hộ và giúp đỡ trong suốt thời gian tác giả học Cao học và viết luận văn.
Hà Nội, ngày 19 tháng 9 năm 2009
Tác giả
Nguyễn Trọng Nam
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
3
Chƣơng 1
LÝ THUYẾT ĐỒNG DƢ
§1. Quan hệ đồng dƣ
1.1. Định nghĩa đồng dƣ
Kí hiệu là tập hợp các số nguyên.
Định nghĩa
Cho m là một số nguyên dương, a và b là hai số nguyên. Ta nói a và b
đồng dư với nhau theo môđun m nếu trong phép chia a và b cho m ta được
cùng một số dư, nghĩa là có các số nguyên q1 , q2 , r với 0 r m sao cho
a mq1 r và b mq2 r .
Khi a và b đồng dư với nhau theo môđun m, ta viết a ≡ b mod m .
Nếu a không đồng dư với b theo môđun m thì ta viết a b mod m .
Định lý
Các mệnh đề sau là tương đương.
i. a và b đồng dư với nhau theo môđun m;
ii. a – b chia hết cho m (kí hiệu là m a b );
iii. Tồn tại số nguyên t sao cho a = b+mt.
Chứng minh
i ii. Ta có a ≡ b mod m a mq1 r , b mq2 r với
q1 , q2 , r , 0 r m . Suy ra a b m q1 q2 . Do q1 q2 nên
m a b .
ii iii. Giả sử m a b . Khi ấy tồn tại số t sao cho a b mt ,
tức là a = b + mt.
iii i. Giả sử có số t sao cho a = b + mt. Gọi r là số dư trong phép
chia a cho m, nghĩa là a = m q1 + r với q1 , r , 0 r m . Khi ấy:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
4
b mt a mq1 r hay b m q1 t r , trong đó q1 t , 0 r m .
Chứng tỏ số dư trong phép chia b cho m cũng là r, tức là a b mod m .
1.2. Các tính chất của quan hệ đồng dƣ
a. Quan hệ đồng dư là một quan hệ tương đương trên tập :
i. Với mọi a : a ≡ a mod m ;
ii. Với mọi a, b : a≡ b mod m khi và chỉ khi b ≡ a mod m ;
iii. Với mọi a, b, c : a b mod m , b c mod m suy ra
a c mod m .
Chứng minh
i. Vì a a chia hết cho m nên a a mod m .
ii. Từ a b mod m ta có m a b . Do đó m b a b ≡
a mod m .
iii. Ta có a ≡ b mod m và b ≡ c mod m nên m a b và m b c .
Khi đó m a b b c hay m a c . Vậy a ≡ c mod m .
b. Ta có thể cộng hoặc trừ từng vế của nhiều đồng dư thức theo cùng
một môđun. Cụ thể là, nếu a1 b1 mod m và a2 b2 mod m thì ta có:
a1 a2 b1 b2 mod m .
Chứng minh
Từ a1 b1 mod m , a2 b2 mod m suy ra tồn tại t1 , t2 sao cho
a1 b1 mt1 , a2 b2 mt2 . Do đó a1 a2 b1 b2 m t1 t2 với t1 t2 .
Vậy a1 a2 b1 b2 mod m .
c. Ta có thể nhân từng vế của nhiều đồng dư thức theo cùng một môđun.
Cụ thể là, nếu a1 b1 mod m , a2 b2 mod m thì a1a2 bb
1 2
mod m .
Chứng minh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
5
Từ a1 b1 mod m , a2 b2 mod m suy ra tồn tại t1 , t2 sao cho
a1 b1 mt1 , a2 b2 mt2 .
Do đó a1a2 bb
1 2
m b2t1 bt1 2 mt1t2 , b2t1 bt
1 2
mt1t2 .
1 2
Vậy a1a2 bb
1 2
chia hết cho m hay a1a2 bb mod m .
d. Hệ quả
1. a ≡ b mod m khi và chỉ khi a ± c ≡ b ± c mod m .
Thật vậy, ta có a ≡ b mod m và c≡c mod m .
Vậy a± c ≡ b ± c mod m .
2. a + c ≡ b mod m khi và chỉ khi a b c mod m .
Thật vậy, ta có a ≡ b mod m , c ≡ c mod m . Vậy a b c mod m .
3. a b mod m khi và chỉ khi a ± km ≡ b mod m với mọi k .
Thật vậy, a ≡ b mod m , km ≡ 0 mod m . Vậy a ± km ≡ b mod m .
4. a b mod m khi và chỉ khi ac ≡ bc mod m .
Ta có a b mod m , c c mod m . Vậy ac bc mod m .
5. a b mod m a n b n mod m n , n > 0.
Ta có a b mod m ; a b mod m ; ...; a b mod m
Suy ra a n bn mod m .
6. Giả sử f(x) là một đa thức với hệ số nguyên và mod m . Khi ấy
f(α) ≡ f(β) mod m
Đặc biệt, nếu f(α) ≡ 0 mod m thì f(α + km) ≡ 0 mod m với mọi k .
Chứng minh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
6
Thật vậy, giả sử f(x) = a0 a1 x ... an xn . Từ giả thiết α ≡ β mod m
suy ra ai i ai i mod m , i = 1, 2,...., n. Do đó
+ ... + ≡ + ... + mod m ,
nghĩa là f(α) ≡ f(β) mod m .
Đặc biệt, vì km mod m k nên f(α)≡ f(α + km) mod m .
Nhưng f(α) ≡ 0 mod m nên ta có f(α + km) ≡0 mod m với mọi k .
e. Ta có thể chia hai vế của một đồng dư thức cho một ước chung của
chúng nguyên tố với môđun m:
ac ≡ bc mod m và UCLN c, m 1 a ≡ b mod m .
Chứng minh
Ta có ac ≡ bc mod m m (ac - bc) hay m|c(a - b). Nhưng m, c 1
nên ta có m a b a ≡ b mod m .
f. Có thể chia hai vế và môđun của một đồng dư thức cho một ước
chung dương của chúng:
a b m
a b mod m , 0 , UCLN a, b, m mod .
Chứng minh
Từ giả thiết δ|(a, b, m), ta đặt a = δ a1 , b = δ b1 , m = δ m1 với a1 , b1 ,
m1 , m1 0 . Mặt khác, a ≡ b mod m a = b + mt, t . Ta có:
a b m
a1 b1 m1 a1 b1 m1t a1 b1 mod m1 hay mod .
g. Nếu hai số đồng dư với nhau theo một môđun thì chúng cũng đồng
dư theo môđun là ước của môđun ấy:
a ≡ b mod m , δ|m, δ > 0 a ≡ b mod m .
Chứng minh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
7
Từ a ≡ b mod m m|(a - b), mà δ|m δ|(a - b) a ≡ b(mod δ).
h. Nếu hai số đồng dư với nhau theo nhiều môđun thì chúng đồng dư
với nhau theo môđun là bội chung nhỏ nhất của các môđun ấy:
a ≡ b(mod mi ), i 1,..., k a≡ b mod m với m BCNN( m1 , m2 ,…, mk ).
i. Nếu hai số đồng dư với nhau theo một môđun thì chúng có cùng
UCLN với môđun ấy:
a ≡ b mod m thì UCLN(a, m) = UCLN(b, m).
§2. Thặng dƣ
2.1. Tập các lớp thặng dƣ
Cho m là số nguyên dương. Theo tính chất của đồng dư thức, quan hệ
đồng dư là quan hệ tương đương trong tập trong tập số nguyên . Ta nói, các
số nguyên a và b cùng thuộc lớp tương đương A nếu chúng đồng dư với
nhau. Như vậy, có thể được phân thành các lớp theo quan hệ tương đương.
Nói cách khác, tồn tại tập thương trên quan hệ tương đương. Ta có
Định nghĩa
Tập thương của tập hợp số nguyên 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à m
.
Mỗi phần tử A của m
được gọi là một lớp thặng dư môđun m.
Từ định nghĩa, hai lớp thặng dư môđun m hoặc bằng nhau hoặc không
giao nhau và m
là hợp của tất cả các lớp thặng dư môđun m rời nhau.
Giả sử A m và a A , Khi ấy A x : x a mod m .
Phần tử a được gọi là đại diện của lớp thặng dư A và cũng được gọi là
một thặng dư môđun m.
Nhiều khi ta cũng viết A a x : x a mod m để thể hiện a là
đại diện cho lớp thặng dư A a .
2.2. Các tính chất của lớp thặng dƣ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
8
Tính chất 1
Tập m
có m phần tử.
Chứng minh
Xét các lớp thặng dư môđun m: 0, 1, ..., m 1 . Ta sẽ chứng minh
chúng gồm: m lớp phân biệt của m
và mỗi lớp x của m
phải trùng với một
trong m lớp đã nêu, do đó m
= 0, 1, ..., m 1 .
Thật vậy, với i j 0 i, j m 1 thì 0 i j m 1 nên i j 0 ,
nghĩa là i j mod m hay i j mod m . Như vậy 0, 1, ..., m 1 là m lớp
thặng dư phân biệt, chúng tạo nên một tập con X gồm m phần tử của m
.
Giả sử x m
và x mq i , i, q , 0 i m 1 thì x i mod m
nên x i ∈ 0, 1, ..., m 1 X . Vậy m
= X = 0, 1, ..., m 1 có m phần tử.
Tính chất 2
Mỗi lớp phần tử của m
là tập hợp của k phần tử phân biệt của km ,
k > 1.
Chứng minh
Giả sử A a m
. Ta sẽ chứng minh A là hợp của k phần tử (k > 1)
đôi một không giao nhau của km xác định như sau:
A0 a mod km , A1 = a m mod km , ..., Ak 1 = a k 1 m mod km .
Trước hết, với i ≠ j, (0 ≤ i, j ≤ k-1) ta có 0 < a im a jm km
nên a + im a + jm mod km . Suy ra Ai Aj . Do đó Ai Aj .
k 1
Ta có A = Ai .
i 0
Thật vậy, giả sử x A a mod m . Ta có x a mod m nên x a mt , t .
Chia t cho k, giả sử t = kq + i (q,i Z , 0 i k 1 ). Ta có:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
9
k 1
x a mi mqk a mi mod km nên x a im Ai Ai .
i 0
k 1
Ngược lại, giả sử x Ai . Khi ấy tồn tại số nguyên i (0 ≤ i ≤ k - 1) sao
i 0
cho x Ai , tức là x a mi mod km nên x ≡ (a + mi) mod m . Do đó
k 1
x ≡ a mod m , tức là x A. Vậy A Ai và ta có điều phải chứng minh.
i 0
2.3. Tập các lớp thặng dƣ nguyên tố với môđun
Nhận xét
Tất cả các thặng dư của cùng một lớp thặng dư có cùng ước chung lớn
nhất với môđun.
Thật vậy, giả sử A m
và a, b A. Khi ấy a ≡ b mod m nên theo tính
chất i. của đồng dư thức ta có UCLN(a, m) = UCLN (b, m). Từ đây ta có
Định nghĩa
Ước chung lớn nhất của một lớp với môđun m là ước chung lớn nhất
của một thặng dư tùy ý của lớp đó với môđun m.
Với A = a modm , ta đặt UCLN (A, m) = d nếu UCLN (a, m) = d.
Khi d =1 ta nói lớp thặng dư A là lớp nguyên tố với môđun m.
Tập hợp các lớp m
nguyên tố với môđun được kí hiệu bởi *
m
. Ta có:
*
m = A m
UCLN A, m 1 = A m
UCLN a, m 1, a A .
Số các phần tử của tập *
m được kí hiệu là (m) .
Vì m
= 0, 1, ..., m 1 nên *
m = a m
0 a m 1, UCLN a, m 1 .
Vậy (m) chính là số các số tự nhiên không vượt quá m 1 và nguyên
tố cùng nhau với m.
2.4. Vành các lớp thặng dƣ
Phép toán trong m
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
10
Trong m
, ta định nghĩa phép cộng và phép nhân như sau:
Giả sử a , b m
, ta đặt a b a b và a. b ab .
Dễ kiểm tra được các phép toán trên là hoàn toàn xác định.
Định lý
Tập hợp m
các lớp thặng dư môđun m cùng với phép cộng và phép
nhân xác định theo qui tắc trên là một vành giao hoán.
Phần tử khả nghịch
Lớp thặng dư A môđun m là phần tử khả nghịch của vành m
khi và chỉ
khi A là lớp nguyên tố với môđun m.
Chứng minh
Giả sử A a là khả nghịch, khi ấy tồn tại B m
sao cho
A.B E 1 mod m , tức là a.b 1 mod m . Nếu A là lớp không nguyên tố
với môđun m, tức là a, m 1 thì tồn tại các số q 1 , a1, m1 nguyên sao cho
a qa1 và m qm1 . Khi ấy ab qa1b và ab, m q 1 . Vô lý. Vậy (A, m) =
(a, m) = 1.
Ngược lại, giả sử (A, m) = 1 và A = a , tức là (a, m) = 1.
Không giảm tổng quát, có thể coi 0 a m 1.
Tập 0, a,2a,..., m 1 a chứa phần tử ab sao cho ab 1 mod m .
Thật vậy, nếu với mọi 0 b m ta có ab 1 mod m thì theo nguyên
lý Dirichlet phải có hai phần tử ab1 và ab2 ( 0 b1 b2 m ) cùng có số dư khi
chia cho m, nghĩa là ab1 ab2 a b1 b2 km . Nhưng 0 b1 b2 m nên
a, m 1, vô lý. Nghĩa là tồn tại 0 b m sao cho ab 1 mod m .
Đặt B = b , ta có ab a. b 1 hay AB = E, nghĩa là A khả nghịch.
Tính chất của phần tử khả nghịch
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
11
Giả sử A, B là những lớp thặng dư của vành m
và A khả nghịch. Khi
X chạy qua tất cả các lớp thặng dư của vành m
thì AX B cũng chạy qua tất
cả các phần tử của m
và AX cũng chạy qua tất cả các phần tử khả nghịch của
m
, tức là:
m
= AX B X m và *
m
AX X *
m .
Kí hiệu (m) là số các phần tử khả nghịch của vành m
các lớp thặng
dư môđun m, hay (m) = card( *
m
).
Ta biết rằng m
= 0, 1, 2, ..., m 1 , từ đó ta có
*
m
= n m
0 n m 1,(n, m) 1 .
Như vậy ta được (m) card( *m ) 1, nghĩa là (m) là hàm số
0 n m 1
( n , m ) 1
biểu thị các số tự nhiên không lớn hơn m 1 và nguyên tố cùng nhau với m.
Ta cũng có thể viết m
= 1, 2,...,m , khi ấy
*
m = n m
1 n m,(n, m) 1 .
Như vậy ta được (m) card( Z m* ) 1 , nghĩa là (m) là hàm số
1 n m
( n , m ) 1
biểu thị các số tự nhiên khác không, không lớn hơn m và nguyên tố với m.
Hệ quả
(1) 1 và nếu p là số nguyên tố thì ta có thì ta có (m) p 1.
§3. Hệ thặng dƣ đầy đủ - Hệ thặng dƣ thu gọn
3.1. Hệ thặng dƣ đầy đủ
Cho m là một số nguyên dương. Tập H gồm nhũng số nguyên lấy ra ở
mỗi lớp thặng dư của m
một và chỉ một số được gọi là một hệ thặng dư đầy
đủ môđun m.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
12
Như vậy: Tập hợp H gồm những số nguyên là một hệ thặng dư đầy đủ
môđun m khi và chỉ khi:
- Các phần tử của H đôi một không đồng dư với nhau theo môđun m.
- Mỗi số nguyên đều đồng dư theo môđun m với một số nào đó thuộc H.
Mỗi một số nguyên của H được gọi là một thặng dư.
Ví dụ với m = 8 ta có: Z8 0, 1, 2, 3, 4, 5, 6, 7 là một hệ thặng dư đầy
đủ môđun 8, nó được gọi là hệ thặng dư đầy đủ không âm nhỏ nhất. Còn hệ
3, 2, 1, 0, 1, 2, 3 là một hệ thặng dư môđun 8, hệ này được gọi là hệ
thặng dư đầy đủ giá trị tuyệt đối nhỏ nhất.
Tổng quát
+) H ={0, 1, ....., m - 1} là một hệ thặng dư đầy đủ môđun m và nó là hệ
thặng dư đầy đủ không âm nhỏ nhất.
+) Với m là một số lẻ, ta có
m 1 m 1 m 1
H= ; 1; ...;
2 2 2
là một hệ thặng dư đầy đủ môđun m được gọi là hệ thặng dư đầy đủ giá trị
tuyệt đối nhỏ nhất.
+) Với m là một số chẵn, ta có
m m m m m m
H = ; 1; ...; hay H = 1; 2; ...;
2 2 2 2 2 2
là hệ thặng dư đầy đủ giá trị tuyệt đối nhỏ nhất.
Tính chất 1
Mỗi hệ thặng dư đầy đủ môđum m đều gồm m phần tử.
Chứng minh
Hiển nhiên vì tập m
có m phần tử.
Tính chất 2
Mỗi hệ gồm m số nguyên đôi một không đồng dư với nhau theo môđun
m đều là một hệ thặng dư đầy đủ môđun m.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
13
Chứng minh
Giả sử H a1 , a2 ,..., an là một hệ gồm m số nguyên đôi một không
đồng dư với nhau theo môđun m. Khi ấy tập các lớp thặng dư theo môđun m
a , a ,..., a gồm m phần tử đôi một phân biệt và là tập con của
1 2 m m
. Nhưng
vì m
có m phần tử và tập con a1 , a2 ,..., an cũng có m phần tử đôi một phân
biệt nên ta có a1 , a2 ,..., an m
.
Từ m
a1 , a2 ,..., an ta được H a1 , a2 ,..., an là một hệ thặng dư đầy đủ
môđun m.
Tính chất 3
Giả sử a là một số nguyên tố với m và b là một số nguyên tùy ý. Khi
ấy xét x chạy qua một hệ thặng dư đầy đủ môđun m thì ax b cũng chạy qua
một hệ thặng dư đầy đủ môđun m.
Chứng minh
Giả sử x chạy qua một hệ thặng dư môđun m là x1 , x2 ,..., xm . Ta chứng
minh ax1 b, ax2 b,..., axm b cũng là một hệ thặng dư đầy đủ môđun m.
Theo Tính chất 2 ở trên ta chỉ cần chứng minh rằng với 1 i j m
thì axi b ax j b mod m . Thật vậy, nếu axi b ax j b mod m thì
axi ax j mod m . Vì a nguyên tố với m nên xi x j mod m . Vô lý vì xi và
x j là 2 thặng dư khác nhau của một hệ thặng dư đầy đủ môđun m.
Vậy ax1 b, ax2 b,..., axm b cũng là một hệ thặng dư đầy đủ
môđun m.
3.2. Hệ thặng dƣ thu gọn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
14
Cho m là một số nguyên dương. Tập hợp K gồm những số nguyên được
lấy ra ở mỗi lớp nguyên tố với môđun m một và chỉ một số được gọi là một hệ
thặng dư thu gọn môđun m.
Vậy một tập hợp K gồm những số nguyên được gọi là một hệ thặng dư
thu gọn môđun m nếu và chỉ nếu:
- Các phần tử thuộc K đôi một không đồng dư với nhau theo môđun m.
- Các phần tử thuộc K nguyên tố với môđun m.
- Mỗi số nguyên tùy ý nguyên tố với môđun m đều đồng dư với một số
nào đó thuộc K.
Nhận xét
Mỗi hệ thặng dư đầy đủ đều chứa duy nhất một hệ thặng dư thu gọn.
Hệ thặng dư thu gọn không âm nhỏ nhất r1 , r2 , ..., r m là hệ thặng dư
thu gọn gồm các phần tử 0 ri m, i 1,2,..., m nguyên tố cùng nhau với m.
Ta có khái niệm hệ thặng dư thu gọn môđun m có trị tuyệt đối nhỏ nhất.
Ví dụ
Khi m = 8 ta có 1, 3, 5,7 là một hệ thặng dư thu gọn không âm nhỏ nhất.
Hệ 3, , 1, 0, 1, 3 là một hệ thặng dư thu gọn giá trị tuyệt đối nhỏ nhất.
Nếu m p là một số nguyên tố thì 1, 2, ..., p 1 là hệ thặng dư thu
p 1 p 1
gọn không âm nhỏ nhất và nếu p 2 thì , ..., 2, 1, 0, 1, 2, ...,
2 2
là hệ thặng dư thu gọn giá trị tuyệt đối nhỏ nhất.
Tính chất của hệ thặng dƣ thu gọn
Tính chất 1
Mỗi hệ thặng dư thu gọn môđun m gồm φ(m) phần tử.
Chứng minh
Hiển nhiên vì tập hợp *
m có φ(m) phần tử.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
15
Tính chất 2
Mỗi hệ gồm m số nguyên tố với m và đôi một không đồng dư với
nhau theo môđun m đều lập nên một hệ thặng dư thu gọn môđun m.
Chứng minh
Giả sử K a1 , a2 ,..., a m là một hệ gồm m số nguyên nguyên tố
với m và đôi một không đồng dư với nhau theo môđun m.
Vì a1 , a2 ,..., a m nguyên tố với m nên ta có tập hợp a1 , a2 ,..., a m các
lớp theo môđun m là một tập con của *
m
gồm m phần tử, nghĩa là có số
phần tử bằng số phần tử của *
m a , a ,..., a = Z .
, do đó ta có 1 2 m
*
m
Từ *
m
= a , a ,..., a ta được K a , a ,..., a là một hệ thặng
1 2 m 1 2 m
dư thu gọn môđum m.
Tính chất 3
Giả sử a là một số nguyên tố với m. Khi ấy nếu x chạy qua một hệ
thặng dư thu gọn môđun m thì ax cũng chạy qua một hệ thặng dư thu gọn
môđun m.
Chứng minh
Giả sử x chạy qua hệ thặng dư thu gọn x1 , x2 ,..., x m môđun m. Khi
ấy ax1 , ax2 ,..., ax m cũng là một hệ thặng dư thu gọn môđun m.
Thật vậy, ax1 , ax2 ,..., ax m là một hệ gồm (m) số nguyên nguyên tố
với m vì UCLN(a, m) = 1 và UCLN xi , m = 1, (i = 1, 2, ..., φ(m)). Theo tính
chất 2 ở trên, ta chỉ cần chứng minh rằng với i j, 1 i, j m thì
axi ax j (mod m). Giả sử ngược lại, axi ax j (mod m). Do UCLN a, m 1 ta
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn
16
có xi x j (mod m), 1 i, j m . Điều này mâu thuẫn với giả thiết với xi , x j
là hai thặng dư khác nhau của một hệ thặng dư thu gọn.
Vậy ax1 , ax2 ,..., ax m cũng là một hệ thặng dư thu gọn môđun m.
3.3. Các định lí quan trọng
Định lý Euler
Giả sử m là một số tự nhiên lớn hơn 1 và a là một số nguyên tố cùng
nhau với m. Khi ấy ta có
a m 1 mod m .
Chứng minh
Ta cho x chạy qua hệ thặng dư thu gọn môđun m không âm nhỏ nhất
r , r , ..., r . Khi ấy theo tính chất 3, tập hợp ar , a r , ..., ar cũng là
1 2 m 1 2 m
một hệ thặng dư thu gọn môđun m.
Giả sử s1 , s2 , ..., s m là các thặng dư không âm nhỏ nhất tương ứng
cùng lớp với ar1 , a r2 , ..., ar m , tức là 0 si m,1 i m và
ar1 s1 (mod m); ar2 s2 (mod m); …; ar m s m mod m . (3.1)
Khi ấy s1 , s2 , ..., s m cũng là hệ thặng dư thu gọn môđun m không âm
nhỏ nhất.
Vì r , r , ..., r và s , s , ..., s cùng là hệ thặng dư thu gọn
1 2 m 1 2 m
môđun m không âm nhỏ nhất nên ta có rr
1 2
...r m s1s2 ...s m .
Nhân vế với vế m đồng dư thức (3.1) ta được
a m rr
1 2
...r m s1s2 ...s m mod m .
Vì ri , m 1 , (i = 1, 2, ..., φ(m)), nên a 1 mod m .
m
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn