Luận văn Thạc sĩ Toán học: Một số chứng minh định lý Fermat nhỏ và định lý Wilson

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

Thêm vào BST

Báo xấu

54
lượt xem 4
download

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

Mục đích nghiên cứu của đề tài là trình bày các chứng minh ban đầu của Định lý Fermat nhỏ và Định lý Wilson và dạng mở rộng của chúng, sau đó trình bày thêm một số chứng minh tổ hợp gần đây. Đồng thời trình bày một số ứng dụng của hai định lý trên.

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: Một số chứng minh định lý Fermat nhỏ và định lý Wilson

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– BÙI THỊ MINH HẢI MỘT SỐ CHỨNG MINH ĐỊNH LÝ FERMAT NHỎ VÀ ĐỊNH LÝ WILSON LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– BÙI THỊ MINH HẢI MỘT SỐ CHỨNG MINH ĐỊNH LÝ FERMAT NHỎ VÀ ĐỊNH LÝ WILSON Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60460113 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. NGUYỄN ĐÌNH BÌNH THÁI NGUYÊN - 2017
iii Mục lục Lời mở đầu 1 1 Định lý Fermat nhỏ và Định lý Wilson 3 1.1 Một số kết quả về đồng dư . . . . . . . . . . . . . . . . . . . 3 1.2 Chứng minh ban đầu Định lý Fermat nhỏ . . . . . . . . . . . 7 1.3 Chứng minh ban đầu Định lý Wilson . . . . . . . . . . . . . . 15 1.4 Ứng dụng giải một số bài tập . . . . . . . . . . . . . . . . . . 28 2 Mở rộng Định lý Fermat nhỏ và Định lý Wilson 35 2.1 Một dạng tổng quát của Định lý Fermat nhỏ . . . . . . . . . . 35 2.2 Một dạng tổng quát của Gauss về Định lý Wilson . . . . . . . 39 2.3 Một số chứng minh tổ hợp . . . . . . . . . . . . . . . . . . . 44 2.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
1 Lời mở đầu Định lý Fermat nhỏ và Định lý Wilson là hai trong những định lý hữu ích, nổi tiếng trong toán học. Chúng được ứng dụng trong nhiều lĩnh vực khác nhau, tuy nhiên trong luận văn này, tác giả tập trung vào trình bày các chứng minh ban đầu của cả hai định lý và mở rộng của chúng, các chứng minh tổ hợp gần đây của hai Định lý Fermat nhỏ và Định lý Wilson. Thông qua việc chứng minh tổ hợp, tác giả muốn thể hiện gần đây các nhà toán học vẫn đang tiếp tục nghiên cứu và tìm các cách khác nhau chứng minh hai định lý trên trong suốt hai thế kỷ qua. Mục đích nghiên cứu Trình bày các chứng minh ban đầu của Định lý Fermat nhỏ và Định lý Wilson và dạng mở rộng của chúng, sau đó trình bày thêm một số chứng minh tổ hợp gần đây. Đồng thời trình bày một số ứng dụng của hai định lý trên. Nhiệm vụ nghiên cứu - Trình bày sơ lược lịch sử và chứng minh ban đầu về Định lý Fermat nhỏ và Định lý Wilson. - Trình bày một mở rộng của Định lý Fermat nhỏ và Định lý Wilson. - Một số ứng dụng của hai định lý này. Dự kiến đóng góp Từ lịch sử các chứng minh ban đầu của cả hai định lý và mở rộng của chúng, các chứng minh tổ hợp gần đây của hai Định lý Fermat nhỏ và Định lý Wilson. Thông qua việc chứng minh tổ hợp, chúng tôi muốn thể hiện các nhà toán học vẫn đang tiếp tục nghiên cứu và tìm các cách khác nhau chứng minh hai định lý trên trong suốt hai thế kỷ qua. Đây chính là nét mới so với kiến thức đã học ở
2 bậc Đại học. Ngoài phần mở đầu và kết luận, bố cục Luận văn dự kiến có 02 chương chính. Chương 1. Định lý Fermat nhỏ và Định lý Wilson Trình bày sơ lược lịch sử và chứng minh ban đầu về Định lý Fermat nhỏ và Định lý Wilson. Chương 2. Mở rộng Định lý Fermat nhỏ và Định lý Wilson Trình bày một mở rộng của Định lý Fermat nhỏ và Định lý Wilson, ứng dụng hai định lý đó. Luận văn này được thực hiện tại Trường Đại học Khoa học – Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của TS. Nguyễn Đình Bình. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các Thầy giáo, Cô giáo đã tham gia giảng dạy lớp Cao học Toán K9B2 (khóa 2015–2017); Nhà trường và các phòng chức năng của Trường; Khoa Toán – Tin, trường Đại học Khoa học – Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Cuối cùng, tôi xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, lãnh đạo đơn vị công tác và đồng nghiệp đã động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi khi học tập và nghiên cứu. Do còn hạn chế về nhiều mặt nên luận văn không tránh khỏi thiếu sót. Rất mong nhận được sự chỉ bảo, góp ý của thầy cô và các bạn. Tác giả Bùi Thị Minh Hải
3 Chương 1 Định lý Fermat nhỏ và Định lý Wilson Mục đích của chương là trình bày sơ lược lịch sử và chứng minh ban đầu về Định lý Fermat nhỏ và Định lý Wilson. Trong suốt luận văn, nhiều khái niệm và kết quả cơ bản của lý thuyết số và tổ hợp sẽ được sử dụng trong chứng minh của Định lý Fermat nhỏ và Định lý Wilson. Những chứng minh của định lý chính được sử dụng có thể được tìm thấy trong hầu hết các sách lý thuyết số và tổ hợp. Những bổ đề quan trọng đã được trình bày trong chương này. 1.1 Một số kết quả về đồng dư Trong mục này, tác giả trình bày một số kết quả về đồng dư, làm cơ sở để chứng minh Định lý Fermat nhỏ và Định lý Wilson. Những kết quả trong mục này được tác giả tham khảo từ [1],[2]. Định nghĩa 1.1.1. Cho a, b và m là các số nguyên, và m > 0. Nếu m|(a − b) thì ta nói a đồng dư với b (mod m) và ta viết a≡b (mod m). Các khái niệm về đồng dư lần đầu tiên được chính thức giới thiệu bởi Gauss
4 trong chương thứ nhất của cuốn Disquisitiones Aritmeticae. Ông chọn kí hiệu ≡ bởi sự gần gũi của nó với đại số [5, p.65] Bổ đề 1.1.2. Nếu ac ≡ bc (mod m) và gcd (c, m) = 1, thì a ≡ b (mod m). Bổ đề 1.1.3. (Định lý Nhị thức). Nếu n là số nguyên dương thì ! n n (x + y)n = ∑ xn−k yk , k=0 k ! n n! với = là số các tổ hợp chập k của n phần tử. k k!(n − k)! Bổ đề 1.1.4. (Định lý đa thức). Nếu k1 , k2 , . . . , km và n là các số nguyên không âm sao cho với n ≥ 1 và k1 + k2 + . . . + km = n, thì ! n (x1 + x2 + . . . + xm )n = ∑ x1k1 x2k2 . . . xm km , k1 +k2 +...+km =n k1 , k2 , . . . , km ! n n! với = là số các hoán vị lặp của n phần tử. k1 , k2 , . . . , km k1 !k2 ! . . . km ! Bổ đề 1.1.5. (Định lý phần dư Trung Hoa). Cho m1 , m2 , . . . , mr với r ≥ 2 là các số tự nhiên sao cho chúng nguyên tố cùng nhau từng đôi một và có tích bằng m. Khi đó hệ r phương trình đồng dư tuyến tính: x ≡ a1 (mod m1 ) x ≡ a2 (mod m2 ) .. . x ≡ ar (mod mr ) có nghiệm duy nhất (mod m).
5 Bổ đề 1.1.6. Nếu a và b là các số nguyên sao cho a ≥ b > 0, khi đó sẽ chỉ tồn tại duy nhất các số nguyên q, r sao cho a = qb + r và 0 ≤ r < b. Bổ đề 1.1.7. Cho v là bậc của x (mod N). Nghĩa là v là số nguyên dương nhỏ nhất sao cho xv ≡ 1 (mod N). Khi đó hệ {1, x, x2 , . . . , xv−1 } là phân biệt (mod N) và nguyên tố cùng nhau với N. Bổ đề 1.1.8. Cho d = gcd(a, m). Nếu d|b, thì ax ≡ b (mod m) có chính xác d nghiệm (mod m). Bổ đề 1.1.9. Nếu a2 ≡ 1(mod p) và gcd(a, p) = 1 thì a ≡ 1 (mod p) hoặc a ≡ p − 1(mod p). ! p Bổ đề 1.1.10. Nếu p là số nguyên tố và 0 < j < p thì p là ước của . j ! p p! Chứng minh. Ta có = , vì 0 < j < p nên sẽ không có p ở mẫu j j!(p − j)! ! p thức của , nhưng sẽ có một nhân tử p ở tử số. j ! ! p p Do đó ≡ 0 (mod p) nên suy ra p| . j j ! p−1 Bổ đề 1.1.11. Nếu p là số nguyên tố và 1 ≤ k ≤ p − 1 khi đó ≡ k (−1)k (mod p). Sử dụng phương!pháp quy nạp. p−1 Đặt S = {k| ≡ (−1)k (mod p)}. k ! p−1 Ta có 1 ∈ S vì = p − 1 ≡ −1 (mod p). Giả sử rằng k − 1 ∈ S. 1 ! p−1 Khi đó ≡ (−1)k−1 (mod p). Theo đẳng thức Pascal, k−1 ! ! ! p−1 p p−1 = − . k k k−1
6 Do vậy ta có ! ! p−1 p−1 ≡− ≡ (−1)(−1)k−1 (mod p) ≡ (−1)k (mod p). k k−1 Do đó k ∈ S. Bổ đề 1.1.12. Cho gcd(r, n) = 1 và r1 , r2 , . . . , rϕ(n) là các số nguyên dương bé hơn n và nguyên tố cùng nhau với n. Nếu r là một căn nguyên thủy của n, khi đó r, r2 , . . . , rϕ(n) đồng dư mođun n với r1 , r2 , . . . , rϕ(n) theo thứ tự, với ϕ(n) là số các số nguyên dương bé hơn n và nguyên tố cùng nhau với n. Bổ đề 1.1.13. Số nguyên n > 1 có căn nguyên thủy khi và chỉ khi n = 2, 4, pe hoặc 2pe với p là số lẻ, với căn nguyên thủy của n được định nghĩa như sau: Nếu r, n là các số nguyên tố cùng nhau, n > 0 và nếu ordn = ϕ(n) được gọi là căn nguyên thủy modunlo n. Bổ đề 1.1.14. (Công thức Euler). Cho a và n là các số nguyên không âm với a ≥ n. Khi đó ! ! ! n n n n! = an − (a − 1)n + (a − 2)n − (a − 3)n 1 2 3 ! n + . . . + (−1)n (a − n)n . n Công thức Euler gốc được chứng minh theo phương pháp quy nạp. Chứng minh dưới đây sử dụng nguyên lý Bù - Trừ Chứng minh (How and Turnage, 2007). Ban đầu ta đếm số cách khác nhau để đặt n vật khác nhau vào trong a ô khác nhau, với điều kiện n ô đầu tiên không được phép để trống và n ≤ a. Khi đó sẽ có n cách chọn với ô đầu tiên, n − 1 cách chọn với ô thứ hai. Tiếp tục như vậy sẽ có n! cách để đặt vật vào trong các ô. Bây giờ ta sẽ tìm câu trả lời theo một cách khác. Đầu tiên, xét tập U là tập bao gồm tất cả cách sắp xếp của các vật khác nhau vào trong các ô khác nhau không có sự hạn chế. Khi đó |U| = an , vì với mỗi n vật sẽ có a cách chọn đối với một ô.
7 Gọi Pi là tính chất mà ô thứ i rỗng. Sử dụng nguyên lý Bù - Trừ, ta phân phối các vật vào trong các ô không chứa bất kì tính chất nào trong các tính chất P1 , P2 , . . . , Pn . Gọi N(Pi0 ) là số cách phân phối không chứa tính chất Pi và N(Pi ) là số cách phân phối chứa tính chất Pi . Khi đó sử dụng nguyên lý Bù - Trừ N(P10 P20 · · · Pn0 ) = an − ∑ N(Pi ) + ∑ N(Pi Pj ) − ∑ N(Pi Pj Pk ) + · · · + (−1)n N(P1 P2 · · · Pn ). ! n Đầu tiên ta tính ∑ N(Pi ). Có cách chọn một trong các ô trống và khi 1 đó !sẽ có (a − 1)n cách sắp xếp n vật vào a − 1 ô còn lại. Do đó ∑ N(Pi ) = n (a − 1)n . 1 ! ! n n Tương tự, ∑ N(Pi Pj ) = (a − 2)n , ∑ N(Pi Pj Pk ) = (a − 3)n và tiếp 2 3 ! n tục như vậy. Do đó tổng quát với k = 1, 2, . . . , n sẽ có cách chọn k của tính k chất và khi đó có (a − k)n cách sắp xếp n vật vào trong (a − k) ô. Do đó ! ! ! n n n N(P10 P20 · · · Pn0 ) = an − (a − 1)n + (a − 2)n − · · · + (−1)n (a − n)n , 1 2 n hay suy ra ! ! ! n n n n! = an − (a − 1)n + (a − 2)n − · · · + (−1)n (a − n)n . 1 2 n 1.2 Chứng minh ban đầu Định lý Fermat nhỏ Định lý 1.2.1. (Định lý Fermat nhỏ) . Nếu p là số nguyên tố, a là một số nguyên và gcd(a, p) = 1 thì a p−1 ≡ 1 (mod p). Định lý Fermat nhỏ là cơ sở để kiểm tra tính nguyên tố theo xác suất trong kiểm tra Fermat.
8 Trong một lá thư gửi cho người bạn Berhard Frénicle de Bessy ngày 18 tháng 10 năm 1640, Pierre de Fermat đã lần đầu tiết lộ về Định lý Fermat nhỏ, ông đã khẳng định rằng: Nếu p là số nguyên tố và a là một số nguyên không chia hết cho p thì a p−1 − 1 chia hết cho p. Tuy nhiên, như thường lệ ông không cung cấp cách chứng minh với Frénicle "Tôi muốn gửi cho anh cả chứng minh tuy nhiên lại sợ rằng nó quá dài", xem [5]. Gần 100 năm sau, vào năm 1736 chứng minh đầu tiên cho Định lý Fermat nhỏ lần đầu được đưa ra bởi Euler trong một bài báo với tựa đề "Theorema- tum Quorundam ad Numeros Primos Spectantium Demonstratio". Leibniz đã có chứng minh với ý tưởng tương tự trong bản thảo không được công bố vào khoảng trước năm 1683, xem [5] Đã có rất nhiều tác giả nghiên cứu và đưa ra các cách khác nhau để chứng minh Định lý Fermat nhỏ. Trong mục này chúng tôi xin trình bày các cách chứng minh đó. Đây là một chứng minh được tìm thấy trong nhiều sách giáo khoa lý thuyết số, và chúng tôi thấy nó về cơ bản là tương đương với hai chứng minh đầu tiên của Euler. Chứng minh 1.1. Đặt S = {a|a p ≡ a(mod p)} với p nguyên tố và a ∈ N. Ta có 0 ∈ S vì 0 p = 0 với mọi p do vậy 0 p ≡ 0(mod p). Bây giờ ta giả sử rằng k ∈ S và k p ≡ k(mod p). Chúng ta muốn chỉ ra rằng k + 1 ∈ S, (k + 1) p ≡ (k + 1)(mod p). Theo định lý Nhị thức, ta có: ! p−1 p p− j (k + 1) p = k p + 1 p + ∑ k j=1 j ≡ k + 1(mod p). Nếu gcd(a, p) = 1, khi đó giản ước a p ≡ a(mod p) ta được a p−1 ≡ 1(mod p). Nếu a là số âm thì a ≡ r(mod p) khi 0 ≤ r ≤ p − 1. Do đó a p ≡ r p ≡ r ≡ a(mod p). Trong cuốn History of the Theory of Number [4, chương 3], cách chứng minh
9 Định lý Fermat nhỏ đã được đưa ra. Tiếp theo, chúng ta tìm hiểu các chứng minh được đưa ra bởi Leibniz, Euler, Lambert, Inovy, và Thue. Chúng tôi sử dụng [4, chương 3] như một tài liệu tham khảo chung cho chương này. Chứng minh dưới đây được đưa ra bởi G.W.Leibniz (1646 - 1716). Chứng minh 1.2 (Leibniz, 1680) Cho p là một số nguyên tố và cho x = a1 + a2 + . . . + am . m m Xét x p − ∑ aip . Ta sẽ chỉ ra rằng p|(x p − ∑ aip ). i=1 i=1 Theo định lí đa thức ta có, ! p x p = (a1 + a2 + . . . + am ) p = ∑ ak11 · ak22 · · · akmm k1 +...+km k1 , k2 , . . . , km ! p p! Chú ý rằng = . Khi ki 6= p với mọi i thì ki < p với k1 , k2 , . . . , km k1 ! · · · km ! mọi i. Khi đó không có nhân tử p ở mẫu số nhưng sẽ có một nhân tử p ở tử số. p! Do đó ki 6= p với mọi i, ≡ 0 (mod p). Do đó k1 ! · · · km ! m x − ∑ aip ≡ (a1p + a2p + · · · + amp ) − (a1p + a2p + · · · + amp ) = 0 (mod p). p i=1 m Do đó p|(x p − ∑ aip ). i=1 Đặt a1 = a2 = · · · = am = 1. Khi đó vì x = a1 + a2 + · · · + am , có nghĩa là p|(x p − x) với bất kì số nguyên x (dựa trên giá trị của m). Do đó x p − x ≡ 0 (mod p), hay x p ≡ x (mod p). Nếu gcd(x, p) = 1, suy ra x p−1 ≡ 1 (mod p). Dưới đây là ba cách chứng minh của L. Euler (1707-1783) về Định lí Fermat nhỏ và nó bao gồm cả chứng minh của Dickson. Chứng minh 1.3 (Euler, 1736)
10 Cho p là một số nguyên tố. Theo công thức Nhị thức, ! ! ! ! ! p p p p p 2 p = (1 + 1) p = + + +...+ + 0 1 2 p−1 p ! p = 1+ p+ +...+ p+1 2 = 2 + pm ! p Vì với mỗi j ∈ Z thì p| với 1 ≤ j ≤ p − 1. j Tương tự, 3 p = (1 + 2) p = 1 + 2 p + kp, với k ∈ Z vì với mỗi hệ số sẽ có một nhân tử của p. Khi đó 3 p − 1 − 2 p = kp, bằng cách thêm và bớt đi 2 ở vế trái ta thu được 3 p − 3 − (2 p − 2) = kp. Tổng quát ta có (1 + a) p = 1 + a p + np với n ∈ Z. Do đó (1 + a) p − 1 − a p = np và bằng cách thêm rồi bớt a vào bên trái biểu thức ta thu được (1 + a) p − (1 + a) − (a p − a) = np. Do đó (1 + a) p − (1 + a) = (a p − a) + np với n ∈ N. Nếu p chia hết a p − a thì khi đó p chia hết (1 + a) p − (1 + a). Ta chứng minh được với a = 2, p chia hết a p − a. Do đó với a > 2, ta xét a + 1. Giả sử p chia hết (a + 1) p − (a + 1). Khi đó p sẽ chia hết (a + 1 + 1) p − (1 + a + 1) = (a + 2) p − (a + 2). Khi p chia hết (a+2) p −(a+2) thì p sẽ chia hết (a+2+1) p −(a+2+1) = (a+3) p −(a+3). Tiếp tục quá trình đó ta sẽ thấy rằng p chia hết x p − x với mọi x ∈ Z. Do đó x p − x ≡ 0 (mod p) nên x p ≡ x (mod p). Nếu gcd(x, p) = 1 bằng giản ước ta có x p−1 ≡ 1 (mod p). Chú ý rằng chứng minh tiếp theo về cơ bản là giống chứng minh 1.1. Chứng minh 1.4 (Euler, 1747) Cho a, b ∈ Z và p là số nguyên tố. Khi đó (a + b) p − a p − b p là chia hết cho p
11 nếu: ! p−1 p p− j j (a + b) p − a p − b p = a p + b p + ∑ a b − a p − b p ≡ 0 (mod p). j=1 j Khi đó nếu a p − a và b p − b đều chia hết cho p thì khi đó (a + b) p − a − b chia hết cho p: (a + b) p − a − b ≡ a p − a + b p − b ≡ 0 (mod p). Đặt b = 1. Khi đó (a + 1) p − a − 1 chia hết cho p khi a p − a chia hết cho p. Vì (a + 1) p − (a + 1) chia hết cho p nên (a + 2) p − a − 2 cũng chia hết p. Tiếp tục và làm với a = 1 ta thấy rằng p chia hết x p − x với mọi x ∈ Z. Do đó x p − x ≡ 0 (mod p) hay x p ≡ x (mod p). Nếu gcd(x, p) = 1 bằng giản ước ta có x p−1 ≡ 1 (mod p). Chứng minh 1.5 (Euler, 1758) Cho p là số nguyên tố, a ∈ Z và gcd(a, p) = 1. Xét tập {1, a, a2 , . . . , ar } với r ∈ Z. Có p − 1 số dư dương nhỏ hơn p phân biệt. Cho am và an là hai số dư (mod p) với m > n. Khi đó am ≡ an (mod p). Giản ước an ở cả hai vế ta thu được am−n ≡ 1(mod p), vì vậy p chia hết am−n − 1. Cho t là số nguyên dương bé nhất sao cho at − 1 chia hết cho p. Vậy t là cấp của a(mod p). Khi đó tập {1, a, a2 , . . . , at−1 } có các số dư phân biệt (mod p). Do đó t ≤ p − 1. Nếu t = p − 1, chứng minh hoàn tất. Nếu t < p − 1, khi đó tồn tại một số nguyên dương k (với k < p). Khi đó hệ {k, ak, a2 k, . . . , at−1 k} có các số dư khác nhau, mà không có giá trị số dư nào là của lũy thừa của a (mod p). (Chứng minh bằng phản chứng. Giả sử kar ≡ kas (mod p) với r > s và r, s ≤ t − 1. Khi đó ar ≡ as (mod p) suy ra ar−s ≡ 1. Vì r 6= s, suy ra rằng r − s 6= 0. Vì r, s ≤ t − 1, r − s < t, nhưng do t là bậc của a. Do đó ta có điều mâu thuẫn.) Xét hai hệ {1, a, a2 , . . . , at−1 } và {k, ak, a2 k, . . . , at−1 k}. Chúng có hai giá trị dư khác nhau là 2t (mod p), mà 2t ≤ p − 1. Nếu t = p−1 2 , khi đó t|(p − 1). Nếu
12 p−1 t< 2 , ta bắt đầu với một số nguyên mới s và thấy rằng {s, as, a2 s, . . . , at−1 s} có các giá trị dư khác nhau, không có giá trị nào là lũy thừa của a hoặc ka. Do vậy 3t ≤ p − 1, do đó t ≤ p−1 3 . Tiếp tục quá trình đó, vì t ≤ p − 1, tính cho cùng t chia hết p − 1. Do đó p − 1 = tm với m ∈ Z, do đó a p−1 = atm . Do đó a p−1 ≡ atm (mod p), vậy a p−1 ≡ atm ≡ (at )m (mod p). Do đó a p−1 ≡ 1 (mod p). Trong chứng minh này, Euler kết luận rằng a p−1 − 1 chia hết cho at − 1. Bởi vì t|(p − 1), và do đó ta hiểu p − 1 = tm với mọi m. Do đó (at − 1)(a p−1−t + a p−1−2t + · · · + a p−1−tm+1 + 1) = a p−1 − 1. Ví dụ. Cho p = 11 và a = 10. Xét tập {1, 10, 102 , 103 , . . .}. Có 11 − 1 = 10. Chú ý rằng 10 và 103 có cùng số dư (mod 11): 10 ≡ 103 (mod 11). Khi đó bằng cách giản ước, ta có 102 ≡ 1 (mod 11). Thấy rằng 2 là bậc của 10 (mod 11). Khi đó hệ {1, 10} có phần dư khác nhau (mod 11), vì 2 < 11 − 1. Vì 2 < 11 − 1 khi đó tồn tại số nguyên k sao cho k < p mà nó không phải phần dư của lũy thừa của 10. Cho k = 2. Khi đó {2, 10 · 2} ≡ {2, 9} (mod 11) có số dư khác nhau mà không một số dư nào là lũy thừa của 10 (mod 11). Khi đó {1, 10} và {2, 9} cho ta 2 · 2 = 4 số dư phân biệt (mod 11), mà 2 · 2 < 11 − 1. Do đó tồn tại số nguyên s sao cho s < p mà không phải là lũy thừa của 10 hoặc 102 . Cho s = 3. Khi đó {3, 10·3} ≡ {3, 8} (mod 11} có số dư phân biệt, mà không số dư nào là lũy thừa của 10 (mod 11) hoặc 102 · 2 (mod11). Ta có 3 · 2 = 6 số dư phân biệt, nhưng 6 < 11 − 1. Tiếp tục tính toán và ta thấy rằng các số dư phân biệt như sau {1, 10}, {2, 9}, {3, 8}, {4, 7}, {5, 6}
13 Do đó có 5 · 2 = 10 = 11 − 1 số dư phân biệt (mod 11). Do đó 1011−1 = 105·2 = (102 )5 ≡ 15 ≡ 1 (mod 11). Johann Heinrich Lambert (1728-1777) đưa ra chứng minh Định lý Fermat nhỏ bằng việc sử dụng Định lý nhị thức và chuỗi hình học đan dấu: Chứng minh 1.6 (Lambert, 1769) Cho b = c + 1 và gcd(b, p) = 1, với p là số nguyên tố lẻ. Theo như định lý nhị thức, ! p−1 b p−1 − 1 = (c + 1) p−1 − 1 = −1 + c p−1 + (p − 1)c p−2 + c p−3 + · · · + 1 2 = −1 + c p−1 − c p−2 + c p−3 − · · · − c + 1 + Ap, ! ! p−1 p−1 Ta có ≡ (−1)k (mod p) nghĩa là = (−1)k + mp với mỗi số k k nguyên m. Vì các hạng tử trung gian là một chuỗi đan dấu, p−1 p−2 cp + 1 p−1 c p−1 − 1 c −c +···+1 = =c − . c+1 c+1 c p−1 − 1 Do đó b p−1 − 1 = c p−1 − 1 + Ap − . Chia mỗi vế cho p ta có c+1 b p−1 c p−1 − 1 c p−1 − 1 = +A− . (1.1) p p p(c + 1) Vì c < b, nếu p | c khi đó c ≡ 0 (mod p) suy ra b ≡ 1 (mod p) và 1 p−1 ≡ 1 (mod p). Nếu p - c, khi đó sử dụng quy nạp với các số nguyên tố cùng nhau với p, gọi S = {x|x p−1 − 1 ≡ 0 (mod p), p - x}. Khi đó 1 ∈ S vì 1 p−1 ≡ 1 (mod p). Giả sử c p−1 −1 c ∈ S sao cho c p−1 − 1 ≡ 0 (mod p). Khi đó p ∈ Z và vì gcd(p, c + 1) = 1 và c + 1|(c p−1 − 1) ta thấy rằng p(c + 1) | (c p−1 − 1) suy ra rằng p | (b p−1 − 1).
14 Do đó từ (1.1) ta có b p−1 − 1 ≡ (c + 1) p−1 − 1 ≡ 0 (mod p). Do đó c + 1 ∈ S. Jame Ivory (1764-1842) cũng đã đóng góp một chứng minh cho định lý Fermat nhỏ. Nó là một chứng minh được đưa ra trong hầu hết các tài liệu về lý thuyết số. Chứng minh 1.7 (Ivory, 1860) Cho n ∈ Z sao cho p - n. Xét tập T = {n, 2n, 3n, . . . , (p − 1)n} và cho S là tập các số dư dương bé nhất (mod p) của các phần tử của T . Nếu j ∈ Z và 1 ≤ j ≤ p−1, khi đó p - pa và bất kì phần tử nào của S và T là phân biệt. Do đó S là một hoán vị của {1, 2, . . . , (p − 1)}. Khi đó p−1 p−1 ∏ nj ≡ ∏j (mod p) j=1 j=1 n · (2n) · (3n) · · · (p − 1)n ≡ 1 · 2 · 3 · · · (p − 1) (mod p) n p−1 (p − 1)! ≡ (p − 1)! (mod p). Do đó gcd((p − 1)!, p) = 1 bằng thu gọn ta được n p−1 ≡ 1 (mod p). Chứng minh tiếp theo của định lý Fermat nhỏ được đưa ra bởi Axel Thue (1863-1922): Chứng minh 1.8 (Thue, 1893) Cho p là số nguyên tố lẻ. Chú ý rằng (a − b) p − (a − b − 1) p = (a − b) p − [(a − b) − 1] p ! p−1 p = ∑ (−1)i i (a − b)i ≡ 1 (mod p). i=0
15 Bởi vì ! p p [(a − b) − 1] p = ∑ (a − b)i (−1) p−i i=0 i ! ! p p = (−1) p (a − b)0 + (−1) p−1 (a − b)1 0 1 ! p + · · · + (−1)0 (a − b) p p và trừ (a − b − 1) p từ (a − b) p được ! p−1 p ∑ (−1)i i (a − b)i i=0 vì p là số lẻ. Bây giờ bằng cách cho b = 0, 1, 2, . . . với bất kì số nguyên a nào: a p − (a − 1) p = 1 + h1 p (a − 1) p − (a − 2) p = 1 + h2 p (a − 2) p − (a − 3) p = 1 + h3 p .. . 2 p − 1 p = 1 + ha−1 p 1 p − 0 p = 1 + ha p với hi là số nguyên. Bằng cách cộng các phần tử từ mỗi bên, ta có a p = a + hp với h = h1 + h2 + . . . + ha . Do đó ta có thể kết luận rằng p | (a p − a). 1.3 Chứng minh ban đầu Định lý Wilson Định lí 2. (Định lý Wilson) Nếu p là số nguyên tố khi đó (p − 1)! ≡ −1 (mod p).
16 Những tuyên bố về Định lý Wilson lần đầu tiên xuất hiện trong Meditationes Algebraicae vào năm 1770 trong một tác phẩm của nhà toán học người Anh Edward Waring. John Wilson, một cựu sinh viên của Waring, công bố định lý nhưng không cung cấp chứng minh, giống như Fermat đã làm với Định lý nhỏ Fermat. Vào năm 1771, Lagrange đã cung cấp chứng minh đầu tiên. Tương tự như trường hợp của Định lý nhỏ Fermat, lưu ý rằng đã có bằng chứng Leibniz nhận đã chứng minh Định lý này, nhưng không bao giờ công bố [5, P.97]. Trừ khi có ghi chú khác, các chứng minh trong chương này là từ [4, chương 3]. Các chứng minh dưới đây xuất hiện trong cuốn Beginning Number Theory của Robbin và rất nhiều sách khác. Chứng minh dưới đây là một trường hợp đặc biệt của một chứng minh tổng quát được đưa ra bởi Dirichlet vào năm 1828. Chứng minh 2.1. Nếu p = 2 khi đó (2 − 1)! = 1 ≡ −1 (mod 2) và nếu p = 3 khi đó (3 − 1)! = 2 ≡ −1 (mod 3). Do đó giả sử p là số nguyên tố lớn hơn 3. Vì (p − 1) ≡ −1 (mod p) nó cũng đủ để cho thấy rằng (p − 2)! ≡ 1 (mod p). Theo như bổ đề 7, với mỗi số j sao cho 1 ≤ j ≤ p − 1 sẽ tồn tại một số nguyên k sao cho 1 ≤ k ≤ p − 1 với jk ≡ 1 (mod p). Nếu k = j, khi đó j2 ≡ 1 (mod p) với j = 1 hoặc j = p − 1. Do đó nếu 2 ≤ j ≤ p − 2, khi đó tồn tại số nguyên k sao cho j 6= k và 2 ≤ k ≤ p − 2 và jk ≡ 1 (mod p). Vì có 21 (p − 3) cặp như thế nhân chúng với nhau được (p − 2)! ≡ 1 (mod p). Khi đó (p − 1)(p − 2)! ≡ (−1)(1) (mod p) ⇒ (p − 1)! ≡ −1 (mod p). Một trong những chứng minh sớm nhất về định lý Wilson đến từ Lagrange. Bây giờ ta sẽ cùng tìm hiểu. Chứng minh 2.2 (Lagrange, 1773) Cho (x + 1)(x + 2) · · · (x + p − 1) = x p−1 + A1 x p−2 + · · · + A p−1 . (1.2) Thay x bởi x + 1, sau đó nhân với x + 1 ta có (x + 1)(x + 2) · · · (x + p)
17 = (x + 1) p + A1 (x + 1) p−1 + A2 (x + 1) p−2 + · · · + A p−1 (x + 1). Nhân (1.2) với (x + p), từ hai biểu thức trên ta có (x + p)[x p−1 + A1 x p−2 + · · · + A p−1 ] = (x + 1) p + A1 (x + 1) p−1 + A2 (x + 1) p−2 + · · · + A p−1 (x + 1). Sau đó đồng nhất hệ số hai vế ta được ! p A1 = 2 ! ! p p−1 2A2 = + A1 3 2 ! ! ! p p−1 p−2 3A3 = + A1 + A2 4 3 2 .. . (p − 2)A p−2 = p + (p − 1)A1 + (p − 2)A2 + · · · + 3A p−3 (p − 1)A p−1 = A p−2 + . . . + A3 + A2 + A1 + 1. Do đó tổng quát với 1 ≤ k ≤ p − 1 ! ! ! ! p p−1 p−2 p−k+1 kAk = + A1 + A2 + · · · + Ak−1 . k+1 k k−1 2 ! p Cho p là số nguyên tố. Khi đó với 0 < k < p, là số nguyên chia hết cho p. k Do đó tất cả A1 , 2A2 , . . . , (p − 2)A p−2 đều chia hết cho p. ! ! ! ! p p−1 p−2 2 (p − 1)A p−1 = + A1 + A2 + · · · + A p−2 p p−1 p−2 2 = 1 + A1 + A2 + · · · + A p−2