Tài liệu Luật tương hỗ bậc hai theo zolotarev frobenius

Header Page 1 of 161. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Đỗ Thị Vân Anh Luật tương hỗ bậc hai theo Zolotarev–Frobenius KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Hà Nội – Năm 2016 Footer Page 1 of 161. Header Page 2 of 161. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Đỗ Thị Vân Anh Luật tương hỗ bậc hai theo Zolotarev–Frobenius Chuyên ngành: Đại số KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Hoàng Lê Trường Hà Nội – Năm 2016 Footer Page 2 of 161. Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 3 of 161. LỜI CẢM ƠN Khóa luận tốt nghiệp này của em đã được hoàn thành dưới sự chỉ đạo, hướng dẫn tận tình của Tiến sĩ Hoàng Lê Trường. Qua đây em xin được bày tỏ lòng biết ơn sâu sắc tới Tiến sĩ Hoàng Lê Trường, người đã trực tiếp tạo điều kiện và giúp đỡ em trong suốt thời gian làm khóa luận. Em xin gửi lời cảm ơn chân thành tới các thầy cô giáo trong tổ Đại số cũng như các thầy cô giáo trong khoa Toán trường Đại học Sư phạm Hà Nội 2 đã tạo điều kiện tốt nhất để em hoàn thành khóa luận tốt nghiệp này. Em xin chân thành cảm ơn! Hà Nội, tháng 5 năm 2016 Sinh viên Đỗ Thị Vân Anh 1 Footer Page 3 of 161. Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 4 of 161. LỜI CAM ĐOAN Khóa luận tốt nghiệp này của em được hoàn thành dưới sự hướng dẫn nhiệt tình của Tiến sĩ Hoàng Lê Trường cùng với sự cố gắng của bản thân. Trong quá trình nghiên cứu, em đã tham khảo và kế thừa những thành quả nghiên cứu của các nhà khoa học và các nhà nghiên cứu với sự trân trọng và lòng biết ơn. Em xin cam đoan những kết quả nghiên cứu của riêng bản thân, không có sự trùng lặp với kết quả của các tác giả khác. Nếu sai em xin hoàn toàn chịu trách nhiệm. Hà Nội, tháng 5 năm 2016 Sinh viên Đỗ Thị Vân Anh Footer Page 4 of 161. i Header Page 5 of 161. Mục lục Lời mở đầu 1 1 MỘT SỐ KHÁI NIỆM CỦA ĐẠI SỐ 1.1 Tính chia hết và ước chung lớn nhất . 1.2 Số học mô-đun . . . . . . . . . . . . . 1.3 Số nguyên tố, sự phân tích duy nhất và 1.4 Lũy thừa của trường hữu hạn . . . . . 1.5 Căn nguyên thủy của trường hữu hạn . 1.5.1 Đa thức trên Z/pZ . . . . . . . 1.5.2 Sự tồn tại của căn nguyên thủy 1.6 Định lý thặng dư Trung Hoa . . . . . . . . . . . . . . . . . . . . . . . . trường hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 LUẬT TƯƠNG HỖ GAUSS 2.1 Số chính phương modulo p . . . . . . . . . . 2.2 Tiêu chuẩn Euler . . . . . . . . . . . . . . . 2.3 Nhóm . . . . . . . . . . . . . . . . . . . . . 2.4 Nhóm đối xứng . . . . . . . . . . . . . . . . 2.5 Chứng minh của luật tương hỗ bậc hai . . . 2.6 Áp dụng luật tương hỗ bậc hai cho toán phổ Tài liệu tham khảo Footer Page 5 of 161. . . . . . . . . . . . . . . . . . . . . thông . . . . . . . . . . . . . . . . . . . . 4 4 11 15 18 24 24 25 26 . . . . . . 30 30 32 35 39 46 48 57 ii Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 6 of 161. Lời mở đầu 1. Lí do chọn đề tài Khoảng đầu thế kỉ 19 các cuốn sách của Legendre (1798), và Gauss kết hợp thành những lý thuyết có hệ thống đầu tiên ở châu Âu. Cuốn Disquisitiones Arithmeticae (1801) có thể nói là đã mở đầu lý thuyết số hiện đại. Sự hình thành lý thuyết đồng dư bắt đầu với cuốn Disquisitiones của Gauss. Ông giới thiệu kí hiệu a ≡ b (mod c), và đã khám phá ra hầu hết trong lĩnh vực này. Chebyshev đã xuất bản vào năm 1847 một công trình bằng tiếng Nga về chủ đề này, và ở Pháp Serre đã phổ biến nó ([5]). Bên cạnh những công trình tổng kết trước đó, Legendre đã phát biểu luật tương hỗ bậc hai như sau: Cho hai số nguyên tố lẻ p và q, khi đó ta có     p−1 q−1 q p · = (−1) 2 · 2 q p trong đó     0 a = +1  p  −1 nếu gcd(a, p) 6= 1 nếu a là thặng dư bậc hai nếu a là phi thặng dư bậc hai. Định lý này, được khám phá ra bởi qui nạp và được diễn đạt bởi Euler, đã được chứng minh lần đầu tiên bởi Legendre trong cuốn Théorie des Nombres của ông (1798) trong những trường hợp đặc biệt. Độc lập với Euler và Legendre, Gauss đã khám phá ra định luật này vào khoảng năm 1795, và là người đầu tiên đưa ra chứng minh tổng quát. Luật này liên quan đến tính giải được của hai phương trình đồng dư bậc hai. Từ đó nó cho phép ta xác định tính giải được của phương trình đồng dư bậc hai bất kỳ, tuy nhiên nó không cung cấp một phương pháp hiệu quả để tìm nghiệm. Gauss gọi đó là ’định lý vàng’ và rất tự hào về nó đến mức ông tiếp tục tìm ra tám chứng minh khác cho nó cho đến cuối đời. Luật tương hỗ bậc hai được cho là định lý quan trọng nhất được giảng dạy trong các giáo trình về Lí thuyết số sơ cấp. Tầm quan trọng của luật tương hỗ bậc hai đã làm cho nhiều nhà toán học khác như Footer Page 6 of 161. 1 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 7 of 161. Jacobi, Cauchy, Liousville, Kronecker, Schering, Frobenius, Artin([1, 2]) nghiên cữu nó sau Gauss và chúng ta đã có hơn 100 chứng minh khác nhau đã được phát hiện. Trong khóa luận này, chúng ta sẽ chứng minh luật tương hỗ bậc hai  liênquan đến tổ hợp và nhóm các hoán vị, bắt a nguồn từ ý tưởng xem như là dấu của hoán vị trên Z/pZ bởi phép q nhân a, của Zolotarev năm 1872([4],[8]). Là sinh viên ngành sư phạm toán, trên cơ sở đã được trang bị các kiến thức nền tảng về đại số và với mong muốn được học hỏi trau dồi thêm vốn kiến thức về toán học nói chung và các kiến thức cơ sở của đại số nói riêng. Chính vì vậy, tôi đã lựa chọn đề tài: "Luật tương hỗ bậc hai theo Zolotarev–Frobenius" cho khóa luận tốt nghiệp của mình. Trong đề tài này tôi dự kiến hệ thống những kiến thức cơ bản nhất về đại số làm cơ sở lí luận để tìm hiểu luật tương hỗ Gauss. 2. Mục đích nghiên cứu Hệ thống hóa một cách khoa học các khái niệm của đại số kèm theo các ví dụ, nghiên cứu cách chứng minh của luật tương hỗ Gauss. 3. Đối tượng và phạn vi nghiên cứu Đối tượng chính mà khóa luận nghiên cứu là luật tương hỗ Gauss, trong đó tập chung vào cách chứng minh của nó. Bên cạnh đó khóa luận còn trình bày hệ thống các khái niệm bổ trợ có thể thể coi như kiến thức chuẩn bị phục vụ cho nghiên cứu đối tượng chính. 4. Phương pháp nghiên cứu khoa học + Phương pháp nghiên cứu lí luận: trước hết là đọc các tài liệu liên quan đến lí thuyết cơ sở đại số. Sau đó là đọc, nghiên cứu và hiểu về luật tương hỗ Gauss. + Phương pháp tổng kết kinh nghiệm: Tổng hợp, hệ thống hóa kiến thức về vấn đề nghiên cứu đầy đủ và khoa học, đưa vào các ví dụ minh họa chi tiết. 5. Ý nghĩa khoa học và thực tiễn Khóa luận có thể là tài liệu tham khảo cho những sinh viên chuyên ngành Toán có mong muốn tìm hiểu sâu hơn về lý thuyết số cụ thể là luật tương hỗ Gauss . 6. Bố cục của khóa luận Ngoài phần Mở đầu, Kết luận và Tài liệu tham khảo, nội dung của khóa luận gồm hai chương. Chương 1 : Một số khái niệm của đại số Footer Page 7 of 161. 2 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 8 of 161. Chương 2 : Luật tương hỗ Gauss Footer Page 8 of 161. 3 Header Page 9 of 161. Chương 1 MỘT SỐ KHÁI NIỆM CỦA ĐẠI SỐ 1.1 Tính chia hết và ước chung lớn nhất Ở mức độ cơ sở nhất, Lý thuyết số là việc nghiên cứu về các số tự nhiên 1, 2, 3, 4, 5, 6, · · · , hay tổng quát hơn là nghiên cứu về các số nguyên · · · , −5, −4, −3, −2, −1, 0, 1, 2, 3, 4, 5, · · · Tập hợp các số nguyên được ký hiệu là Z. Các số nguyên có trừ và nhân theo cách thông thường, và thỏa mãn tất cả các thông thường của số học (tính chất giao hoán, tính chất kết chất phân phối,..). Tập hợp các số nguyên với các tính chất cộng và phép nhân là một ví dụ về vành. thể cộng, tính chất hợp, tính của phép Định nghĩa 1.1. Cho a và b là số nguyên với b 6= 0. Ta nói rằng b chia hết a, hay a được chia hết bởi b, nếu có một số nguyên c sao cho a = bc. Ta viết b | a thay cho b chia hết a. Nếu b không chia hết a, thì ta viết b - a. Ví dụ 1.2. Ta có 5 | 20, vì 20 = 5 · 4, 6 - 20, vì 20 = 6 · 3 + 2, vì vậy 20 không phải là bội của 6. Footer Page 9 of 161. 4 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 10 of 161. Nhận xét 1.3. Mỗi số nguyên đều được chia hết bởi 1. Những số nguyên được chia hết bởi 2 được gọi là số chẵn, và những số nguyên không được chia hết bởi 2 được gọi là số lẻ. Mệnh đề 1.4. Cho a, b, c là số nguyên. Khi đó, các mệnh đề sau là đúng. 1. Nếu a | b và b | c, thì a | c. 2. Nếu a | b và b | a, thì a = ±b. 3. Nếu a | b, và a | c, thì a | (b + c) và a | (b − c). Chứng minh. 1. Vì a | b và b | c nên tồn tại a1 ∈ Z và b1 ∈ Z sao cho b = aa1 và c = bb1. Ta có c = (aa1 )b1 = a(a1 b1 ), do đó a | c. 2. Vì a | b và b | a nên tồn tại a1 , b1 ∈ Z sao cho b = aa1 và a = bb1 . Ta có b = (bb1)a1 = b(b1a1 ). Do đó a1 b1 = 1 và a1 = b1 = ±1. Vậy a = ±b. 3. Vì a | b và b | c nên tồn tại a1 , a2 ∈ Z sao cho b = aa1 và c = aa2 . Do đó b + c = a(a1 + a2 ) và b − c = a(a1 − a2 ). Vậy a | (b + c) và a | (b − c). Định nghĩa 1.5. Ước chung của hai số nguyên a và b là số nguyên dương d chia hết cả a và b. Ước chung lớn nhất của a và b là số nguyên dương lớn nhất d sao cho d | a và d | b. Ước chung lớn nhất của a và b được kí hiệu là gcd(a, b) hay (a, b). (Nếu a và b bằng 0, thì gcd(a, b) không xác định.) Ví dụ 1.6. Ước chung lớn nhất của 12 và 18 là 6. Tương tự ta có, ước chung lớn nhất của 748 và 2024 là 24. Một cách kiểm tra là liệt kê tất cả các ước nguyên dương của 748 và 2024. Ước của 748 = {1, 2, 4, 11, 17, 22, 34, 44, 68, 187, 374, 748}. Ước của 2024 = {1, 2, 4, 8, 11, 22, 23, 44, 46, 88, 92, 184, 253, 506, 1012, 2024}. Kiểm tra hai dãy trên, ta thấy ước chung lớn nhất của 748 và 2024 là 44. Từ ví dụ này ta thấy, đây không phải là phương pháp hiệu quả. Nếu cần tính ước chung lớn nhất của các số lớn, ta sẽ phải tìm phương pháp khác hiệu quả hơn. Footer Page 10 of 161. 5 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 11 of 161. Chìa khóa để tìm thuật toán hiệu quả hơn cho việc tính ước chung lớn nhất là phép chia có dư. Do đó nếu a và b là số nguyên dương và nếu chia a bởi b, chúng ta sẽ được thương q và số dư r, phần dư r nhỏ hơn b. Ví dụ 230 được chia bởi 17, ta được thương là 13 với số dư là 9, tức là 230 = 17 · 13 + 9, với số dư 9 nhỏ thực sự hơn số chia 17. Định nghĩa 1.7. (Thuật toán chia) Cho a và b là hai số nguyên dương. a được chia bởi b có thương q và số dư r nghĩa là với 0 ≤ r < b. a=b·q+r Giá trị của q và r là duy nhất được xác định bởi a và b. Định lý 1.8. (Thuật toán Euclid). Cho a và b là số nguyên dương với a ≥ b. Thuật toán dưới đây tính gcd(a, b) trong một số hữu hạn bước. Bước 1: Cho r0 = a và r1 = b. Bước 2: Đặt i = 1. Bước 3: Chia ri−1 bởi ri nhận được thương qi và số dư ri+1, với 0 ≤ ri+1 < ri. ri−1 = ri qi + ri+1 Bước 4: Nếu số dư ri+1 = 0, thì ri = gcd(a, b) và thuật toán kết thúc. Bước 5: Nếu ri+1 > 0, ta đặt i = i + 1 và bắt đầu bước 3. Các bước của phép chia được thực hiện nhiều nhất 2 log2 (b) + 1 lần. Chứng minh. Thuật toán Euclid bao gồm một dãy của phép chia với dư được minh họa như sau (ta đặt r0 = a và r1 = b). a = b · q1 + r2 với 0 ≤ r2 < b, b = r2 · q2 + r3 với 0 ≤ r3 < r2 , r2 = r3 · q3 + r4 với 0 ≤ r4 < r3 , r3 = r4 · q4 + r5 .. . với 0 ≤ r5 < r4 , .. . rt−2 = rt−1 · qt−1 + rt với 0 ≤ rt < rt−1 , rt−1 = rt · qt . Thì rt = gcd(a, b). Bảng 1.1: * Giá trị ri giảm dần, và ngay sau khi ri bằng 0 thì thuật toán kết thúc, Footer Page 11 of 161. 6 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 12 of 161. điều này chứng minh rằng thuật toán kết thúc sau hữu hạn bước. Hơn nữa, tại mỗi lần lặp lại bước 3, ta có một phương trình có dạng ri−1 = ri · qi + ri+1. Phương trình này suy ra rằng bất kỳ ước chung của ri−1 và ri đều là ước của ri+1, tương tự ta cũng có bất kỳ ước chung của ri và ri+1 cũng là ước của ri−1. Do đó gcd(ri−1, ri) = gcd(ri, ri+1) với mọi i ∈ N Tuy nhiên, như đã nói ở trên, cuối cùng chúng ta cũng có một ri = 0. Giả sử rt+1 = 0 khi đó rt−1 = rt · qt , vì vậy gcd(rt−1, rt ) = gcd(rt · qt , rt) = rt . Ta cần chứng minh số dư cuối cùng khác không trong thuật toán Euclid bằng ước chung lớn nhất của a và b. Vì giá trị ri là giảm dần, và r1 = b. Do đó thuật toán sẽ kết thúc tại nhiều nhất là b bước. Ta thấy điều ràng buộc trên là không xác thực. Vì sau mỗi lần lặp lại bước 3, giá trị của ri giảm ít nhất một nửa. Nói cách khác, ta có bổ đề sau. Bổ đề: ri+2 < 21 ri với mọi i ∈ N Chứng minh. Để chứng minh bổ đề này, ta cần xem xét hai trường hợp. Trường hợp 1: ri+1 ≤ 21 ri . Vì giá trị ri giảm dần, nên 1 ri+2 < ri+1 ≤ ri. 2 Trường hợp 2: ri+1 > 21 ri Vì giá trị của ri+1 > 21 ri nên ri = ri+1 · 1 + ri+2. Do đó ri+2 = ri − ri+1 < ri − 21 ri = 12 ri . Ta đã chứng minh được bổ đề trên là ri+2 < 21 ri với mọi i ∈ N. Áp dụng bổ đề này lặp đi lặp lại, ta có r2k+1 < 21 r2k−1 < 14 r2k−3 < 81 r2k−5 < · · · < Footer Page 12 of 161. 7 1 r 2k 1 = 1 b. 2k Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 13 of 161. Do đó, nếu 2k ≥ b, thì r2k+1 < 1, suy ra r2k+1 = 0 và thuật toán kết thúc. Giá trị của rt+1 = 0, vì vậy ta có t + 1 ≤ 2k + 1, và do đó t ≤ 2k. Thêm vào đó, có t phép chia, vì vậy thuật toán Euclid kết thúc sau 2k lần lặp lại. Chọn số k nhỏ nhất sao cho 2k ≥ b > 2k−1, thì: số lần lặp lại ≤ 2k = 2(k − 1) + 2 < 2 log2(b) + 2, từ đó định lý được chứng minh. Chúng ta cùng minh họa thuật toán Euclid bằng một ví dụ. Ví dụ 1.9. Tìm gcd(2024, 748) sử dụng thuật toán Euclid, đó là việc lặp đi lặp lại nhiều lần phép chia có dư. 2024 = 748 · 2 + 528, 748 = 528 · 1 + 220, 528 = 220 · 2 + 88, 220 = 88 · 2 + 44, 88 = 44 · 2 + 0. Vậy gcd(2024, 748) = 44. Định lý 1.10. (Thuật toán Euclid mở rộng). Cho a và b là số nguyên dương. Phương trình au + bv = gcd(a, b) luôn tìm được nghiệm nguyên u và v. Nếu (u0, v0) là nghiệm bất kỳ, thì mỗi nghiệm của phương trình au + bv = gcd(a, b) đều có dạng u = u0 + b·k gcd(a, b) và v = v0 − a·k gcd(a, b) với k ∈ Z . Chứng minh. Từ bảng 1.1, ta có thể giải quyết dòng đầu tiên với r2 = a − b · q1 và thay thế nó vào dòng thứ hai được b = (a − b · q1 ) · q2 + r3 , vì vậy r3 = −aq2 + b(1 + q1 q2). Thay vào biểu thức tiếp theo với r2 và r3 vào dòng thứ ba ta được a − b · q1 = (−a · q2 + b · (1 + q1q2 ))q3 + r4. Sau khi tính toán ta được r4 = a · (1 + q2q3 ) − b · (q1 + q2 + q1 · q2 · q3 ). Footer Page 13 of 161. 8 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 14 of 161. Điểm quan trọng là r4 = a · u + b · v, với u và v là số nguyên. Tiếp tục quá trình này, ở mỗi bước ta tìm được ri là tổng một bội của a và một bội của b. Cuối cùng, ta đặt rt = a.u + b.v, với số nguyên u và v. Nhưng rt = gcd(a, b), do đó hoàn thành việc chứng minh phần đầu tiên của định lý. Nếu (u0, v0) là nghiệm nguyên bất kỳ của phương trình au + bv = gcd(a, b) và u = u0 + b·k gcd(a, b) và v = v0 − a·k gcd(a, b) với k ∈ Z thì ta có a · (u0 + a·k b·k ) + b · (v0 − ) = a · u0 + b · v0 = gcd(a, b). gcd(a, b) gcd(a, b) Do đó u = u0 + b·k gcd(a, b) và v = v0 − a·k gcd(a, b) với k ∈ Z cũng là nghiệm của phương trình au + bv = gcd(a, b). Ví dụ 1.11. Quay về ví dụ 1.1.9, ta sử dụng thuật toán Euclid để tính gcd(2024, 748) như sau: 2024 = 748 · 2 + 528, 748 = 528 · 1 + 220, 528 = 220 · 2 + 88, 220 = 88 · 2 + 44, 88 = 44 · 2 + 0. Vậy gcd(2024, 748) = 44. Đặt a = 2024 và b = 748, vì vậy dòng đầu tiên nói rằng 528 = a − 2b. Thay thế điều này vào dòng thứ hai ta được b = (a − 2b) · 1 + 220 vì vậy 220 = −a + 3b. Tiếp tục thay thế các biểu thức 528 = a − 2b và 220 = −a + 3b vào dòng thứ ba ta được Footer Page 14 of 161. 9 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 15 of 161. a − 2b = (−a + 3b) · 2 + 88 vì vậy 88 = 3a − 8b. Cuối cùng, thay biểu thức 220 = −a + 3b và 88 = 3a − 8b vào dòng cuối cùng ta được −a + 3b = (3a − 8b) · 2 + 44 vì vậy 44 = −7a + 19b. Nói cách khác, −7 · 2024 + 19 · 748 = 44 = gcd(2024, 748). Từ đó, chúng ta đã tìm thấy thấy một cách viết gcd(a, b) như một biểu thức tuyến tính của các số nguyên a và b, đó là kết quả đơn giản với nhiều hệ quả quan trọng. Trường hợp đặc biệt của thuật toán Euclid mở rộng là ước chung lớn nhất của a và b bằng 1. Định nghĩa 1.12. Cho a và b là số nguyên. Chúng ta nói rằng a và b là nguyên tố cùng nhau nếu gcd(a, b) = 1. Tổng quát hơn, phương trình A · u + B · v = gcd(A, B) có thể đưa về trường hợp các số nguyên tố cùng nhau bằng cách chia cả hai vế cho gcd(A, B). Do đó B A ·u+ · v = 1. gcd(A, B) gcd(A, B) Với a= A gcd(A, B) và b= B gcd(A, B) là nguyên tố cùng nhau và thỏa mãn a · u + b · v = 1. Ví dụ 1.13. Chúng ta đã tìm được ước chung lớn nhất của 2024 và 748 là 44 thỏa mãn −7 · 2024 + 19 · 748 = 44. Chia cả hai vế cho 44 , ta được −7 · 46 + 19 · 17 = 1. Do đó, 2024/44 = 46 và 748/44 = 17 là nguyên tố cùng nhau, với u = −7 và v = 19 là hệ số của một biểu thức tuyến tính của 46 và 17. Footer Page 15 of 161. 10 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 16 of 161. 1.2 Số học mô-đun Chúng ta đã gặp ”đồng hồ số học” ở trường lớp, khi đến số 12, thì số tiếp theo là số 1. Từ đó dẫn đến phương trình và 7+8=3 1 − 3 = 10. Nhìn điều này lạ, nhưng nó sử dụng đúng với đồng hồ số học, từ ví dụ 10 : 00 là 3 giờ trước của 1 : 00. Vì vậy lần đầu tiên ta tính được 1 − 3 = −2, sau đó cộng thêm 12 để được câu trả lời. Tương tự, 9 giờ sau 6 : 00 là 3 : 00, vì 6 + 9 − 12 = 3. Định lý về đồng dư là một phương pháp trong lý thuyết số, cái mà dựa trên ý tưởng đơn giản của đồng hồ số học. Định nghĩa 1.14. Cho m ≥ 1 là một số nguyên. Ta nói rằng số nguyên a và b là đồng dư môđun m, nếu hiệu a − b được chia hết bởi m. Ta viết a≡b (mod m) để chỉ ra a và b là đồng dư môđun m. Số m được gọi là môđun. Trong ví dụ về đồng hồ số học, chúng ta có thể viết như quan hệ đồng dư sử dụng môđun m = 12, như 6 + 9 = 15 ≡ 3 (mod 12) và 2 − 3 = −1 ≡ 11 (mod 12). Ví dụ 1.15. Ta có 17 ≡ 7 (mod 5) vì 5 chia hết 10 = 17 − 7. Mặt khác, 19 6≡ 6 (mod 11) vì 11 không chia hết 13 = 19 − 6. Chú ý rằng các số thỏa mãn a ≡ 0 (mod m) là các số được chia hết bởi m hay là bội của m. Mệnh đề 1.16. Cho m ≥ 1 là một số nguyên. Khi đó các mệnh đề sau là đúng. 1. Nếu a1 ≡ a2 (mod m) và b1 ≡ b2 (mod m), thì chúng ta có a1 ± b1 ≡ a2 ± b2 (mod m) Footer Page 16 of 161. 11 và a1 .b1 ≡ a2 .b2 (mod m). Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 17 of 161. 2. Cho a là số nguyên. Thì a.b ≡ 1 (mod m) với một số b khi và chỉ khi gcd(a, m) = 1. Nếu số nguyên b tồn tại thì ta nói rằng b là nghịch đảo của a môđun m. Chứng minh. 1. Vì a1 ≡ a2 (mod m) và b1 = b2 (mod m), nên m | (a1 − a2 ) và m | (b1 − b2 ). Do đó m | ((a1 − a2 ) ± (b1 − b2 )) và m | ((a1 ± b1) − (a2 ± b2)). Vậy (a1 ± b1) ≡ (a2 ± b2) (mod m). Vì a1 ≡ a2 (mod m) và b1 = b2 (mod m), nên m | (a1 − a2 ) và m | (b1 − b2). Khi đó tồn tại u, v ∈ Z sao cho a1 = b1 + um và a2 = b2 + vm. Do đó a1 a2 = b1b2 + m(b1 v + b2 u) + m2 uv và m | (a1a2 − b1 b2) = m(b1v + b2u) + m2 uv. Vậy a1 a2 ≡ b1 b2 (mod m). 2. Giả sử gcd(a, m) = 1, thì tồn tại số nguyên u, v sao cho au+mv = 1. Do đó au − 1 = −mv và m | (au − 1), vì vậy từ định nghĩa ta có au ≡ 1 (mod m). Nói cách khác, ta có thể đặt b = u. Ngược lại, giả sử a có một nghịch đảo môđun m, tức là a.b ≡ 1 (mod m). Điều đó có nghĩa là m | (ab − 1), khi đó tồn tại số nguyên c sao cho ab − 1 = cm, do đó ab + (−c)m = 1. Vậy gcd(a, m) = 1. Định lý đã chứng minh được a có một nghịch đảo môđun m khi và chỉ khi gcd(a, m) = 1. Ví dụ 1.17. Ta có m = 5 và a = 2. Rõ ràng gcd(2, 5) = 1, vì vậy tồn tại một nghịch đảo của 2 môđun 5. Nghịch đảo của 2 môđun 5 là 3 vì 2 · 3 ≡ 1 (mod 5), vì vậy 2−1 ≡ 3 (mod 5). Tương tự gcd(4, 15) = 1 vì vậy tồn tại 4−1 môđun 15. Ta có 4 · 4 ≡ 1 (mod 15), vì vậy 4 là nghịch đảo của riêng nó môđun 15. Chúng ta có thể làm việc với phân số a/d môđun m với điều kiện (d, m) = 1. Ví dụ, chúng ta có thể tính 5/7 modun 11. Lưu ý rằng 7 · 8 ≡ 1 (mod 11), vì vậy 7−1 = 8 (mod 11). Do đó ta có 5 = 5 · 7−1 ≡ 5 · 8 ≡ 40 ≡ 7 (mod 11). 7 Nhận xét 1.18. Trong ví dụ trước, chúng ta dễ dàng tìm nghịch đảo môđun m bởi việc thử. Tuy nhiên, khi m lớn, chúng ta lại gặp vấn đề Footer Page 17 of 161. 12 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 18 of 161. lớn để tính a−1 môđun m. Lưu ý rằng, chúng ta chỉ ra rằng tồn tại phần tử nghịch đảo bằng cách sử dụng thuật toán Euclid mở rộng. Để tính u và v xuất hiện trong phương trình au + mv = gcd(a, m), chúng ta có thể áp dụng thuật toán Euclid trực tiếp như đã làm ở ví dụ 1.13.Trong mọi trường hợp, vì thuật toán Euclid chỉ mất 2 log2 (b) + 3 lần lặp lại để tính gcd(a, b), nó chỉ mất nhỏ hơn log2 (m) bước để tính a−1 môđun m. Bây giờ, nếu a chia m có thương q và số dư r, nó có thể được viết như là a = mq + r với 0 ≤ r < m. Điều này chỉ ra rằng a ≡ r (mod m) với những số nguyên r ở giữa 0 và m − 1, vì vậy nếu chúng ta muốn làm việc với các số nguyên môđun m, chúng ta chỉ cần sử dụng các số nguyên 0 ≤ r < m. Từ đó ta có định nghĩa sau. Định nghĩa 1.19. Ta viết Z/mZ = {0, 1, 2, · · · , m − 1} và gọi Z/mZ là vành các số nguyên môđun m. Bất cứ lúc nào ta cũng có thể thực hiện cộng hoặc nhân trong Z/mZ, và chia kết quả cho m và lấy số dư đế có được một phần tử trong Z/mZ. Nhận xét 1.20. Nếu chúng ta biết về lý thuyết vành, Z/mZ là vành thương của Z bởi ideal chính mZ, và các số 0, 1, 2, · · · , m − 1 là đại diện cho các lớp đồng dư bao gồm các phần tử của Z/mZ. Định nghĩa 1.21. Mệnh đề 1.16 (2) nói với chúng ta rằng a có một nghịch đảo môđun m khi và chỉ khi gcd(a, m) = 1. Số mà có nghịch đảo được gọi là khả nghịch. Chúng ta kí hiệu tập tất cả các phần tử khả nghịch bởi (Z/mZ)∗ = {a ∈ Z/mZ : gcd(a, m) = 1} = {a ∈ Z/mZ : a có một nghịch đảo modun m}. ∗ Tập (Z/mZ) được gọi là nhóm các phần tử khả nghịch môđun m. Chú ý rằng nếu a1 và a2 là khả nghịch môđun m, thì a1 a2 cũng vậy. Nhưng nếu cộng hai phần tử khả nghịch, ta có thể không được một phần tử khả nghịch. Footer Page 18 of 161. 13 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 19 of 161. + 0 1 2 3 4 · 0 1 2 3 4 0 0 1 2 3 4 0 0 0 0 0 0 1 1 2 3 4 0 1 0 1 2 3 4 2 2 3 4 0 1 2 0 2 4 1 3 3 3 4 0 1 2 3 0 3 1 4 2 4 4 0 1 2 3 4 0 4 3 2 1 Bảng 1.2: Bảng phép cộng và phép nhân mô-đun 5 Ví dụ 1.22. Bảng sau đây minh họa hoàn chỉnh phép cộng và nhân trong vành Z/5Z. Ví dụ 1.23. Nhóm các phần tử khả nghịch môđun 24 là (Z/24Z)∗ = {1, 5, 7, 11, 13, 17, 19, 23}. Phép nhân trong (Z/24Z)∗ được minh họa trong bảng 1.3. · 1 5 7 11 13 17 19 23 1 1 5 7 11 13 17 19 23 5 5 1 11 7 17 13 23 19 7 7 11 1 5 19 23 13 17 11 11 7 5 1 23 19 17 13 13 13 17 19 23 1 5 7 11 17 17 13 23 19 5 1 11 7 19 19 23 13 17 7 11 1 5 23 23 19 17 13 11 7 5 1 Bảng 1.3: Nhóm các phần tử khả nghịch mô-đun 24 Ta có định nghĩa sau. Định nghĩa 1.24. Hàm số Euler φ là hàm số φ(m) được định nghĩa bởi quy tắc φ(m) = |(Z/mZ)∗| = |{0 ≤ a < m | gcd(a, m) = 1}|. Ví dụ φ(24) = 8 và φ(7) = 6. Ví dụ 1.25. Nhóm các phần tử khả nghịch môđun 7 là (Z/7Z)∗ = {1, 2, 3, 4, 5, 6} vì mỗi số nguyên ở giữa 1 và 6 đều nguyên tố với 7. Phép nhân trong (Z/7Z)∗ được minh họa trong bảng sau. Footer Page 19 of 161. 14 Khóa luận tốt nghiệp Đại học Đỗ Thị Vân Anh Header Page 20 of 161. 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1 · Bảng 1.4: Nhóm các phần tử khả nghịch mô-đun 7 1.3 Số nguyên tố, sự phân tích duy nhất và trường hữu hạn Trong phần 1.2, chúng ta đã đề cập đến số học mô-đun và đã chỉ ra rằng lý thuyết số học mô-đun có ý nghĩa đối với phép cộng, trừ và nhân số nguyên m. Chúng ta chỉ có thể chia bởi a trong Z/mZ khi gcd(a, m) = 1. Nhưng nếu số m là nguyên tố thì ta có thể chia bởi mỗi phần tử khác không của Z/mZ. Định nghĩa 1.26. Số nguyên p được gọi là số nguyên tố nếu p ≥ 2 và p chỉ được chia hết bởi 1 và p. Ví dụ 1.27. Mười số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 trong khi số nguyên tố thứ hàng trăm nghìn là 1299709 và thứ một triệu là 15485863. Có vô hạn các số nguyên tố, thực tế đó đã được biết đến trong thời Hi lạp cổ đại và xuất hiện như là một định lý trong thời Euclid. Số nguyên tố p được xác định theo những số chia p. Vì vậy mệnh đề sau đây mô tả tính chất của những số mà chia hết bởi p. Chú ý rằng mệnh đề nay là sai đối với hợp số. Ví dụ 6 | 3 · 10 nhưng 6 không chia hết 3 hay 10. Mệnh đề 1.28. Cho p là số nguyên tố, và giả sử p chia hết tích ab của hai số nguyên a và b. Thì p chia hết ít nhất một trong hai số a và b. Tổng quát, nếu p chia hết một tích của các số nguyên p | a1 a2 · · · an , thì p chia hết ít nhất một trong các ai , với i = 1, · · · n. Chứng minh. Cho g = gcd(a, p), thì g | p. Vì p nguyên tố nên g = 1 hoặc g = p. Nếu g = p thì p | a, ta có điều phải chứng minh. Nếu g = 1 Footer Page 20 of 161. 15