Xemtailieu Tải về Định lý fermat
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ************* LÊ NHƯ QUỲNH ĐỊNH LÝ FERMAT KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Đại số Hà Nội – Năm 2016 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ************* LÊ NHƯ QUỲNH ĐỊNH LÝ FERMAT KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Đại số NGƯỜI HƯỚNG DẪN KHOA HỌC Ths. DƯƠNG THỊ LUYẾN Hà Nội – Năm 2016 LỜI CẢM ƠN Sau một thời gian nghiên cứu cùng với sự hướng dẫn và chỉ bảo tận tình cuả cô giáo, Thạc sĩ Dương Thị Luyến, khóa luận của em đến nay đã hoàn thành. Qua đây em xin bày tỏ lòng biết ơn sâu sắc của mình tới cô Dương Thị Luyến, người đã trực tiếp hướng dẫn chỉ bảo cho em nhiều kinh nghiệm quí báu trong thời gian em thực hiện khóa luận này. Em cũng xin chân thành cảm ơn sự giúp đỡ của các thầy cô 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 cho em trong thời gian em làm khóa luận. Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện khóa luận này. Hà Nội, tháng 05 năm 2016 Sinh viên Lê Như Quỳnh LỜI CAM ĐOAN Tôi khẳng định rằng đây là công trình nghiên cứu của riêng tôi, do chính tôi nghiên cứu và hoàn thành trên cơ sở những kiến thức đã học và tài liệu tham khảo. Nó không trùng kết quả với bất cứ người nào khác. Hà Nội, tháng 05 năm 2015 Sinh viên Lê Như Quỳnh Mục lục Lời nói đầu 1 1 Lịch sử định lý Fermat 2 1.1 Lịch sử định lý nhỏ Fermat . . . . . . . . . . . . . . . . 2 1.2 Sự ra đời định lý lớn Fermat . . . . . . . . . . . . . . . . 3 2 Chứng minh định lý Fermat 2.1 Chứng minh định lý nhỏ Fermat . . . . . . . . . . . . . . 5 2.1.1 Kiến thức có liên quan . . . . . . . . . . . . . . . 5 2.1.2 Chứng minh định lý nhỏ Fermat thông qua định lý Euler . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.3 Chứng minh trực tiếp định lý nhỏ Fermat . . . . 8 2.1.4 Chứng minh định lý nhỏ Fermat bằng quy nạp theo a . . . . . . . . . . . . . . . . . . . . . . . . 2.1.5 2.1.6 9 Chứng minh định lý nhỏ Fermat dựa vào số nguyên tố 2.2 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Chứng minh định lý nhỏ Fermat dựa vào định lý Lagrange . . . . . . . . . . . . . . . . . . . . . . . 12 Định lý lớn Fermat . . . . . . . . . . . . . . . . . . . . . 13 ii Khóa luận tốt nghiệp Đại học Lê Như Quỳnh 2.2.1 Lịch sử về chứng minh định lý lớn Fermat . . . . 13 2.2.2 Các bộ số Pythagore . . . . . . . . . . . . . . . . 17 2.2.3 Định lý lớn Fermat . . . . . . . . . . . . . . . . . 21 3 Ứng dụng định lý Fermat vào giải toán 26 3.1 Các bài toán về tính chia hết . . . . . . . . . . . . . . . 26 3.2 Tìm dư trong một phép chia . . . . . . . . . . . . . . . . 34 3.3 Các bài toán về số nguyên tố . . . . . . . . . . . . . . . 37 3.4 Giải phương trình nghiệm nguyên . . . . . . . . . . . . . 42 Kết luận 50 Tài liệu tham khảo 51 iii Khóa luận tốt nghiệp Đại học Lê Như Quỳnh Lời nói đầu I.Lí do chọn đề tài Trong lịch sử toán học, bài toán về định lý Fermat là một trong những bài toán khó nhất khi nó đã tồn tại gần 400 năm và thách thức tất cả nỗ lực của những bộ óc thiên tài nhất. Dù cuối cùng nó đã được giải đáp vào thập niên 90 của thế kỉ XX, nhưng đến nay nó vẫn là vấn đề mở trong toán học. Do đó, tìm hiểu lịch sử ra đời và phương pháp chứng minh các định lý Fermat, một vài ứng dụng của nó vào các bài toán số học vẫn là vấn đề bổ ích. Với sự yêu thích và hướng dấn tận tình của Giảng viên THS. Dương Thị Luyến đã giúp em mạnh dạn chọn đề tài “Định lý Fermat”. II. Mục đích nghiên cứu Tìm hiểu sự ra đời và phương pháp chứng minh các định lý Fermat, một vài ứng dụng của nó vào các bài toán số học. Qua đó chúng ta thấy được tầm quan trọng của định lý Fermat. III. Đối tượng nghiên cứu - Định lý nhỏ Fermat. - Định lý lớn Fermat. IV. Ý nghĩa khoa học và thực tiễn - Nghiên cứu sự ra đời của hai định lý Fermat. - Chứng minh định lý nhỏ Fermat. - Ứng dụng định lý Fermat. 1 Chương 1 Lịch sử định lý Fermat 1.1 Lịch sử định lý nhỏ Fermat Fermat lần đầu thông báo định lý trong một bức thư đề ngày 18 tháng 10 năm 1640 cho bạn ông là Frenicle Fermat đã trình bày một kết quả sau đây - Nếu p là số nguyên tố và a là số nguyên sao cho (a, p) = 1 thì p sẽ là ước của số ap−1 − 1. - Nếu p là số nguyên tố và a là số nguyên thì p sẽ là ước của số ap −a. Fermat không chứng minh khẳng định của ông. Mặc dù có lẽ là nó đã được chứng minh, bằng chứng đầu tiên được xuất bản bởi Euler năm 1749. Kết quả về sau được gọi là “Định lý nhỏ Fermat”. Thuật ngữ “Định lý nhỏ Fermat” lần đầu tiên được sử dụng vào năm 1913 trong sách giáo khoa tiếng Đức của Hensel. Nguyên văn bản viết tay của Fermat hiện đang được lưu giữ tại Derpartmental Archiver of Haute- Garonne, Toulouse. 2 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh Đây là một trong những định lý cơ sở và đẹp nhất của số học. [8] 1.2 Sự ra đời định lý lớn Fermat Năm 1670, Cleman Samuel con trai trưởng của Fermat cho xuất bản quyển “Số học Diophant với những ghi chú của Fermat”. Quyển sách của Cleman Samuel vừa ra đời đã mang đến cho giới toán học lúc bấy giờ những bất ngờ, những thích thú và lẫn những cơn sốc. Nó tô điểm cho toán học bằng 48 ghi chú của Fermat trên quyển số học của ông. Tất cả những ghi chú này Fermat đều gọi là định lý. Bởi vì theo ông viết, ông đã chứng minh cụ thể cho từng định lý. Các nhà toán học bắt đầu cuộc đua “chứng minh lại các định lý của Fermat”. Sau đó, người ta chứng minh được hầu hết các định lý của Fermat. Duy nhất có một định lý nhìn qua tưởng chừng đơn giản, nhưng lại rất “ngoan cố” trước những nỗ lực của các nhà toán học ròng rã mấy thế kỷ liền. Định lý này người ta gọi là “Định lý lớn Fermat”, Định lý lớn Fermat là định lý cần chứng minh cuối cùng nên còn được gọi là “Định lý cuối cùng của Fermat”. Năm 1637, Fermat viết bên lề quyển sách số học cạnh bài toán “Tìm số nguyên dương x, y, z thỏa mãn x2 + y 2 = z 2 ” như sau: “Phương trình xn + y n = z n , với n ≥ 3 không có nghiệm nguyên dương. Tôi đã tìm ra phương pháp chứng minh, nhưng vì lề sách quá hẹp không đủ chỗ nên không trình bầy ở đây.”. Đây chính là định lý Fermat vĩ đại. Và phải mất 358 năm năm sau, với nỗ lực không ngừng của các nhà toán học qua bao nhiêu đắng cay, thất bại người ta mới tìm ra lời giải cho định 3 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh lý này. Vẻ đẹp của định lý ở chỗ nó là bài toán vô cùng khó nhưng lại được biểu diễn một cách đến nỗi ai cũng có thể hiểu được. [9] 4 Chương 2 Chứng minh định lý Fermat 2.1 2.1.1 Chứng minh định lý nhỏ Fermat Kiến thức có liên quan Một số khái niệm • Tập thương của tập hợp các số nguyên Z 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 và kí hiệu là Zm . • Mỗi phần tử A ∈ Zm được gọi là một lớp thặng dư môđun m, với a thuộc A ta kí hiệu A = a (mod m), a được gọi là một thặng dư môđun m. Tập hợp Zm gồm m phần tử. • Trong tập hợp các lớp thặng dư Zm ta xác định hai phép toán như sau a+b=a+b a.b = a.b, trong đó a, b ∈ Zm . 5 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh • Tập hợp Zm các lớp thặng dư môđun m cùng với phép cộng và nhân xác định như trên là một vành giao hoán có đơn vị. • Phần tử khả nghịch của vành Zm Phần tử a (mod m) của vành Zm gọi là một phần tử khả nghịch nếu như có b ∈ Zm sao cho a.b = 1. Tập hợp các phần tử khả nghịch của Zm được kí hiệu bởi Z∗m và (Z∗m , .) lập thành một nhóm với phép nhân của vành Zm . • Tính chất của các phần tử khả nghịch Giả sử A, B là những lớp thặng dư của vành Zm và A là phần tử khả nghịch, khi đó - Nếu X chạy qua khắp các phần tử của Zm thì AX + B cũng vậy, nghĩa là {AX + B/X ∈ Zm } = Zm . - Nếu X chạy qua khắp các phần tử của Z∗m thì AX cũng vậy, nghĩa là {AX/X ∈ Z∗m } = Z∗m . • Định nghĩa Phi-hàm Euler Giả sử m là số nguyên dương. Phi-hàm Euler được định nghĩa là số các số nguyên dương không vượt quá m và nguyên tố với m. Kí hiệu Phi-hàm Euler ϕ(m). • Công thức tính ϕ(m) - Phân tích m ra thừa số nguyên tố m = pα1 1 pα2 2 ...pαk k với pi là số các số nguyên tố; αi ∈ N∗ , i = 1, 2, ..., k. Ta có 1 1 1 ϕ(m) = m 1 − 1− ... 1 − . p1 p2 pk 6 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh Ví dụ: ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4. Ta có kết quả sau Với số nguyên tố p ta có ϕ(p) = p − 1. Ngược lại, nếu p là số nguyên dương sao cho ϕ(p) = p − 1, thì p là số nguyên tố. 2.1.2 Chứng minh định lý nhỏ Fermat thông qua định lý Euler Định lý nhỏ Fermat 1) Cho p là số nguyên tố và a là số nguyên sao cho (a, p) = 1. Khi đó ap−1 ≡ 1 (mod p). 2) Cho p là số nguyên tố, a ∈ Z tùy ý . Khi đó ap ≡ a (mod p). Chứng minh định lý Trước tiên ta đi chứng minh định lý Euler - Định lý Euler Giả sử m là số nguyên dương và a là số nguyên với (a, m) = 1. Khi đó aϕ(m) ≡ 1 (mod m) Chứng minh Ta gọi X1 , X2 , . . . , Xϕ(m) là phần tử khả nghịch của Zm tức là ta có lớp thặng dư A = ā (mod m) là phần tử khả nghịch của vành Zm khi và chỉ khi A là lớp nguyên tố với môđun m. Do (a, m) = 1 nên ā ∈ Z∗m . Theo tính chất của phần tử khả nghịch thì āX1 , āX2 , ..., āXϕ(m) cũng là các phần tử khả nghịch của Zm , hay ∗ Zm = {āX1 , āX2 , ..., āXϕ(m) }. 7 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh ∗ Nhân tất cả các phần tử của Zm theo hai cách biểu diễn ta được āX1 .āX2 .....āXϕ(m) = X1 .X2 . . . . .Xϕ(m) ⇒ (ā)ϕ(m) X1 .X2 . . . . .Xϕ(m) = X1 .X2 . . . . .Xϕ(m) ⇒ (ā)ϕ(m) = 1̄ ⇒ aϕ(m) ≡ 1 (mod m). Chứng minh định lý nhỏ Fermat 1) Theo giả thiết ta có p là số nguyên tố nên ta có ϕ(p) = p − 1. Mặt khác (a, p) = 1 suy ra theo định lý Euler ta được ap−1 ≡ 1 (mod p). 2) - Nếu a chia hết cho p thì hiển nhiên ap ≡ a (mod p). - Nếu a không chia hết cho p thì theo 1) ta có ap−1 ≡ 1 (mod p). Nhân cả hai vế của đồng dư thức trên với a ta được ap ≡ a (mod p). 2.1.3 Chứng minh trực tiếp định lý nhỏ Fermat 1) Do (a, p) = 1 ⇒ a không chia hết cho p. Vì thế các số a, 2a, 3a, . . . , (p − 1)a cũng không chia hết cho p. Giả sử các số a, 2a, 3a, . . . , (p − 1)a chia cho p được các số dư là r1 , r2 , . . . , rp−1 . Ta chứng minh ri 6= rj , ∀i 6= j (1 ≤ i, j ≤ p − 1). Thật vậy, nếu trái lại, thì tồn tại i 6= j (1 ≤ i, j ≤ p − 1) mà ri = rj . Do ia ≡ ri (mod p); ja ≡ rj (mod p), . mà ri = rj nên suy ra ia ≡ ja (mod p), do đó a(i − j).. p. . Do 0 < |i − j| < p ⇒ (i − j, p) = 1 ⇒ a.. p. Đó là điều vô lý (Vì a không chia hết cho p). Nhận xét được chứng minh. 8 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh Vì thế r1 r2 ...rp−1 = (p − 1)! ⇒ a.2a.3a . . . (p − 1)a ≡ r1 r2 ...rp−1 (mod p) ⇒ (p − 1)!ap−1 ≡ (p − 1)! (mod p) ⇒ ap−1 ≡ 1 (mod p). 2) Được chứng minh như 2.1.2. 2.1.4 Chứng minh định lý nhỏ Fermat bằng quy nạp theo a Trước tiên ta đi chứng minh 2). . Ta cần chứng minh (ap − a).. p với a nguyên dương, (a nguyên < 0 suy ra từ a nguyên > 0 bằng cách đặt a = −b, khi đó b nguyên dương). . Khi a = 0 hoặc a = 1 thì ap − a = 0 và hiển nhiên 0.. p. Giả sử mệnh đề đã đúng đến a = k, tức là ta có . k p − k .. p (1) Xét khi a = k + 1, ta có (theo công thức của nhị thức Newton) (k + 1)p − (k + 1) = k p + pk p−1 + Cp2 k p−2 + . . . + pk + 1 − k − 1 p = (k − k) + pk p−1 + Cp2 k p−2 + ... + Cpp−2 k 2 Để ý rằng Cpn = p(p − 1)(p − 2) . . . (p − n + 1) .. . p với n < p. 1.2 . . . n Vì thế từ (2) (và kết hợp với (1)), suy ra . [(k + 1)p − (k + 1)] .. p. Vậy 2) đúng với a = k + 1 9 . + pk (2) Khóa luận tốt nghiệp Đại học Lê Như Quỳnh Theo nguyên lý quy nạp suy ra đpcm. Ngược lại từ 2) ta có thể suy ra 1), thật vậy từ ap ≡ a(mod p) và (a, p) = 1 nên bằng cách chia hai vế của đồng dư thức cho a ta được ap−1 ≡ 1 (mod p). 2.1.5 Chứng minh định lý nhỏ Fermat dựa vào số nguyên tố Trước tiên ta đi chứng minh một số bổ để sau . Bổ đề 1. p là số nguyên tố khi và chỉ khi Cpk .. p, ∀k = 1, 2, . . . , p − 1. Chứng minh ⇒) Giả sử p là số nguyên tố, khi đó (k, p) = 1 với k = 1, 2, . . . , p − 1. p(p − 1)(p − 2) . . . (p − k + 1) . Ta có Cpk = ∈ Z ⇒ Cpk .. p. 1.2 . . . k k .. ⇐) Giả sử Cp . p, ∀k = 1, 2, . . . , p − 1 Ta chứng minh p là số nguyên tố nếu p không là số nguyên tố thì p có ước nguyên tố q < p. Khi đó Cpq = p(p − 1)(p − 2) . . . (p − q + 1) .. .p 1.2 . . . q . ⇒ (p − 1)(p − 2) . . . (p − q + 1).. q! ⇒ q |(p − 1)(p − 2) . . . (p − q + 1) Suy ra q|(p − i) vì 1 ≤ i ≤ q − 1 hay q|i, vô lý. Vậy p là số nguyên tố. Bổ đề 2. Nếu p là số nguyên tố, k1 , k2 , . . . , kn là n số tự nhiên. Khi đó (k1 + k2 + . . . + kn )p ≡ k1p + k2p + . . . + knp (mod p). Chứng minh 10 (∗) Khóa luận tốt nghiệp Đại học Lê Như Quỳnh Ta chứng minh bằng quy nạp theo n. Với n = 1 hiển nhiên. Với n = 2 ta có (k1 + k2 )p = k1p + Cp1 k1p−1 k2 + . . . + Cpp−1 k1 k2p−1 + k2p . . Theo bổ đề 1 ta có Cpk .. p, ∀k = 1, 2, . . . , p − 1 suy ra (k1 + k2 )p ≡ k1p + k2p (mod p). Giả sử ta có (k1 + k2 + . . . + kn )p ≡ k1p + k2p + . . . + knp (mod p), khi đó (k1 + k2 + . . . + kn + kn+1 )p = [(k1 + k2 + . . . + kn ) + kn+1 ]p p ≡ (k1 + k2 + . . . + kn )p + kn+1 (mod p) p ≡ k1p + k2p + . . . + knp + kn+1 (mod p) Vậy (*) đúng với mọi n. Chứng minh định lý nhỏ Fermat Trước tiên ta đi chứng minh 2). Ta cần chứng minh ap ≡ a (mod p) với mọi a nguyên dương,(a nguyên < 0 suy ra từ a nguyên > 0 bằng cách đặt a = −b, khi đó b nguyên dương). Áp dụng bổ đề 2 với k1 = k2 = . . . = ka = 1 ta được 11 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh ap = (1 + 1 + . . . + 1)p ⇒ ap ≡ 1p + 1p + . . . + 1p (mod p). ⇒ ap ≡ a (mod p) Từ 2) ta có thể suy ra 1). Thật vậy từ ap ≡ a (mod p) và (a, p) = 1 nên bằng cách chia hai vế của đồng dư thức cho a ta được ap−1 ≡ 1 (mod p). 2.1.6 Chứng minh định lý nhỏ Fermat dựa vào định lý Lagrange Định lý Lagrange Cấp của một nhóm X hữu hạn là bội của cấp của mọi nhóm con của nó. Chứng minh định lý nhỏ Fermat Xét nhóm cộng các lớp thặng dư theo môđun p, với p là một số nguyên tố Zp = {0̄,1̄, . . . , p − 1}. Tập hợp, Z∗p = {1̄, . . . , p − 1} là một nhóm với phép nhân, có cấp là p − 1. Dó đó mọi phần tử của Z∗p có cấp là ước của p − 1. Giả sử a ∈ Z là một số nguyên tùy ý. . Nếu a.. p thì ta có a ≡ 0 (mod p) và ap ≡ 0 (mod p), 12 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh từ đây ta có ap ≡ a (mod p). Nếu a không chia hết cho p thì ā ∈ Z∗p do đó ap−1 = 1̄ suy ra ap−1 ≡ 1 (mod p) hay ap ≡ a (mod p). 2.2 Định lý lớn Fermat 2.2.1 Lịch sử về chứng minh định lý lớn Fermat Định lý lớn Fermat được phát biểu như sau: “Phương trình xn + y n = z n , với n ≥ 3 không có nghiệm nguyên dương.”. Fermat viết bên lề cuốn sách “Số học” của Diophante là ông đã tìm ra cách chứng minh kỳ diệu của định lý. Nhưng trong các tài tài liệu của Fermat để lại, chỉ tìm thấy chứng minh của định lý với n = 4 được con trai của Fermat công bố sau khi Fermat qua đời. Để chứng minh x4 + y 4 = z 4 không có nghiệm nguyên dương, Fermat đã phát minh ra phương pháp “đại lượng giảm dần”. Sau đấy, bằng phương pháp này Euler đã chứng minh được Định lý Fermat với n = 3. 70 năm sau ngày Euler đăng bài chứng minh với n = 3, Sophie Germain tìm ra một phương pháp dành cho những n là số nguyên tố và 2n + 1 cũng là số nguyên tố. Bằng phương pháp này hai nhà toán học Adrien Marien Legendre và Pierre Gustave Lejeune Dirichlet song song với nhau tìm ra lời giải cho n = 5. Đến 1840, Gabrial Lamé chứng minh được cho n = 7. Tháng 04 năm 1847 hai nhà toán học người pháp Lamé và Cauchy đăng một số chi tiết về lời giải của mình. Ngày 24 tháng 05 năm 1847 nhà toán học Đức Kummer vạch ra 13 Khóa luận tốt nghiệp Đại học Lê Như Quỳnh những sai lầm khủng khiếp của hai nhà toán học pháp. Kummer đã chỉ ra không có một phương pháp đang tồn tại lúc bấy giờ có thể cho phép một cách tổng quát chứng minh Định lý Fermat. Sau công trình của Kummer nhiệt huyết tìm lời giải bị nguội lạnh hơn bao giờ hết. Mãi đến năm 1908, công nghiệp gia người Đức Paul Volfskehl thổi một làn sinh khí mới cho vấn đề “Định lý Fermat”. Paul Volfskehl đã phát hiện và lấp đầy lỗ hổng của nhà số học lừng danh Kummer. Sau chiến tranh thế giới thứ hai, một nhóm các nhà lập trình và các nhà toán học đã chứng minh định lý Fermat đúng với n = 500, sau đó n = 1000 và cuối cùng với n = 10000. Vào những thập niên 50 của thế kỉ XX, hai nhà toán học trẻ người Nhật đã đưa ra một giả thuyết, sau này mang tên họ, giả thuyết Taniyama – Shimura. Giả thuyết nói rằng "bất kỳ đường cong elliptic nào cũng có một hình thể modular tương ứng và ngược lại.". Các đường cong elliptic không liên quan gì đến các hình elip, thực ra chúng là những đường cong có dạng y 2 = x3 + ax2 + bx + c với a, b, c là những số nguyên. Các đường cong elliptic trở nên cuốn hút các nhà lý thuyết số vì chúng có thể trả lời nhiều câu hỏi về phương trình và nghiệm của phương trình. Những năm 60 của thế kỉ XX, các nhà toán học hầu như chỉ làm mỗi việc là kiểm tra giả thuyết Taniyama - Shimura. Người ta lấy một đường cong elliptic nào đó, tính dãy E, sau đó lại tìm hình thể modular có dãy M như thế. Mặc dù càng tìm nhiều bằng chứng thì giả thuyết càng thuyết phục, nhưng tất cả những bằng chứng đó đều không thể gọi là lời giải của giả thuyết. Việc chứng minh giả thuyết Taniyama 14 Tải về bản full