Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1. MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC, ĐẠI SỐ 1. Khái niệm trong số học 1).
Ký hiệu chia hết Cho a và b là hai số nguyên dương. Số a chia hết cho số b ký hiệu là a b Tồn tại n N sao cho: a=b*n Khi đó người ta nói b là ước của a và ký hiệu: b | a. Ước số chung lớn nhất Cho a và b là hai số nguyên dương. Ước số chung lớn nhất của a và b là số tự nhiên m lớn nhất sao cho m | a và m | b.
Khi đó ký hiệu là gcd(a, b) = m. Hai số nguyên tố cùng nhau Cho a và b là hai số nguyên dương. Số a và số b được gọi là 2 nguyên tố cùng nhau gcd(a, b) = 1. Đồng dư modulo Cho n N, n 0 và a, b Z n*.
Một số tính chất của đồng dư modulo (a b) (mod n) [(a mod n) (b mod n)] (mod n) (a * b) (mod n) [(a mod n) * (b mod n)] (mod n) 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Khái niệm trong đại số 1). Khái niệm nhóm Nhóm là một cặp (G, *), trong đó G là tập hợp khác rỗng, * là phép toán hai ngôi trên G thoả mãn ba điều kiện sau: 1. Phép toán có tính kết hợp: (x * y) * z = x * (y * z) với mọi x, y, z G.
Có phần tử phần tử trung lập e G: x * e = e * x = x với mọi x G. Với mọi x G, có phần tử nghịch đảo x’ G: x * x’ = x’ * x = e 2). Nhóm con Cho G là một Nhóm, cho S G và S . S được gọi là Nhóm con của G nếu: 1/.
Phần tử trung lập e của G nằm trong S. S khép kín đối với luật hợp thành trong G (tức là x * y S với mọi x, y S). S khép kín đối với phép lấy nghịch đảo trong G (tức x-1 S với mọi xS). Khái niệm Nhóm Cyclic Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một trong các phần tử của nó.
Tức là có phần tử g G mà với mỗi a G, đều tồn tại số n N để g n = g * g * … * g = a (Chú ý: g * g * … * g là g * g với n lần). Khi đó g được gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G. Nói cách khác: G được gọi là Nhóm Cyclic nếu tồn tại g G sao cho mọi phần tử trong G đều là một luỹ thừa nguyên nào đó của g. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Ví dụ: Nhóm (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1.
Cấp của Nhóm Cyclic: Cho (G, *) là Nhóm Cyclic với phần tử sinh g và phần tử trung lập e. Nếu tồn tại số tự nhiên nhỏ nhất n mà g n = e, thì G sẽ chỉ gồm có n phần tử khác nhau: e, g, g2, g3,. Khi đó G được gọi là nhóm Cyclic hữu hạn cấp n. Nếu không tồn tại số tự nhiên n để g n = e, thì G có cấp .
Ví dụ: (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1, e = 0. Đó là Nhóm Cyclic vô hạn, vì không tồn tại số tự nhiên n để g n = e, c). Cấp của một phần tử trong Nhóm Cyclic: Phần tử G được gọi là có cấp d, nếu d là số nguyên dương nhỏ nhất sao cho d = e, trong đó e là phần tử trung lập của G. Như vậy phần tử có cấp 1, nếu = e.
Tập Zn và Z* Zn = 0, 1, 2,. Tức Zn là tập các số nguyên không âm < n. Tập này cùng với phép cộng lập thành Nhóm Cyclic có phần tử sinh là 1. Đó là Nhóm hữu hạn có cấp n.
Zn* = e Zn, e là nguyên tố cùng nhau với n. Đó là tập các số nguyên dương < n, nhưng nguyên tố cùng nhau với n. được gọi là tập Thặng dư thu gọn theo mod n, lập thành một Nhóm với phép nhân mod n. (n) là số các phần tử của tập Z n*.
10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Một số kết quả Những kết quả sau đã được chứng minh, nhắc lại để sử dụng: * Định lý Lagrange: Cho G là nhóm Cấp n và g G. Khi đó cấp của g là ước của n. * Hệ quả: Giả sử g Z n* có Cấp m thì m là ước của (n).
Nếu p là số nguyên tố thì (p) = p -1. Do đó với mọi b Z *p (tức b nguyên tố với p) thì b (p) 1 (mod n) hay bp -1 1 (mod n). * Định lý: Nếu p là số nguyên tố thì Z *p là Nhóm Cyclic. Chú ý: Phần tử Z n* có cấp d nếu d là số nguyên dương nhỏ nhất sao cho d = e trong Z n* , tức là d 1 (mod n).
Khái niệm Logarit rời rạc Cho p là số nguyên tố, là phần tử nguyên thuỷ của Zp, Z *p. Logarit rời rạc chính là việc giải phương trình x = log (mod p) với ẩn x. Hay phải tìm số x duy nhất sao cho: x (mod p). - Hệ quả: Với p là một số nguyên tố và (a, p) = 1 thì ap-1 (mod p) = 1.
11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Đồng dư và phương trình đồng dư tuyến tính Cho n là một số nguyên dương. Hai số nguyên a và b là đồng dư với nhau theo mô đun n, và viết a b (mod n), nếu n/a-b (tức cũng là nếu a – b chia hết cho n, hay khi chia a và b cho n được cùng một số dư như nhau).7 Quan hệ đồng dư (theo một môđun n) trên tập hợp các số nguyên có các tính chất phản xạ, đối xứng và bắc cầu, tức là một quan hệ tương đương, do đó nó tạo ra một phân hoạch trên tập hợp tất cả các số nguyên Z thành ra các lớp tương đương: hai số nguyên thuộc cùng một lớp tương đương khi và chỉ khi chúng cho cùng một số dư nếu chia cho n. Mỗi lớp tương đương như vậy được đại diện bởi một số duy nhất trong tập hợp Zn = {0, 1, 2, 3, ., n-1}, là số dư chung khi chia các số trong lớp đó cho n.
Vì vậy, ta có thể đồng nhất Zn với tập hợp tất cả các lớp tương đương các số nguyên theo mod n; trên tập đó ta có thể xác định các phép tính cộng, trừ và nhân theo mod n. Một số nguyên x Zn được gọi là nghịch đảo của a theo modn, nếu a. Nếu có số x như vậy thì ta nói a là khả nghịch, và ký hiệu x là a-1 mod n. Thí dụ 22-1 mod 25 = 8, vì 22.
Từ định nghĩa ta có thể suy ra rằng a là khả nghịch theo mod n khi và chỉ khi gcd (a,n) = 1, tức là khi a và n nguyên tố với nhau. Dịnh nghĩa phép chia trong Zn như sau: a : b (mod n) = a. Phép chia chỉ thực hiện được khi b là khả nghịch theo mod n. 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Bây giờ xét các phương trình đồng dư tuyến tính Phương trình đồng dư tuyến tính có dạng a.1) Trong đó a, b, n là các số nguyên, n > 0, x là ẩn số.
Phương trình đó có nghiệm khi và chỉ khi d = gcd (a,n) /b, và khi đó có đúng d nghiệm theo mod n. Thực vậy, đặt a” = a/d, b’ = b/d, n’ = n/d ta thấy phương trình đồng dư (1.1) tương đương với phương trình a’x b’ (mod n’) Vì gcd(a’, n’) = 1, nên phương trình này có một nghiệm theo mod n’: x = xo b’. a’-1 (mod n’) và do đó phương trình (1.1) có d nghiệm theo mod n là: x = xo, xo + n’, ., xo + (d - 1) n’ (mod n) Tất cả d nghiệm đó khác nhau theo mod n, nhưng cùng đồng dư với nhau theo mod n’. Bây giờ ta xét hệ thống các phương trình đồng dư tuyến tính.
Một hệ như vậy có thể đưa về dạng x1 a1 (mod n1 ) x a (mod n ) 2 2 2 .nk, Ni = n/ni. Có định lý sau đây: Định lý về Số dư (định lý số dư Trung Quốc). Giả sử các số nguyên n1, n2, ., nk là từng cặp nguyên tố với nhau. Khi đó, hệ phương trình đồng dư tuyến tính (1.2) có một nghiệm duy nhất theo mod n.
13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nghiệm duy nhất nói trong định lý 1.2 được cho bởi biểu thức: x = ki=1 ai.Mi mod n, trong đó Mi = Ni -1 mod ni (có Mi vì Ni và ni nguyên tố với nhau). Nhận xét: Định lý số dư Trung Quốc cho phép tính đồng dư theo modulo của một số lớn (tích của nhiều số nguyên tố cùng nhau), thông qua tính toán đồng dư theo modulo các số nhỏ (từng thừa số). Ví dụ: Tìm nghiệm của hệ phương trình: x 3118(mod 5353) x 139(mod 391) x 239(mod 247) Vì các số 5353, 391, 247 nguyên tố cùng nhau, nên theo định lý Trung Quốc về số dư hệ, có nghiệm duy nhất theo modulo m = 5353*391*247 = 516976681. Để tìm x mod m ta tính: m1 = m/5353 = 96577 → y1 = 96577-1 mod 5353 = 5329 m2 = m/391 = 1322191 → y2 = 1322191-1 mod 391 = 16 m3 = m/247 = 2093023 → y3 = 2093023-1 mod 247 = 238 x = 31188.238 (mod m) = 13824 (mod m) Nếu (n1, n2) = 1, thì cặp phương trình x a (mod n1) và x a (mod n2) có nghiệm duy nhất x a (mod n) theo mod n với n = n1 n2.
14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Thặng dư thu gọn và phần tử nguyên thủy Tập Zn = {0, 1, 2, ., n-1} thường được gọi là tập các thặng dư đầy đủ theo mod n, vì mọi số nguyên bất kỳ đều có thể tìm được trong Zn một số đồng dư với mình (theo mod n).