Slide Chương 8: Cấu trúc đại số và lý thuyết mã hóa đại số | Môn Linear algebra and Algebraic structures - Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoAR cPSD| 58759230 Chương 8.
CẤU TRÚC ĐẠI SỐ
VÀ LÝ THUYẾT MÃ HÓA ĐẠI SỐ
1/ Một số kiến thức về số nguyên
Định lý 1 (Số dư của phép chia) Cho các số nguyên a b,
với a 0, tồn tại duy nhất các số nguyên q r, sao cho b qa lOMoAR cPSD| 58759230 r , và 0
r a. q là thương và r là số dư của phép của b khi chia cho a. lOMoAR cPSD| 58759230
Nếu b=ac (a b c, , ; a 0) thì b được gọi là chia hết cho a (hay a là
ước của b, hay b là bội của a), và viết là b a hoặc a b| .
Nếu d là ước của cả a và b thì d được gọi là ước chung của a và b. Ước
chung lớn nhất của a và b ký hiệu là gcd(a,b).
Nếu m là bội của cả a và b thì m được gọi là bội chung của a và b. Bội chung
nhỏ nhất của a và b ký hiệu là lcm(a,b). Nếu gcd , ab
1 thì a và b được gọi là nguyên tố cùng nhau. Cho số nguyên dương n.
Hai số nguyên a, b được gọi là đồng dư với nhau theo modulo n nếu a b
n. Ký hiệu a b modn . Chú ý: lOMoAR cPSD| 58759230
1) Nếu a b modn thì a b kn . , với k là một số nguyên nào đó.
2) Nếu a b modn (a, b >0) thì a và b có cùng số dư khi chia cho n.
Ví dụ: 3 5 mod2 vì 3 5 chia hết cho 2 (hoặc có thể hiểu là vì
3 5 k.2, với k 1; hoặc vì 3 chia cho 2 dư 1 và 5 chia cho 2 cũng có số dư là 1).
VÍ DỤ 1 Tìm số nguyên k, biết 0 k 7 và 20 k mod8 . lOMoAR cPSD| 58759230
VÍ DỤ 2 Tìm số nguyên dương m sao cho 13 m mod8 . lOMoAR cPSD| 58759230
Tính chất (của đồng dư)
1. Nếu a b modm thì ak bk modm (k là số nguyên dương). 2. Nếu
a b modm và c d modm thì a c
b d modm và ac bd. . modm
3. Nếu ac b. .c mod m và c nguyên tố cùng nhau với
m thì a b modm lOMoAR cPSD| 58759230 VÍ DỤ 3 VÍ DỤ 4 lOMoAR cPSD| 58759230 VÍ DỤ 4 lOMoAR cPSD| 58759230 VÍ DỤ 5 lOMoAR cPSD| 58759230 VÍ DỤ 5 lOMoAR cPSD| 58759230
Lớp tương đương của số nguyên a theo modulo n là a
b : a b modn
b : b a kn k . ,  . lOMoAR cPSD| 58759230
Lớp tương đương của số nguyên a theo modulo n là a
b : a b modn
b : b a kn k . ,  .
Gọi n là tập hợp chứa tất cả các lớp tương đương của các số nguyên theo modulo n.
VÍ DỤ 6. Liệt kê các phần tử của 3 lOMoAR cPSD| 58759230 n 0, 1,, n 1 . lOMoAR cPSD| 58759230
Định lý 5. Cho a p p 1 2 1 2 p b p pk k, 1 2 1 2 pk k là hai số
nguyên dương bất kỳ với i 0, i 0. Khi đó, gcd a b p, 1 p2 pk k k, min 1 1, min 2 2, min và lcm a b p, 1max 1 1, p2max 2 2, pkmax k k,
Hơn nữa gcd a b, .lcm a b ab, . .
VÍ DỤ 7 Tìm ước chung lớn nhất và bội chung nhỏ nhất của a=120, b=54
Định lý 5. Cho a p p 1 2 1 2 p b p pk k, 1 2 1 2 pk k là hai số nguyên
dương bất kỳ với i 0, i 0. Khi đó, lOMoAR cPSD| 58759230 gcd a b p, 1min 1 1, p2min 2 2, pkmin k k, và lcm a b p,
1 p2 pk k k, max 1 1, max 2 2, max
Hơn nữa gcd a b, .lcm a b ab, . .
VÍ DỤ 7 Tìm ước chung lớn nhất và bội chung nhỏ nhất của a=120, b=54 = 2 . 3.5, = 2.3 , gcd = 2 .3 .5 = 6 , lcm = 2 .3 . 5 = 1080 lOMoAR cPSD| 58759230 Thuật toán Euclide
Định lý 7 (Thuật toán Euclide). Cho a và b là các số nguyên
dương. Ta sử dụng thuật toán chia: a qb r
1 1, 0 r1 b b q r 2 1 a chia b dư r1 r 2, 0 r2 r1 b chia r1 dư r2
r1 q r3 2 r3, 0 r3 r2 r1 chia r2 dư r3 ….
rs 2 qrs s 1 rs,0 rs rs 1 r s-2 chia rs-1 dư rs r
s 1 q rs 1 s Khi đó rs gcd a b, . rs-1 chia hết cho rs VÍ DỤ 7 UCLN là số dư
Tìm ước chung lớn nhất của a=120, b=54 cuối (trước phép VÍ DỤ 7 chia hết)
Tìm ước chung lớn nhất của a=120, b=54 lOMoAR cPSD| 58759230 VÍ DỤ 7
Tìm ước chung lớn nhất của a=120, b=54 Số bị chia Số chia Dư 120 54 12 54 12 6 12 6 0 VÍ DỤ 7
Tìm ước chung lớn nhất của a=120, b=54 Sốbịchia Sốchia Dư 120 54 12 54 12 6 12 6 0 lOMoAR cPSD| 58759230 Vậy gcd(120,54)=6
Định lý 8. Cho a và b là các số nguyên dương. Khi đó tồn tại
các số nguyên m và n sao cho gcd a b ma nb, .
Các số m và n trong định lý trên là không duy nhất. lOMoAR cPSD| 58759230
Thuật toán Euclide mở rộng
Định lý 9 (Thuật toán Euclide mở rộng). Cho ma trận
sau có hai hàng là R R1, 2 và ba cột là C C C1, 2, 3 : C C C1 2 3 RR21 ba 1 00 1 .
Theo thuật toán Euclide ở trên, ta biểu diễn các hàng
R3 : R q R R1 1 2, 4 : R2 q R2 3, mỗi khi tạo ra một hàng mới, ta được a 1 0 b 0 1 C C C12 3 r1 1 1 qqq1 21 lOMoAR cPSD| 58759230 r2 q2 rs m n
Khi đó gcd a b, rs ma nb.
VÍ DỤ 8 Cho a=321, b=843. Tìm một biểu diễn tuyến tính của ước chung lớn
nhất ở dạng gcd(a,b)=ma+nb