Luận văn Thạc sĩ Toán học: Biểu diễn số nguyên thành tổng hai bình phương của số nguyên

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:52

Thêm vào BST

Báo xấu

31
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn trình bày các kết quả của lý thuyết số về các tính chất đặc trưng của những số nguyên dương (nói riêng là các số nguyên tố) biểu diễn được dưới dạng tổng bình phương của hai số nguyên, số cách biểu diễn thành tổng hai bình phương, một số bài toán và định lý có liên quan tới bài toán tổng của hai số bình phương. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Biểu diễn số nguyên thành tổng hai bình phương của số nguyên

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐẶNG TUẤN LONG BIỂU DIỄN SỐ NGUYÊN THÀNH TỔNG HAI BÌNH PHƯƠNG CỦA SỐ NGUYÊN LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐẶNG TUẤN LONG BIỂU DIỄN SỐ NGUYÊN THÀNH TỔNG HAI BÌNH PHƯƠNG CỦA SỐ NGUYÊN LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. TRẦN VŨ THIỆU Thái Nguyên - 2016
i Mục lục Mở đầu 1 Chương 1. Kiến thức chuẩn bị 4 1.1 Ước chung lớn nhất . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Ước số và phần dư . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Số nguyên tố và hợp số . . . . . . . . . . . . . . . . . . . 5 1.2 Đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Số nguyên Gauss và vành Z[i] . . . . . . . . . . . . . . . . . . . 13 1.4 Bài toán áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Chương 2. Tổng bình phương của hai số nguyên 20 2.1 Bài toán tổng của hai số bình phương . . . . . . . . . . . . . . . 20 2.2 Số nguyên tố nào là tổng của hai bình phương? . . . . . . . . . 22 2.3 Số nguyên nào là tổng của hai bình phương? . . . . . . . . . . . 26 2.4 Số biểu diễn được thành tổng hai bình phương . . . . . . . . . . 30 2.5 Bài toán áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Chương 3. Một số bài toán có liên quan 38 3.1 Tổng của nhiều số bình phương . . . . . . . . . . . . . . . . . . 38 3.2 Bộ số Pythagoras và bài toán Fermat . . . . . . . . . . . . . . . 40 3.3 Một số bài toán chưa có lời giải . . . . . . . . . . . . . . . . . . 45 3.4 Bài toán áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Kết luận 48 Tài liệu tham khảo 49
1 Mở đầu Lý thuyết số nghiên cứu tập hợp số tự nhiên (các số nguyên dương) 1, 2, 3, 4, 5, 6, 7, . . . và các mối quan hệ giữa các loại số khác nhau. Người ta chia ra nhiều loại số nguyên: • số chẵn: 2, 4, 6, 8, 10, . . . • số lẻ: 1, 3, 5, 7, 9, 11, . . . • số chính phương: 1, 4, 9, 16, 25, 36, . . . • số lập phương: 1, 8, 27, 64, 125, . . . • số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, . . . • hợp số: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, . . . • 1 (modulo 4): 1, 5, 9, 13, 17, 21, 25, . . . • 3 (modulo 4): 3, 7, 11, 15, 19, 23, 27, . . . • số tam giác: 1, 3, 6, 10, 15, 21, 28, . . . • số hoàn hảo: 6, 28, 496, . . . • số Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . Một trong những mục tiêu chính của lý thuyết số là khám phá ra những quan hệ thú vị bất ngờ giữa các loại số khác nhau và chứng minh những quan hệ này là đúng. Có nhiều bài toán tiêu biểu về lý thuyết số, trong số đó một số đã có lời giải, một số cho tới nay vẫn chưa giải được.
2 Một số bài toán đã có lời giải: những số nào bằng tổng bình phương của hai số tự nhiên? Ví dụ, 5 = 12 + 22 , 13 = 22 + 32 , . . . Chúng có những đặc tính chung gì? Có bao nhiêu cách biểu diễn như thế? Bài toán tương tự: số nào bằng tổng lập phương của hai số nguyên dương? Ví dụ, 9 = 13 + 23 , 28 = 13 + 33 , 35 = 23 + 33 , . . . Đặc điểm của những số này là gì? Đề tài luận văn Biểu diễn số nguyên thành tổng hai bình phương của số nguyên có mục đích tìm hiểu và trình bày các kết quả của lý thuyết số về các tính chất đặc trưng của những số nguyên dương (nói riêng là các số nguyên tố) biểu diễn được dưới dạng tổng bình phương của hai số nguyên, số cách biểu diễn thành tổng hai bình phương, một số bài toán và định lý có liên quan tới bài toán tổng của hai số bình phương: bộ số Pythagoras, nghiệm nguyên của phương trình bậc hai với hệ số nguyên, định lý cơ bản của số học, định lý Fermat bé, định lý Wilson, định lý Thue, định lý hai số bình phương, ... Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo [1] - [6] lấy từ nguồn Internet và được chia thành ba chương. Chương 1 Kiến thức chuẩn bị trình bày lại các khái niệm về các số tự nhiên, số nguyên tố, hợp số, về phép chia hết, phép phân tích số nguyên ra thừa số nguyên tố, về phép tính đồng dư modulo. Chương 2 Tổng bình phương của hai số nguyên đề cập tới bài toán cổ điển trong lý thuyết số: biểu diễn một số nguyên dương (nói riêng, số nguyên tố) dưới dạng tổng hai bình phương của số nguyên. Trình bày các định lý về tính chất đặc trưng của các số nguyên tố, các số nguyên dương biểu diễn được dưới dạng tổng hai bình phương của số nguyên. Chương 3 Một số bài toán có liên quan đề cập tới bài toán mở rộng về biểu diễn số nguyên thành tổng của nhiều số bình phương (bài toán Waring), bộ số Pythagoras (x2 + y 2 = z 2 ) và Định lý lớn Fermat về sự không tồn tại nghiệm nguyên khác không của phương trình xn + y n = z n , với mọi n > 2. Cuối chương giới thiệu một số bài toán của lý thuyết số chưa có lời giải. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn
3 GS.TS. Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả cũng xin chân thành cảm ơn các thầy cô giáo của khoa Toán-Tin, Trường Đại học Khoa học Thái Nguyên và của Viện Toán học, Viện Công nghệ thông tin thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và tạo điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Thái Nguyên, tháng 5 năm 2016 Tác giả luận văn Đặng Tuấn Long
4 Chương 1 Kiến thức chuẩn bị Chương này nhắc lại một số khái niệm cơ bản của lý thuyết số: phần dư của phép chia nguyên, ước chung lớn nhất của các số nguyên, số nguyên tố và hợp số, khái niệm đồng dư và tính chất. Số nguyên Gauss và vành các số nguyên Gauss. Nội dung của chương được tham khảo từ các tài liệu [1], [2], [3] và [5]. 1.1 Ước chung lớn nhất 1.1.1 Ước số và phần dư Xét tập số nguyên Z = {0, ±1, ±2, ...}. Từ lý thuyết số, ta biết kết quả sau. Định lý 1.1 (Định lý chia). Với mọi a, b ∈ Z, b 6= 0, tồn tại duy nhất q, r ∈ Z, 0 ≤ r < |b|, sao cho a = bq + r. (Chia a cho b được q là thương số, r là phần dư). Ví dụ 1.2. a) Với a = 13, b = 3 ta có q = 4, r = 1, vì 13 = 3 × 4 + 1. b) Với a = 17, b = −5 ta có q = −3, r = 2, vì 17 = (−5) × (−3) + 2. c) Với a = −5, b = 4 ta có q = −2, r = 3, vì −5 = 4 × (−2) + 3. d) Với a = −11, b = −5 ta có q = 3, r = 4, vì −11 = (−5) × 3 + 4. Định nghĩa 1.3. Với a, b ∈ Z, ta nói a là ước (divisor) của b nếu tồn tại số nguyên x sao cho a.x = b. Trong trường hợp này ta nói rằng b chia hết (divisible) cho a hay b là bội (multiple) của a và viết a | b (đọc là a là ước của b). Trái lại, ta nói a không là ước của b và viết a - b.
5 Ví dụ 1.4. Các ước của 6 là −6, −3, −2, −1, 1, 2, 3 và 6. Ta chỉ ra điều này bằng cách viết −3 | 6, 2 | 6, 3 | 6, . . . Nhưng 4 không là ước của 6 nên ta viết 4 - 6. Định nghĩa 1.5. Với bất kỳ a ∈ Z, các điều sau đây luôn đúng: 1 | a, −1 | a, a | a, −a | a. Ta nói 1, −1, a và −a là các ước tầm thường (trivial divisors) của a; 1 và −1 gọi là đơn vị (units), mọi ước bất kỳ khác của a gọi là ước thực sự (proper divisors). Ví dụ 1.6. -3, -2, 2, 3 là các ước thực sự của 6. 1.1.2 Số nguyên tố và hợp số Định nghĩa 1.7. Số nguyên dương a > 1 được gọi là một số nguyên tố (prime) nếu a không có ước thực sự. Số nguyên dương a gọi là một hợp số (composite) nếu a có ước thực sự. Nếu a là số nguyên dương và các số nguyên tố p1 , p2 , p3 ..., pk thỏa mãn a = pα1 1 × pα2 2 × pα3 3 × ... × pαk k thì tích pα1 1 × pα2 2 × pα3 3 × ... × pαk k gọi là phân tích thừa số nguyên tố (prime factoriza- tion) của a. Ví dụ 1.8. Các số nguyên tố nhỏ hơn 40 là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Định lý 1.9 (Định lý cơ bản của số học). Mọi số a, a > 1, có phân tích thừa số nguyên tố duy nhất (không kể sự sai khác về thứ tự các thừa số). Ví dụ 1.10. 12 = 22 × 3; 18 = 2 × 32 ; 231 = 3 × 7 × 11. Định nghĩa 1.11. Cho a, b ∈ Z. Ta định nghĩa ước chung lớn nhất (greatest common divisor) của a và b là số nguyên lớn nhất d mà cả a và b đều chia hết cho d : d | a và d | b. Ước chung lớn nhất được ký hiệu là (a, b) = d hoặc gcd(a, b) = d. Trong luận văn này ta sẽ sử dụng gcd(a, b) để chỉ ước chung lớn nhất của a và b. Ví dụ 1.12. Hãy tìm ước chung lớn nhất của 8 và 12. Ta thấy các ước của 8 là ±1, ±2, ±4, ±8 và các ước của 12 là ±1, ±2, ±3, ±4, ±6, ±12. Từ đó, ước
6 chung của 8 và 12 là ±1, ±2, ±4. Vì thế, ước chung lớn nhất của 8 và 12 là 4 và ta viết gcd(8, 12) = 4. Có thể thấy gcd(6, −9) = 3, gcd(−15, 25) = 5 và gcd(−3, −7) = 1. Định nghĩa 1.13. Nếu ước chung lớn nhất gcd(a, b) = 1 thì ta nói hai số nguyên a và b là nguyên tố cùng nhau (relatively prime). Định lý 1.14. Nếu a, b ∈ Z và gcd(a, b) = d thì gcd(a/d, b/d) = 1. Chứng minh. Giả sử gcd(a/d, b/d) = k. Từ đó a/d = mk, b/d = nk với m, n nguyên và ta có a = mkd, b = nkd. Điều này cho thấy a và b chia hết cho kd, tức là kd | a và kd | b. Do d là ước chung lớn nhất của a và b nên kd ≤ d. Suy ra k ≤ 1. Do k nguyên dương nên phải có k = 1. Vậy gcd(a/d, b/d) = k = 1. Ví dụ 1.15. Hãy tìm ước chung lớn nhất của 15 và 40. Bằng cách phân tích ra thừa số nguyên tố ta có 15 = 3 × 5 và 40 = 23 × 5. Từ đó, ta tìm được ước chung lớn nhất của 15 và 40 bằng 5, tức là gcd(15, 40) = 5. Ta thấy gcd(15/5, 40/5) = gcd(3, 8) = 1. Định lý 1.16. Cho a, b, c ∈ Z. Khi đó gcd(a + cb, b) = gcd(a, b). Chứng minh. Giả sử gcd(a, b) = d, gcd(a + cb, b) = k. Ta cần chứng minh rằng d = k. Do gcd(a, b) = d nên a = pd và b = qd với p, q nguyên tố cùng nhau (Định lý 1.14). Trong gcd(a + cb, b) = k thay a = pd, b = qd và cb = cqd, ta được k = gcd(a + cb, b) = gcd(pd + cqd, qd) = gcd((p + cq)d, qd). Đẳng thức này cho thấy ước chung lớn nhất của (p + cq)d và qd bằng d, bởi vì (p + cq) có trong (p + cq)d đúng d lần và q có trong qd cũng d lần. Vì thế, gcd(a + cb, b) = d, nghĩa là d = k. Định lý được chứng minh. Ví dụ 1.17. Xét ba số: a = 110, b = 44, c = 22. Theo Định lý 1.16, ta có gcd(110 + 22 × 44, 44) = gcd(110, 44) hay gcd(1078, 44) = gcd(110, 44).
7 Để kiểm tra đẳng thức này, ta tính gcd(1078, 44) và gcd(110, 44). Ta thấy 44 = 22 × 11, 110 = 2 × 5 × 11 và 1078 = 2 × 72 × 11. Từ đó suy ra gcd(1078, 44) = gcd(110, 44) = 22. Kết quả kiểm tra đúng. Định nghĩa 1.18. Cho a, b ∈ Z . Tổ hợp tuyến tính (linear combination) của a và b là tổng có dạng ax + by, trong đó x, y ∈ Z. Định lý 1.19. Nếu a, b, m, n ∈ Z và c là ước số chung của a và b thì c cũng là ước số của ma + nb, nghĩa là c | a và c | b thì c | (ma + nb). Chứng minh. Nếu c | a và c | b thì theo định nghĩa của ước sẽ tìm được u, v ∈ Z sao cho a = cu, b = cv. Khi đó ma + nb = mcu + ncv = c(mu + nv). Do đó (ma + nb) là bội của c. Vì thế c | (ma + nb). Ví dụ 1.20. Giả sử a = 21, b = 39, và c = 3. Ta có 21 = 3 × 7 và 39 = 3 × 13. Vì thế, 21 và 39 chia hết cho 3. Giả sử m = 7, n = −3. Khi đó 7 × 21 − 3 × 39 = 147 − 117 = 30. Rõ ràng 3 là ước của 30, vì 30 = 3 × 10. Định lý 1.21. Cho hai số a, b ∈ Z. Khi đó d = gcd(a, b) là số nguyên dương nhỏ nhất biểu diễn được dưới dạng d = ax + by với x, y ∈ Z. Chứng minh. Giả sử k là số nguyên dương nhỏ nhất có dạng k = ax + by với x, y ∈ Z. Ta chứng minh d = k. Thật vậy, do d là ước chung của a và b nên theo Định lý 1.19, d cũng là ước của ax + by, tức là d | (ax + by) = k, do đó d ≤ k.a phải chia hết cho k, vì nếu trái lại thì a = ku + v với 0 < v < k, trong đó u, v ∈ Z. Từ đó v = a − ku = a − u(ax + by) = a(1 − ux) + b(−uy). Như vậy, v cũng là một tổ hợp tuyến tính của a và b. Thế nhưng v < k, điều này trái với giả thiết: k là số nguyên dương nhỏ nhất có dạng ax + by. Chứng minh tương tự cho thấy b cũng chia hết cho k. Vậy phải có k ≤ gcd(a, b) = d. Ở trên ta đã thấy d ≤ k. Vì thế, k = d. Ví dụ 1.22. Giả sử a = 51 và b = 187. Ta thấy 51 = 3 × 17 và 187 = 11 × 17. Từ đó gcd(51, 187) = 17. Nếu chọn x = 4, y = −1, ta có 51 × 4 − 187 × 1 = 204 − 187 = 17 = gcd(51, 187).
8 Định lý 1.23. Nếu a, b, c ∈ Z, a | bc và a, b nguyên tố cùng nhau thì a | c. Chứng minh. Do a, b nguyên tố cùng nhau nên gcd(a, b) = 1. Theo Định lý 1.21, tồn tại x, y ∈ Z sao cho 1 = ax + by. Nhân hai vế với c ta được c = acx + bcy. Rõ ràng a | ac và theo giả thiết a | bc. Từ đó theo Định lý 1.19, a | (acx + bcy) = c, tức là a | c. Định lý 1.24. Nếu a, b là các số nguyên dương thì tập hợp các tổ hợp tuyến tính của a và b là tập các bội nguyên của gcd(a, b). Chứng minh. Giả sử gcd(a, b) = c. Trước hết, ta chứng minh mỗi tổ hợp tuyến tính của a và b, chẳng hạn ma + nb, là một bội nguyên của c. Thật vậy, với gcd(a, b) = c thì c | a và c | b. Theo Định lý 1.19, c | (ma + nb), do đó ma + nb = ck, nghĩa là ma + nb là một bội nguyên của gcd(a, b). Ngược lại, theo Định lý 1.21, c = gcd(a, b) biểu diễn được dưới dạng một tổ hợp tuyến tính của a và b, chẳng hạn c = ax + by với x, y ∈ Z. Nhân cả hai vế với s ∈ Z, ta có sc = s(ax + by) = a(sx) + b(sy). Như vậy, mỗi bội nguyên của c là một tổ hợp tuyến tính của a và b. Ví dụ 1.25. Giả sử a = 52, b = 117. Ta thấy 52 = 22 × 13 và 117 = 32 × 13. Do đó gcd(52, 117) = 13. Với bất kỳ x, y ∈ Z tìm được số nguyên k nghiệm đúng phương trình 52x + 117y = 13k. Tìm x và y cho ta k = 2, tức là x, y thỏa mãn 52x + 117y = 13 × 2 = 26. Chia cả hai vế cho 13, phương trình rút gọn còn 4x + 9y = 2. Ta tìm được x = 5 và y = −2, vì 4 × 5 − 9 × 2 = 20 − 18 = 2. Định nghĩa 1.26. Một tập G được gọi là một nhóm cộng nếu tồn tại một ánh xạ từ tích Descartes G × G vào G (ảnh của phần tử (a, b) ∈ G × G qua ánh xạ này ta ký hiệu là a + b) thỏa mãn các tính chất sau: i) Kết hợp: a + (b + c) = (a + b) + c, với ∀a, b, c ∈ G. ii) Có phần tử không (ký hiệu là 0): Tồn tại phần tử 0 ∈ G sao cho a + 0 = 0 + a = a, với ∀a ∈ G. iii) Có phần tử đối: Với mỗi a ∈ G luôn tồn tại phần tử đối, ký hiệu là −a ∈ G, sao cho a + (−a) = (−a) + a = 0. Nếu a + b = b + a với a, b ∈ G thì G được gọi là nhóm Abel (hay nhóm giao hoán).
9 Định nghĩa 1.27. Một tập con H của nhóm cộng G được gọi là một nhóm con của G nếu các điều kiện sau được thỏa mãn: i) Phép toán cộng là đóng với H, tức là a + b ∈ H, với ∀a, b ∈ H. ii) H chứa phần tử không của G. iii) −a ∈ H với mọi a ∈ H. Rõ ràng, tập hợp tất cả các số nguyên Z là một nhóm Abel đối với phép toán cộng. Dưới đây ta có một kết quả thú vị cho nhóm này. Bổ đề 1.28. Cho S ⊆ Z là một nhóm con của Z với phép cộng. Khi đó, tồn tại d ∈ Z sao cho S = dZ, trong đó dZ = {dz : z ∈ Z} . Chứng minh. Vì S là nhóm con của Z nên ta biết rằng nếu cho trước a, b ∈ Z thì a + b ∈ Z. Bằng cách cộng lặp a với chính nó, ta được aZ ⊆ S. Chứng minh tiến hành theo hai trường hợp: a) S = {0}. Khi đó, chọn d = 0 thì S = 0Z = {0} . b) S 6= {0}. Giả sử d là số nguyên dương nhỏ nhất trong S. Ta biết rằng dZ ⊆ S. Để chứng minh S ⊆ dZ ta lấy s ∈ S. Ta sẽ chỉ ra d | s, do đó s ∈ dZ. Theo thuật toán chia ta biết rằng s = dq + r, trong đó 0 ≤ r ≤ d − 1. Lưu ý rằng do d ∈ S nên dq ∈ S và −s ∈ S. Do S đóng kín đối với phép cộng nên dq + (−s) = r ∈ S. Nhưng vì 0 ≤ r ≤ d − 1, S ⊆ Z và d là số nguyên dương nhỏ nhất trong S nên phải có r = 0. Do đó s = dq và d | s. 1.2 Đồng dư Định nghĩa 1.29. Cho a, b ∈ Z. Ta nói rằng a đồng dư với b (congruent to) theo modulo m (viết tắt là mod m) nếu m | (a − b). Ta ký hiệu là a ≡ b (mod m) và hiểu đơn giản là: khi chia a và b cho m ta được phần dư như nhau (đồng dư). Nhận xét 1.30. Lưu ý rằng ta có thể diễn đạt m | a bởi cách viết a ≡ 0 (mod m). Có thể chứng minh các tính chất sau:
10 • Với bất kỳ 1 < m ∈ Z và bất kỳ a ∈ Z ta có: 1. a ≡ a (mod m): Do m × 0 = 0 nên m | 0 = a − a. Từ đó a ≡ a (mod m); 2. Nếu a ≡ b (mod m) thì b ≡ a (mod m). Từ a ≡ b (mod m) ⇒ m | (a−b) ⇒ a − b = km, k ∈ Z ⇒ b − a = −km, −k ∈ Z ⇒ m | (b − a) ⇒ b ≡ a (mod m); 3. Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m). Thật vậy, a ≡ b (mod m) ⇒ m | (a − b) ⇒ a − b = um, u ∈ Z, b ≡ c (mod m) ⇒ m | (b − c) ⇒ b − c = vm, v ∈ Z ⇒ a − c = (a − b) + (b − c) = (u + v)m ⇒ m | (a − c) ⇒ a ≡ c (mod m). • Nếu a ≡ b (mod m) thì ta có: 1. a + c ≡ b + c (mod m): Từ a ≡ b (mod m) ⇒ m | (a − b) = (a + c) − (b + c) ⇒ a + c ≡ b + c (mod m); 2. ac ≡ bc (mod m): Từ a ≡ b (mod m) ⇒ m | (a − b) ⇒ m | c(a − b) = ac − bc ⇒ ac ≡ bc (mod m); • Nếu a ≡ b (mod m) và c ≡ d (mod m) thì ta có: 1. a + c ≡ b + d (mod m): Từ a ≡ b (mod m) ⇒ m | (a − b) ⇒ a − b = um, u ∈ Z. Từ c ≡ d (mod m) ⇒ m | (c − d) ⇒ c − d = vm, v ∈ Z. Từ đó (a − b) + (c − d) = (a + c) − (b + d) = (u + v)m ⇒ m | (a + c) − (b + d) ⇒ a + c ≡ b + d (mod m); 2. ac ≡ bd (mod m): Từ a ≡ b (mod m) ⇒ m | (a − b) ⇒ a − b = um, u ∈ Z ⇒ ac − bc = cum. Từ c ≡ d (mod m) ⇒ m | (c − d) ⇒ c − d = vm, v ∈ Z ⇒ bc − bd = bvm. Từ đó (ac − bc) + (bc − bd) = (ac − bd) = (cu + bv)m với (cu + bv) ∈ Z ⇒ m | (ac − bd) ⇒ ac ≡ bd (mod d). • Nếu ac ≡ bc (mod m) và c, m nguyên tố cùng nhau thì a ≡ b (mod d). Thật vậy, ac ≡ bc (mod m) ⇒ m | (ac − bc = c(a − b). Do m, c nguyên tố cùng nhau nên theo Định lý 1.23, m | (a − b) ⇒ a ≡ b (mod m).
11 Bây giờ ta có thể phân chia số nguyên thành các lớp dựa trên quan hệ đồng dư modulo m của chúng, với số nguyên m nào đó, m > 1, bằng cách đặt các số nguyên đồng dư với nhau vào cùng một lớp. Mỗi số nguyên chỉ được đặt vào một và chỉ một lớp như thế và bất kỳ cặp số nguyên x, y lấy ra từ cùng một lớp sẽ thỏa mãn x ≡ y (mod m). Các lớp này gọi là lớp thặng dư modulo m (residue classes), ký hiệu là am , trong đó a là một phần tử trong lớp đó. Một tập chứa đúng một phần tử của mỗi lớp thặng dư có thể được viết thành Z/mZ. Ví dụ khi m = 4, ta có thể viết Z/4Z = {0, 1, 2, 3}. Với một số phép toán, cụ thể là cộng, trừ, nhân và lũy thừa, thì một phần tử bất kỳ của lớp là đại diện cho cả lớp, nghĩa là thực hiện các phép toán này trên các phần tử đại diện của hai lớp sẽ cho kết quả là lớp thặng dư giống như áp dụng cho phần tử bất kỳ của mỗi lớp đó. Với các phép toán khác, ví dụ ước chung lớn nhất, thì không được. Ví dụ với lớp thặng dư 2 và 3 ∈ Z/4Z thì 2 + 3 là lớp 1, giống như 6 ≡ 2 (mod 4) cộng 11 ≡ 3 (mod 4) cho 17 ≡ 1 (mod 4). Nhận xét 1.31. Ta có thể tùy ý thay đổi giữa biểu thức đồng dư và biểu thức đại số của một số. Chẳng hạn, phát biểu "n có dạng 4k + 1" tương đương với cách nói rằng n ≡ 1 (mod 4). Trước khi trình bày tiếp một số kết quả về đồng dư, chúng tôi sẽ nhắc lại một số kiến thức về nhóm nhân, vành và trường. Tương tự với định nghĩa nhóm cộng, ta có định nghĩa nhóm nhân như sau. Định nghĩa 1.32. Một tập G được gọi là một nhóm nhân nếu tồn tại một ánh xạ từ tích Descartes G × G vào G (ảnh của phần tử (a, b) ∈ G × G qua ánh xạ này ta ký hiệu là ab) thỏa mãn các tính chất sau: i) Kết hợp: a(bc) = (ab)c, với ∀a, b, c ∈ G. ii) Có phần tử đơn vị (ký hiệu là e): Tồn tại phần tử e ∈ G sao cho ae = ea = a, với ∀a ∈ G. iii) Có phần tử nghịch đảo: Với mỗi a ∈ G luôn tồn tại phần tử nghịch đảo, ký hiệu là a−1 ∈ G, sao cho aa−1 = a−1 a = e. Nếu G thỏa mãn tính chất giao hoán đối với phép nhân, tức là ab = ba, với mọi a, b ∈ G ta cũng nói G là nhóm Abel đối với phép toán nhân.
12 Định nghĩa 1.33. (i) Một tập hợp R được gọi là một vành nếu trên R có hai phép toán cộng và nhân thỏa mãn các tính chất sau: • Tập R là một nhóm Abel đối với phép cộng. • Phép nhân trên R có tính chất kết hợp và có phần tử đơn vị. • Luật phân phối: Phép nhân là phân phối với phép cộng, tức là, với các phần tử a, b, c ∈ R tùy ý, ta có (a + b)c = ac + bc và c(a + b) = ca + cb. ii)Một vành R là vành giao hoán nếu phép nhân thỏa mãn điều kiện ab = ba, ∀a, b ∈ R. iii) Một phần tử khác không a ∈ R được gọi là một ước của không nếu tồn tại một phần tử khác không b ∈ R sao cho ab = ba = 0. iv) Một vành giao hoán không có ước của không được gọi là một miền nguyên. v) Một vành R được gọi là một trường nếu R là một vành giao hoán và mọi phần tử khác không của R đều có nghịch đảo. Định lý 1.34. Nếu m, n nguyên tố cùng nhau thì m có nghịch đảo trong phép nhân modulo n. Chứng minh. Do m, n nguyên tố cùng nhau nên gcd(m, n) = 1 = am + bn với a, b ∈ Z theo Định lý 1.21. Xét phương trình đồng dư (modulo n): 1 ≡ am + bn (mod n) ⇒ 1 ≡ am + 0 ≡ am (mod n). Do đó m có nghịch đảo trong phép nhân modulo n. Với p nguyên tố thì Fp = Z/pZ là một trường, nghĩa là các số nguyên có phần dư khác 0 khi chia cho p, sẽ tạo thành một nhóm nhân Fp∗ (với Fp∗ = Fp \{0}). Các tính chất căn bản của những cấu trúc đại số này giúp ích cho mục tiêu của ta là: • Do Fp∗ = {1, 2, ....p − 1} là một nhóm nhân, nên với mỗi a ∈ Fp∗ tồn tại đúng một a−1 ∈ Fp∗ sao cho a × a−1 ≡ 1 (mod p). • Với a ∈ Fp∗ khi và chỉ khi a ≡ 1 (mod p) hoặc a ≡ p − 1 (mod p). Chứng minh của sự kiện này như sau.
13 Trước tiên giả sử rằng a2 ≡ 1 (mod p). Khi đó, p | (a2 − 1) = (a + 1)(a − 1). Bây giờ do p nguyên tố nên p | (a + 1) hoặc p | (a − 1). Nếu p | (a + 1) thì do a ∈ Fp∗ nên a ≡ p − 1 (mod p). Nếu p | (a − 1) thì a ≡ 1 (mod p). Bây giờ giả sử rằng a ≡ 1 (mod p). Khi đó, a = kp + 1 với k ∈ Z. Suy ra a2 = k 2 p2 + 2kp + 1 ⇒ a2 ≡ 1 (mod p). Còn nếu a ≡ p − 1 (mod p) thì a + 1 = kp với k ∈ Z thì ⇒ a2 = k 2 p2 − 2kp + 1 ⇒ a2 ≡ 1 (mod p). 1.3 Số nguyên Gauss và vành Z[i] Số nguyên Gauss là một số phức với phần thực và phần ảo của nó đều là các số nguyên. Với phép cộng và phép nhân thông thường của số phức, các số nguyên Gauss tạo ra một miền nguyên, thường được ký hiệu là Z[i] (i2 = −1). Về hình thức, tập các số nguyên Gauss là Z[i] = {a + bi | a, b ∈ Z} . Với α = a + bi trong Z[i], ta đặt chuẩn của α là số nguyên không âm N (α) = a2 + b2 . Chuẩn này là một hàm nhân tính, nghĩa là N (αβ) = N (α)N (β). Thật vậy, giả sử α = a + bi, β = a0 + b0 i, Khi đó αβ = (aa0 − bb0 ) + (ab0 + a0 b)i. Do đó, N (αβ) = (aa0 − bb0 )2 + (ab0 + a0 b)2 = (a2 + b2 )(a02 + b02 ) = N (α)N (β). Chuẩn N biểu thị số đo cho kích thước của các phần tử. Với số nguyên a ∈ Z thì N (a) = a2 . Nói riêng, N (1) = 1. Định nghĩa đơn vị trong Z[i] là các phần tử α có chuẩn bằng 1, tức là N (α) = a2 + b2 = 1. Do vậy, a = ±1, b = 0 hoặc a = 0, b = ±1. Nội dung này được phát biểu cụ thể trong định lý sau. Định lý 1.35. Đơn vị trong Z[i] là các số 1, −1, i và −i. Chứng minh. Vì 1.1 = 1, (−1)(−1) = 1 và i(−i) = 1 nên bốn phần tử này đều là các phần tử đơn vị trong Z[i]. Ngược lại, nếu u là một đơn vị trong Z[i]
14 thì uv = 1 với v nào đó trong Z[i]. Lấy chuẩn hai vế ta được N (u)N (v) = 1. Phương trình này gồm các số nguyên dương nên cả N (u) và N (v) phải bằng 1. Bằng cách viết u = a + bi, ta sẽ có a2 + b2 = 1. Nghiệm nguyên của phương trình này chỉ có thể là (a, b) = (1, 0); (−1, 0); (0, 1) và (0, −1). Chúng tạo ra bốn số nguyên Gauss 1, −1, i và −i. Cách viết chung các đơn vị trong Z[i] là ik , k = 0, 1, 2, 3 (lần lượt tương ứng với 1, i, −1 và −i). Tương tự như Z, ta cũng có định lý chia trong Z[i]. Để đo kích thước của phần dư trong phép chia, ta dùng khái niệm chuẩn và có định lý sau. Định lý 1.36. Với bất kỳ α và β 6= 0 trong Z[i] tồn tại các số γ, ρ thỏa mãn α = βγ + ρ, N (ρ) ≤ N (β)/2 < N (β). Chứng minh. Chuẩn trên Z[i] có liên hệ chặt chẽ với mô đun trên C: N (a + bi) = |a + bi|2 . Mô đun trên C là cách để ta đo khoảng cách trong C và ta sẽ tận dụng khái niệm này. Trong C khoảng cách xa nhất từ một số phức tới một phần tử trong √ Z[i] là 1/ 2 , bởi vì tâm của các hình vuông 1 × 1 với bốn đỉnh trong Z[i] sẽ có √ khoảng cách tới các đỉnh này bằng 1/ 2. Bây giờ ta xem tỉ số α/β như một số phức và đặt nó vào hình vuông 1 × 1 với bốn đỉnh trong Z[i]. Giả sử γ ∈ Z[i] √ là đỉnh của hình vuông gần α/β nhất, do đó |α/β − γ| ≤ 1/ 2. Nhân với |β| √ ta được |α − β.γ| ≤ (1/ 2).|β|. Bình phương hai vế và gọi bình phương mô đun của số phức trên Z[i] là chuẩn, ta nhận được N (α − βγ) ≤ N (β)/2 < N (β). Bây giờ đặt ρ = α − β.γ, ta có N (ρ) ≤ N (β)/2 < N (β). Nhận xét 1.37. Khác với trường hợp trong Z, thương và phần dư trong Z[i] không duy nhất. Chẳng hạn, chọn α= 37 + 2i và β = 11 + 2i. Có thể dễ dàng kiểm tra thấy rằng α = β.3 + (4 − 4i) và và α = β.(3 − i) + (2 + 7i).
15 Ở đây cả thương và phần dư có chuẩn nhỏ hơn N (β) = 125 (đúng ra, nhỏ hơn 125/2). Chứng minh của Định lý 1.36 giải thích hình học vì sao thương và phần dư trong Z[i] không duy nhất: α/β gần hai đỉnh của hình vuông 1 × 1 chứa nó hơn so với độ dài nửa đường chéo của hình vuông đó. Sự thiếu tính duy nhất này của thương và phần dư không phải là điểm yếu chủ chốt, vì hệ quả chính của định lý chia, chẳng hạn thuật toán Euclid và phân tích ra thừa số duy nhất, trên thực tế không sử dụng tới tính duy nhất. Điều quan trọng chính là ở chỗ phần dư nhỏ hơn (theo một nghĩa nào đó) số chia và đó mới là điều Định lý 1.36 muốn nêu ra. Hệ quả 1.38. Vành Z[i] có phân tích thừa số duy nhất. Số nguyên tố trong Z[i] được hiểu là số Gauss không có ước khác đơn vị và chính nó. Sau đây là một vài ví dụ về số nguyên tố Gauss trong Z[i] (Hình 1.1): 1 + i, 3, 1 + 2i, 1 − 2i, 7, 11, 2 + 3i, 2 − 3i. Hình 1.1: Minh họa số nguyên tố Gauss trong Z[i] Lưu ý rằng 2 và 5 không có mặt trong danh sách này, bởi vì chúng không là số nguyên tố trong Z[i]: 2 = (1 + i)(1 − i); 5 = (2 + i)(2 − i).
16 1.4 Bài toán áp dụng Bài toán 1.39. Chứng minh rằng nếu 2n − 1 là một số nguyên tố thì n cũng là số nguyên tố (nhưng ngược lại, lại không đúng, bởi vì có thể kiểm tra 89 | (211 − 1)). Lời giải. Khi m là số lẻ ta có phân tích đa thức ra thừa số xm − 1 = (x − 1)(xm−1 + xm−2 + ... + x + 1). Giả sử n không là số nguyên tố, nghĩa là n = m × k với k là một số nguyên nào đó, m > 1. Thay thế x = 2k vào đồng nhất thức ở trên, ta nhận được 2n − 1 = 2mk − 1 = (2k − 1)(2k(m−1) + 2k(m−2) + ... + 2k + 1). Do đó 2k − 1 là một ước của 2n − 1. Còn phải chỉ ra rằng đó không phải là một ước tầm thường, nghĩa là 1 < 2k − 1 < 2n − 1. Như thế 2n − 1 không là số nguyên tố, ta gặp mâu thuẫn. Vì vậy n không thể là một hợp số. Bài toán 1.40. Chứng minh rằng nếu 2n + 1 là một số nguyên tố thì n = 2k , k ≥ 0 (Fermat đã nghĩ rằng điều ngược lại cũng đúng. Nhưng Euler đã bác 5 bỏ điều này bằng cách chỉ ra rằng 641 | (22 + 1) = 232 + 1). Lời giải. Khi m là số lẻ ta có phân tích đa thức ra thừa số xm + 1 = (x + 1)(xm−1 − xm−2 + ... − x + 1). Giả sử n không phải là số bình phương của 2, nghĩa là n có một ước lẻ m > 1. Giả sử n = m × k. Thay thế x = 2k vào đồng nhất thức ở trên, ta nhận được 2n + 1 = (2mk + 1 = (2k + 1)(2k(m−1) − 2k(m−2) + ... − 2k + 1). Do đó 2k + 1 là ước của 2n + 1. Còn phải chỉ ra rằng đó không phải là một ước tầm thường, nghĩa là 1 < 2k + 1 < 2n + 1. Như thế 2n + 1 không là số nguyên tố, ta gặp mâu thuẫn. Vậy n không thể chứa ước nào là số lẻ lớn hơn 1. Bài toán 1.41. Chứng minh rằng có vô số các số nguyên tố p sao cho p + 2 không phải là một số nguyên tố.
17 Lời giải. Giả sử p + 2 là hợp số với chỉ một số hữu hạn số nguyên tố p. Khi đó, có số p0 sao cho p nguyên tố và p > p0 kéo theo p + 2 nguyên tố. Chọn một số nguyên tố p > p0 . Khi đó, hệ quả là mọi số lẻ lớn hơn p đều là số nguyên tố. Điều này là không thể, bởi vì, chẳng hạn mọi lũy thừa bậc k ≥ 2 của 3 là hợp số. Ta gặp mâu thuẫn. Bài toán 1.42. [Russia 2001] Tìm tất cả các số nguyên tố p và q sao cho p + q = (p − q)3 . Lời giải. Có duy nhất cặp số nguyên tố như vậy là p = 5 và q = 3. Thật vậy, vì (p − q)3 = p + q 6= 0, p và q là các số phân biệt và do đó nguyên tố cùng nhau. Vì p − q ≡ 2p (mod (p + q)), chia modulo phương trình cho p + q thu được 0 ≡ 8p3 (mod (p − q)). Do p và q nguyên tố cùng nhau, nên p và p + q cũng là nguyên tố cùng nhau. Cho nên, 0 ≡ 8 (mod (p + q)); tức là p + q là ước của 8. Tương tự, chia modulo phương trình cho p − q được 2p ≡ 0 (mod (p − q)). Do p và q nguyên tố cùng nhau nên p và p − q nguyên tố cùng nhau. Ta kết luận rằng 2 ≡ 0 (mod (p − q)), hay p − q là ước của 2. Kết hợp hai điều kiện suy ra (p, q) = (3, 5) hoặc (5, 3); thay lại chỉ có (5, 3) thỏa mãn bài toán. Bài toán 1.43. [Baltic 2001] Cho a là một số nguyên lẻ. Chứng minh rằng n n m m a2 + 22 và a2 + 22 nguyên tố cùng nhau với mọi số nguyên dương n và m sao cho n 6= m. Lời giải. Không giảm tính tổng quát, giả sử m > n. Với bất kỳ số nguyên tố n n p là ước của a2 + 22 , ta có n n a2 ≡ −22 (mod p). Lấy bình phương hai vế phương trình trên m − n lần thu được m m a2 ≡ 22 (mod p). m m m Bởi vì a lẻ, ta có p 6= 2. Do đó, 22 + 22 = 22 +1 6= 0 (mod p), cho nên m m m a2 ≡ 22 6≡ −22 (mod p).