ĐẠ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ỏ . . 1.3 Chứng minh ban đầu Định lý Wilson . . . . . . . . . . . . . . . . . . . . . . . 7 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ỏ . . 2.2 Một dạng tổng quát của Gauss về Định lý Wilson . . . . . . . . . . . . . 35 39
2.3 Một số chứng minh tổ hợp . . 2.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 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 ∑ k=0
(cid:32) (cid:33) n (x + y)n = xn−kyk, k
(cid:33) (cid:32) n = với là số các tổ hợp chập k của n phần tử. n! k!(n − k)! 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ì
(cid:33) (cid:32)
1 xk2 xk1
2 . . . xkm m ,
(x1 + x2 + . . . + xm)n = n k1, k2, . . . , km
∑ k1+k2+...+km=n
(cid:32) (cid:33)
= là số các hoán vị lặp của n phần tử. với n! k1!k2! . . . km! n 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)
(mod m2)
x ≡ a2 ... 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).
(cid:32)
. Bổ đề 1.1.10. Nếu p là số nguyên tố và 0 < j < p thì p là ước của (cid:33) p j
(cid:32) (cid:33)
= , vì 0 < j < p nên sẽ không có p ở mẫu Chứng minh. Ta có p! j!(p − j)! p j (cid:32)
thức của , nhưng sẽ có một nhân tử p ở tử số.
(cid:33) p j (cid:33) (cid:32) (cid:32) (cid:33) p p . Do đó ≡ 0 (mod p) nên suy ra p| j j
(cid:32) (cid:33)
≡ Bổ đề 1.1.11. Nếu p là số nguyên tố và 1 ≤ k ≤ p − 1 khi đó p − 1 k
(−1)k (mod p).
Sử dụng phương pháp quy nạp. (cid:32) (cid:33)
Đặt S = {k| ≡ (−1)k (mod p)}.
p − 1 k (cid:32) (cid:33)
Ta có 1 ∈ S vì = p − 1 ≡ −1 (mod p). Giả sử rằng k − 1 ∈ S. p − 1 1 (cid:32) (cid:33)
Khi đó ≡ (−1)k−1 (mod p). Theo đẳng thức Pascal, p − 1 k − 1
(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33)
= − . p − 1 k p k p − 1 k − 1
6
Do vậy ta có
(cid:32) (cid:33) (cid:32) (cid:33)
≡ − (mod p). ≡ (−1)(−1)k−1 (mod p) ≡ (−1)k p − 1 k p − 1 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 đó
(cid:33) (cid:33) (cid:33) (cid:32) n (cid:32) n (cid:32) n n! = an − (a − 1)n + (a − 2)n − (a − 3)n 1 3 2
(cid:33) (cid:32) n (a − n)n. + . . . + (−1)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(P(cid:48) i ) 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ừ
2 · · · P(cid:48)
1P(cid:48)
n) = an −∑ N(Pi) +∑ N(PiPj) −∑ N(PiPjPk)
N(P(cid:48)
+ · · · + (−1)nN(P1P2 · · · Pn).
(cid:32) (cid:33) n cách chọn một trong các ô trống và khi Đầu tiên ta tính ∑ N(Pi). Có 1
(cid:33) đó 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) = (cid:32) n (a − 1)n. 1 (cid:33) (cid:33) (cid:32) n (cid:32) n (a − 3)n và tiếp Tương tự, ∑ N(PiPj) = (a − 2)n, ∑ N(PiPjPk) = 2 3 (cid:33)
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 (cid:32) n 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) = an −
1P(cid:48)
2 · · · P(cid:48)
(cid:33) (cid:33) (cid:33) (cid:32) n (cid:32) n (cid:32) n N(P(cid:48) (a − n)n, (a − 1)n + (a − 2)n − · · · + (−1)n n 1 2
hay suy ra
(cid:33) (cid:33) (cid:33) (cid:32) n (cid:32) n (cid:32) n (a − n)n. n! = an − (a − 1)n + (a − 2)n − · · · + (−1)n n 1 2
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ì ap−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ì ap−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|ap ≡ a(mod p)} với p nguyên tố và a ∈ N. Ta có 0 ∈ S vì 0p = 0 với mọi p do vậy 0p ≡ 0(mod p). Bây giờ ta giả sử rằng k ∈ S và kp ≡ 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ó:
(cid:32) (cid:33)
p−1 ∑ j=1 ≡ k + 1(mod p).
kp− j (k + 1)p = kp + 1p + p j
Nếu gcd(a, p) = 1, khi đó giản ước ap ≡ a(mod p) ta được ap−1 ≡ 1(mod p). Nếu a là số âm thì a ≡ r(mod p) khi 0 ≤ r ≤ p − 1. Do đó ap ≡ 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,
m ∑ i=1
m ∑ i=1
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. ap i . Ta sẽ chỉ ra rằng p|(xp − Xét xp − ap i ).
Theo định lí đa thức ta có,
m
1 · ak2 ak1
2 · · · akm
(cid:33) (cid:32)
k1+...+km
xp = (a1 + a2 + . . . + am)p = ∑ p k1, k2, . . . , km
(cid:32) (cid:33)
= Chú ý rằng . Khi ki (cid:54)= p với mọi i thì ki < p với p! k1! · · · km! p k1, k2, . . . , 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ố.
≡ 0 (mod p). Do đó Do đó ki (cid:54)= p với mọi i, p! k1! · · · km!
m) = 0 (mod p).
m) − (ap
i ≡ (ap ap
2 + · · · + ap
1 + ap
2 + · · · + ap
1 + ap
m ∑ i=1
xp −
m ∑ i=1
Do đó p|(xp − ap i ).
Đặt a1 = a2 = · · · = am = 1. Khi đó vì x = a1 + a2 + · · · + am, có nghĩa là p|(xp − x) với bất kì số nguyên x (dựa trên giá trị của m). Do đó xp − x ≡ 0 (mod p), hay xp ≡ x (mod p). Nếu gcd(x, p) = 1, suy ra xp−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,
(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) p p p p + + + . . . + + 2p = (1 + 1)p = p 0 1 2 p p − 1
(cid:32) (cid:33) p = 1 + p + + . . . + p + 1 2
= 2 + pm
(cid:32)
Vì với mỗi j ∈ Z thì p| với 1 ≤ j ≤ p − 1. (cid:33) p j
Tương tự, 3p = (1 + 2)p = 1 + 2p + kp, với k ∈ Z vì với mỗi hệ số sẽ có một nhân tử của p. Khi đó 3p − 1 − 2p = kp, bằng cách thêm và bớt đi 2 ở vế trái ta thu được 3p − 3 − (2p − 2) = kp. Tổng quát ta có (1 + a)p = 1 + ap + np với n ∈ Z. Do đó (1 + a)p − 1 − ap = 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) − (ap − a) = np.
Do đó (1 + a)p − (1 + a) = (ap − a) + np với n ∈ N. Nếu p chia hết ap − 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 ap − 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 xp − x với mọi x ∈ Z. Do đó xp − x ≡ 0 (mod p) nên xp ≡ x (mod p). Nếu gcd(x, p) = 1 bằng giản ước ta có xp−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 − ap − bp là chia hết cho p
11
nếu:
(cid:32)
p−1 ∑ j=1
(a + b)p − ap − bp = ap + bp + ap− jb j − ap − bp ≡ 0 (mod p). (cid:33) p j
Khi đó nếu ap − a và bp − b đều chia hết cho p thì khi đó (a + b)p − a − b chia hết cho p:
(a + b)p − a − b ≡ ap − a + bp − b ≡ 0 (mod p).
Đặt b = 1. Khi đó (a + 1)p − a − 1 chia hết cho p khi ap − 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 xp − x với mọi x ∈ Z. Do đó xp − x ≡ 0 (mod p) hay xp ≡ x (mod p). Nếu gcd(x, p) = 1 bằng giản ước ta có xp−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, a2k, . . . , at−1k} 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 (cid:54)= s, suy ra rằng r − s (cid:54)= 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, a2k, . . . , at−1k}. 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
t < p−1 2 , ta bắt đầu với một số nguyên mới s và thấy rằng {s, as, a2s, . . . , at−1s} 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 đó ap−1 = atm. Do đó ap−1 ≡ atm (mod p), vậy ap−1 ≡ atm ≡ (at)m (mod p). Do đó ap−1 ≡ 1 (mod p). Trong chứng minh này, Euler kết luận rằng ap−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)(ap−1−t + ap−1−2t + · · · + ap−1−tm+1 + 1) = ap−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,
(cid:32) (cid:33)
bp−1 − 1 = (c + 1)p−1 − 1 = −1 + cp−1 + (p − 1)cp−2 + cp−3 + · · · + 1 p − 1 2
= −1 + cp−1 − cp−2 + cp−3 − · · · − c + 1 + Ap,
(cid:32) (cid:33) (cid:32) (cid:33)
≡ (−1)k (mod p) nghĩa là = (−1)k + mp với mỗi số Ta có p − 1 k
p − 1 k nguyên m. Vì các hạng tử trung gian là một chuỗi đan dấu,
= cp−1 − . cp−1 − cp−2 + · · · + 1 = cp−1 − 1 c + 1 cp + 1 c + 1
Do đó bp−1 − 1 = cp−1 − 1 + Ap − . Chia mỗi vế cho p ta có cp−1 − 1 c + 1
= + A − . (1.1) bp−1 p cp−1 − 1 p cp−1 − 1 p(c + 1)
Vì c < b, nếu p | c khi đó c ≡ 0 (mod p) suy ra b ≡ 1 (mod p) và 1p−1 ≡ 1 (mod p).
Nếu p (cid:45) 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|xp−1 − 1 ≡ 0 (mod p), p (cid:45) x}. Khi đó 1 ∈ S vì 1p−1 ≡ 1 (mod p). Giả sử c ∈ S sao cho cp−1 − 1 ≡ 0 (mod p). Khi đó cp−1−1 p ∈ Z và vì gcd(p, c + 1) = 1 và c + 1|(cp−1 − 1) ta thấy rằng p(c + 1) | (cp−1 − 1) suy ra rằng p | (bp−1 − 1).
14
Do đó từ (1.1) ta có
bp−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 (cid:45) 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 (cid:45) 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 ∏ j=1
p−1 ∏ j=1
j (mod p) n j ≡
(mod p)
(mod p). n · (2n) · (3n) · · · (p − 1)n ≡ 1 · 2 · 3 · · · (p − 1) np−1(p − 1)! ≡ (p − 1)!
Do đó gcd((p − 1)!, p) = 1 bằng thu gọn ta được np−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 ∑ i=0
(cid:32) (cid:33) p = (−1)i (a − b)i ≡ 1 (mod p). i
15
Bởi vì
(cid:32) (cid:33)
p ∑ i=0
[(a − b) − 1]p = (a − b)i(−1)p−i p i
(cid:32) (cid:33) (cid:32) (cid:33) p p (a − b)1 = (−1)p (a − b)0 + (−1)p−1 0 1
(cid:32) (cid:33)
(a − b)p + · · · + (−1)0 p p
và trừ (a − b − 1)p từ (a − b)p được
(cid:32) (cid:33)
p−1 ∑ i=0
(a − b)i (−1)i p i
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:
ap − (a − 1)p = 1 + h1 p (a − 1)p − (a − 2)p = 1 + h2 p (a − 2)p − (a − 3)p = 1 + h3 p
... 2p − 1p = 1 + ha−1 p 1p − 0p = 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ó
ap = a + hp
với h = h1 + h2 + . . . + ha. Do đó ta có thể kết luận rằng p | (ap − 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 (cid:54)= k và 2 ≤ k ≤ p − 2 và jk ≡ 1 (mod p). Vì có 1 2(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
(1.2) (x + 1)(x + 2) · · · (x + p − 1) = xp−1 + A1xp−2 + · · · + Ap−1.
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 + · · · + Ap−1(x + 1).
Nhân (1.2) với (x + p), từ hai biểu thức trên ta có
(x + p)[xp−1 + A1xp−2 + · · · + Ap−1]
= (x + 1)p + A1(x + 1)p−1 + A2(x + 1)p−2 + · · · + Ap−1(x + 1).
Sau đó đồng nhất hệ số hai vế ta được
(cid:32) (cid:33) p A1 = 2
(cid:32) (cid:32) (cid:33) (cid:33) p 2A2 = + A1 3 p − 1 2
(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) p 3A3 = + A1 + A2 4 p − 1 3 p − 2 2
...
(p − 2)Ap−2 = p + (p − 1)A1 + (p − 2)A2 + · · · + 3Ap−3
(p − 1)Ap−1 = Ap−2 + . . . + A3 + A2 + A1 + 1.
Do đó tổng quát với 1 ≤ k ≤ p − 1
(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33)
. kAk = + A1 + A2 + · · · + Ak−1 p − 1 k p k + 1 p − 2 k − 1 p − k + 1 2
(cid:32) (cid:33) 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)Ap−2 đều chia hết cho p.
(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33) (cid:33) p (cid:32) 2 + (p − 1)Ap−1 = A1 + A2 + · · · + Ap−2 p p − 1 p − 1 p − 2 p − 2 2
= 1 + A1 + A2 + · · · + Ap−2
18
Do đó
(p − 1)Ap−1 ≡ 1 (mod p)
(−1)Ap−1 ≡ 1 (mod p),
tức là
(mod p). Ap−1 + 1 ≡ 0
Do đó 1 + Ap−1 chia hết cho p. Nhắc lại phương trình ban đầu
(x + 1)(x + 2)(x + 3) · · · (x + p − 1) = xp−1 + A1xp−2 + A2xp−3 + · · · + Ap−1.
Vì từ (1.2) Ap−1 = (p − 1)!, suy ra Ap−1 + 1 ≡ 0 (mod p). Do đó
(p − 1)! ≡ (−1) (mod p).
Lagrange cũng cung cấp một chứng minh khác về định lý Fermat nhỏ:
Chứng minh 1.9. Cho x là số nguyên cố định. Vì x, x + 1, . . . , x + p − 1 là một dãy p các số nguyên liên tiếp, một trong số chúng chia hết cho p. Ngoài ra A1, A2, . . . , Ap−2 tất cả đều chia hết cho p và
Ap−1 = (p − 1)! ≡ −1 (mod p).
Do đó, biểu thức
x(x + 1) · · · (x + p − 1) = xp + A1xp−1 + · · · + Ap−2x2 + Ap−1x
cho ta
(mod p), 0 ≡ xp − x
đó chính là định lý Fermat nhỏ.
Số Ak ngày nay được biết là số Stirling. Một kí hiệu phổ biến là Ak = s(p, p − k) với k = 1, . . . , p. Lagrange lần đầu chứng minh s(p, k) ≡ 0 (mod p) với 1 ≤
19
k ≤ p − 1. Tham khảo [6, Chương 5] để hiểu thêm về số Stirling.
Lagrange cũng cung cấp chứng minh thứ hai, điều đó sử dụng công thức
Euler (tham khảo thêm Chương 2): Chứng minh 2.3 (Lagrange, 1773) Đọc lại công thức Euler (Bổ đề 11):
(cid:32) (cid:33) (cid:32) (cid:33) x x x! = ax − x(a − 1)x + (a − 2)x − (a − 3)x + · · · 2 3
Thay x = p − 1 và a = p ta có
(cid:32) (cid:33)
(p − 1)! = pp−1 − (p − 1)(p − 1)p−1 + (p − 2)p−1 p − 1 2
(cid:32) (cid:33) (cid:32) (cid:33)
− (p − 3)p−1 + · · · − (2p−1) + (−1)p−1. p − 1 3 p − 1 p − 2
Sử dụng Định lý Ferma nhỏ, ta có
(cid:32) (cid:33) (cid:32) (cid:33) (cid:32) (cid:33)
− +· · ·− (p−1)! ≡ 0−(p−1)+ +(−1)p−1(mod p). p − 1 2 p − 1 3 p − 1 p − 2
Chú ý rằng
(cid:32) (cid:33) (cid:32) (cid:33)
(1−1)p−1 = 1p−1 −(p−1)1p−2 + 1p−3(−1)2 −· · ·+(−1)p−1. p − 1 0 p − 1 2
Do đó
(mod p). (p − 1)! ≡ (1 − 1)p−1 − 1 ≡ −1
Euler cung cấp chứng minh Định lý Wilson có sử dụng căn nguyên thủy:
Chứng minh 2.4 (Euler, 1783) Cho a là một căn nguyên thủy của p. Khi đó gcd(a, p) = 1, bậc của a là ϕ(p) = p − 1 và ap−1 ≡ 1 (mod p). Xét tập {1, a, a2, . . . , ap−2}. Vì p − 1 là bậc của a,
20
khi đó đồng dư với hệ {1, 2, 3, . . . , p − 1}. Khi đó tích của hệ các phần tử phải đồng dư, do đó
(mod p)
ap−2 · ap−1 · · · a2 · a · 1 ≡ (p − 1)! (p−1)(p−2) 2 a (mod p). ≡ (p − 1)!
p−1 2 .
Giả sử p > 2, và cho p = 2n + 1 với mỗi số nguyên dương n. Khi đó
p−1 2 −1)(a
p−2 2 +1), từ Định lý Fermat nhỏ ta thấy p | (a p−2 2 + 1). Vì a là một căn nguyên thủy, p phải chia hết (a
p−1 2 −1) p−1 2 + 1).
an = a
2n(2n−1)
(p−1)(p−2) 2
Vì ap−1 ≡ 1 = (a hoặc p | (a p−1 2 ≡ −1 (mod p). Khi đó Tức là a
2 = an(2n−1) = (an)2n−1 ≡ (−1)2n−1
a = a (mod p).
Vì 2n − 1 là lẻ, suy ra (p − 1)! ≡ −1 (mod p).
Chứng minh tiếp theo của Định lý Wilson là của Dirichlet.
p−1 2
Chứng minh 2.5 (Dirichlet, 1828) Hai số m, n gọi là tương ứng nếu m, n < p và mn ≡ a (mod p), với p là số nguyên tố, a là số nguyên cố định, và a, p là nguyên tố cùng nhau. Bây giờ, với mỗi số 1, 2, . . . , p − 1 có duy nhất một số tương ứng. Bất kì một đồng dư tuyến tính nào với d = gcd(a, n), ax ≡ b (mod n) có d nghiệm nếu d | b. Trong trường hợp này, ax ≡ b (mod p) có 1 nghiệm vì gcd(a, p) = 1. Do vậy có duy nhất một số nguyên n với 1 ≤ n ≤ p − 1 sao cho mn ≡ a (mod p). Trường hợp 1: Nếu x2 ≡ a(mod p) không có nghiệm nguyên, số tương ứng là phân biệt và
(mod p) 1 · 2 · 3 · · · (p − 1) = (p − 1)! ≡ a
là bậc của a.
vì p−1 2 Trường hợp 2: Nếu k là một số nguyên dương nhỏ hơn p sao cho k2 ≡ a (mod p),
21
khi đó
(p − k)2 = p2 − 2pk + k2 ≡ a (mod p).
p−3 2
Bỏ k và p − k từ tích, ta được
(mod p). (1)(2) · · · (k − 1)(k + 1) · · · (p − k − 1)(p − k + 1) · · · (p − 1) ≡ a
p−3 2
Do đó
p−3 2
(mod p)
p−3 2
(mod p) (p − 1)! ≡ k(p − k) · a ≡ (pk − k2) · a
p−1 2 )
≡ −a · a (mod p)
(mod p). ≡ −(a
Cho a = 1. Định lý Wilson sau trường hợp 2:
p−1 2 ) ≡ −1 (mod p).
(p − 1)! ≡ −(1
Nếu p là số nguyên tố lẻ, khi đó tiêu chuẩn Euler thỏa mãn. Nếu a là số dư bậc hai (mod p), i.e nếu đồng dư x2 ≡ a (mod p) có nghiệm, khi đó theo Định lý p−1 Wilson và trường hợp 2 ta được a 2 ≡ 1 (mod p). Nếu a là số không dư bậc hai p−1 2 ≡ −1 (mod p). (mod p), khi đó theo trường hợp 1 và Định lý Wilson ta có a
p−1 2 ≡ ±1 (mod p), bình phương ta sẽ thu được Định lý Fermat nhỏ
Vì a
ap−1 ≡ 1 (mod p).
1−x).
Stern cũng đã cung cấp một chứng minh thú vị, sử dụng chuỗi Maclaurin của log( 1
Chứng minh 2.6 (Stern, 1860) Cho f là hàm giá trị thực. Tổng quát, nếu f khả vi tại x0, khi đó chuỗi Taylor
22
của hàm f tại x = x0 là
∞ ∑ k=0
(x−x0)k = f (x0)+ f (cid:48)(x0)(x−x0)+ (x−x0)2 +· · ·+ (x−x0)k +· · · f (k)(x0) k! f (cid:48)(cid:48)(x0) 2! f k(x0) k!
Khi x0 = 0, ta có chuỗi Maclaurin của f :
∞ ∑ k=0
(x)2 + · · · + (x)k + · · · (x)k = f (0) + f (cid:48)(0)(x) + f (k)(0) k! f (cid:48)(cid:48)(0) 2! f k(0) k!
1−x) = − log(1 − x). Chuỗi Maclaurin của − log(1 − x) là
Xét log( 1
+ + · · · 0 + x + x2 2 x3 3
2 + x3
Chú ý ta có
3 +··· = elog( 1
1−x ) =
ex+ x2 1 1 − x
2 + x3
Mà 1 + x + x2 + . . . = . Do đó ta có 1 1 − x
3 +··· = 1 + x + x2 + · · ·
ex+ x2 (1.3)
Bây giờ khai triển vế trái của (1.3) ta có
+ + · · · ex = 1 + x +
x2 2! 1!
x2 2 = 1 + ...
e + + + · · · x2 x3 2! 3! ( x2 2 )2 2! ( x2 2 )3 3!
xp p 1!
xp p = 1 + ...
e + + + · · · ( xp p )2 2! ( xp p )3 3!
23
2 + x3
Do đó
ex+ x2
x2 2! 1!
+ + + · · · ) + · · · )(1 + = (1 + x + ( x2 2 )2 2! ( x2 2 )3 3!
+ + + · · · ) . . . . . . (1 +
3 +··· x3 x2 + 2! 3! ( xp p )2 2! (cid:18) 1 2!
xp p 1! x 1!
1 2 1!
1 3 1!
( xp p )3 3! (cid:19) + x2 + + x3( · + + ) + = 1 + 1 2 1 3! 1 1! (cid:33) (cid:32)
1 2 1!
1 p 1
+ · · · + · · · · xp + . . . + 1 p! 1 (p − 2)!
Hạng tử xp là tổng của các hạng tử trong công thức sau
· · · · · = ( xp p )ap ap! xa1 a1! ( x2 2 )a2 a2! ( x3 3 )a3 a3! xa1+2a2+3a3+···+pap a1!a2!a3! · · · ap!2a23a3 · · · pap
trong đó a1 + 2a2 + 3a3 + · · · + pap = p.
. xp p!
= . Trường hợp 2. ap = 1, ai = 0 với mọi i < p. Cho ta xp p Trường hợp 1. a1 = p, ai = 0 với mọi i > 1. Ta sẽ được xp p 1!
= + với p không chia hết s và r, s là nguyên tố 1 p Trường hợp 3. a1 (cid:54)= p, ai = 0. Trong trường hợp ai < p, khi đó p sẽ không chia hết cho mẫu thức a1!a2!a3! · · · ap!2a23a3 · · · pap. 1 Do đó hệ số của xp là p!
r s cùng nhau. Khi đó hệ số ở biểu thức 1.3 sẽ tương đương với hệ sau
+ + = 1 1 p r s
( + ) = ) (1 − 1 p r s 1 p! p!s 1 1 p! p!s 1
s(1 + (p − 1)!) = p!s − p!r = p!(s − r) = p(p − 1)!(s − r).
24
Vì p (cid:45) s suy ra p | (1 + (p − 1)!) nên ta có
(p − 1)! ≡ −1 (mod p).
Chứng minh tiếp theo có liên quan đến "toán tử sai phân" ∆, được định nghĩa như sau
∆ f (x) = f (x + 1) − f (x)
với bất kì hàm f nào. Chú ý rằng
∆( f (x) + g(x)) = ( f (x + 1) + g(x + 1)) − ( f (x) + g(x))
= ( f (x + 1) − f (x)) + (g(x + 1) − g(x))
= ∆ f (x) + ∆g(x).
Ta định nghĩa ∆k f (x) = ∆k−1(∆ f (x)) = ∆(∆k−1 f (x)). Ta sẽ chỉ ra rằng
(cid:32) (cid:33) (cid:32) (cid:33)
f (x + k − 1) + f (x + k − 2) ∆k f (x) = f (x + k) − k k + 2
= f (x + j). (−1)k− j (1.4) (cid:32) k j k k − 1 − · · · + (−1)k f (x) (cid:33) k ∑ j=0
Bây giờ ta sử dụng quy nạp để chứng minh rằng
(cid:33)
k ∑ j=0
f (x + j) (−1)k− j ∆k f (x) = (cid:32) k j
với mọi số nguyên k. Và khi đó ta sẽ chứng minh Định lý Wilson.
Chứng minh 2.7 (Thue, 1893)
25
Cho (cid:33)
k ∑ j=0
f (x + j)} (−1)k− j S = {k|∆k f (x) = (cid:32) k j
(1) 1 ∈ S :
(cid:33) (cid:32) 1 (cid:32) (cid:33) 1 f (x + 0) + (−1)0 f (x + 1) ∆1 f (x) = f (x + 1) − f (x) = (−1)1−0 0 1
= − f (x) + f (x + 1)
2 ∈ S :
∆2 f (x) = ∆1(∆ f (x)) = ∆( f (x + 1) − f (x))
= ( f (x + 2) − f (x + 1)) − ( f (x + 1) − f (x)) (cid:33) (cid:32) 2 f (x + 1) + f (x) = f (x + 2) − 1
(2) Giả sử đúng với k − 1 có nghĩa là
(cid:32) (cid:33)
k−1 ∑ j=0
f (x + j). (−1)k−1− j ∆k−1 f (x) = k − 1 j
26
Khi đó
∆k f (x) = ∆(∆k−1 f (x)) (cid:32) (cid:33)
k−1 ∑ j=0
f (x + j)) (−1)k−1− j = ∆(
(cid:32) k − 1 j (cid:33) (cid:32) (cid:33)
= ∆[(−1)k−1−0 f (x + 0)] + ∆[(−1)k−1−1 k − 1 0 k − 1 1
(cid:32) (cid:33)
f (x + k − 1)] f (x + 1)] + · · · + ∆[(−1)k−1−(k−1) k − 1 k − 1
(cid:32) (cid:33) (cid:32) (cid:33)
= (−1)k−1 ( f (x + 1) − f (x)) + (−1)k−2 k − 1 0 k − 1 1
(cid:32) (cid:33)
( f (x + 2) − f (x + 1)) + · · · + (−1)0 k − 1 k − 1
(cid:33) (cid:32)
= (−1)k−1− j ( f (x + j + 1) − f (x + j)). k − 1 j ( f (x + k) − f (x + k − 1)) k−1 ∑ j=0
Với 1 ≤ j ≤ k − 1, theo đồng nhất thức Pascal hệ số của f (x + j) là
(cid:34)(cid:32) (cid:33) (cid:32) (cid:33)(cid:35) (cid:33) (cid:32) k + . (−1)k− j = (−1)k− j k − 1 j j k − 1 j − 1
Dễ dàng thấy rằng hệ số của f (x + k) là 1:
(cid:33)
(−1)k−k = 1, (cid:32) k k
và hệ số của f (x) là (−1)k:
(cid:33) (cid:32) k = (−1)k. (−1)k−0 0
27
Nếu f (x) = xn thì
(cid:33)
k ∑ j=0
(x + j)n. (−1)k− j ∆kxn = (cid:32) k j
k ∑ j=0
Khi x = 0 ta được (cid:33) (cid:32) k ( j)n. (−1)k− j ∆k0n = j
Ở đây ta chú ý rằng ∆k0n = k!S(n, k). [6,p.14] Cho f (x) = xp−1, với p là số nguyên tố. Từ (1.4), áp dụng Định lý Fermat nhỏ và Định lý Binomial, với k = 1, 2, 3, . . . , p − 2. Ta có k = 1, 2, 3, . . . , p − 2:
(cid:33) (cid:33)
k ∑ j=1
k ∑ j=1
≡ (1−1)k ≡ 0 (mod p). (−1)k− j (1+ j)p−1 ≡ (−1)k− j ∆k f (1) = (cid:32) k j (cid:32) k j
Bây giờ ta chú ý rằng
∆2 f (0) = ∆ f (1) − ∆ f (0) ∆3 f (0) = ∆2 f (1) − ∆2 f (0) ∆4 f (0) = ∆3 f (1) − ∆3 f (0)
...
(1.5)
∆p−2 f (0) = ∆p−3 f (1) − ∆p−3 f (0) ∆p−1 f (0) = ∆p−2 f (1) − ∆p−2 f (0).
28
Sử dụng (1.5) ta tìm được
∆p−1 f (0) = ∆p−2 f (1) − ∆p−3 f (1) + ∆p−4 f (1) − · · ·
+ ∆3 f (1) − ∆2 f (1) + ∆ f (1) − ∆ f (0)
≡ −∆ f (0)
= − f (1) + f (0) = −1p−1
(mod p). ≡ −1
Thay vào (1.4) ta được
(cid:32) (cid:33)
p−1 ∑ j=0 (cid:32)
j p−1 (−1)p−1− j ∆p−1 f (0) = ∆p−10p−1 = p − 1 j
(cid:33) (cid:32) (cid:33)
= (p − 1)p−1 − (p − 2)p−1 + (p − 3)p−1 p − 1 1 p − 1 2
(cid:32) (cid:33)
− · · · − 1p−1 p − 1 p − 2
Theo công thức Euler thì nó bằng (p − 1)!. Do đó (p − 1)! ≡ 1 (mod p).
1.4 Ứng dụng giải một số bài tập
Bài tập 1. Tìm tất cả các số nguyên dương x, y thỏa mãn
x2017 − 1 = (x − 1)(y2015 − 1).
Giải. Rõ ràng cặp số (1, y) với y nguyên dương tùy ý là nghiệm của phương trình. Xét trường hợp x > 1. Khi đó, ta có thể viết lại phương trình dưới dạng
= y2015 − 1. (1) x2016 + x2015 + . . . + x + 1 = x2017 − 1 x − 1
29
Gọi p là một ước nguyên tố bất kì của A = , ta sẽ chứng minh x2017 − 1 x − 1
p ≡ 1(mod 2017)
hoặc p = 2017. Thật vậy, nếu (p − 1, 2017) = 1 thì theo Định lí Bezout, tồn tại các số nguyên dương a, b để 2017a − (p − 1)b = 1. Do x2017 ≡ 1(mod p) nên
x2017a ≡ 1(mod p).
từ đó sử dụng Định lý Fermat nhỏ, ta có
1 ≡ x2017a ≡ x(p−1)b+1 ≡ x(mod p).
Điều này chứng tỏ x ≡ 1(mod p), suy ra
x2016 + x2015 + . . . + x + 1 ≡ 2017(mod p).
(2).
Do đó, ta có p = 2017. Tóm lại, nếu p là một ước nguyên tố của A thì hoặc p ≡ 1(mod 2017) hoặc p = 2017. Bây giờ, gọi d là ước dương bất kì của A, ta cũng dễ thấy d ≡ 1(mod 2017) hoặc d ≡ 0(mod 2017) Theo (1), ta có y − 1 là một ước dương của A, do đó y − 1 ≡ 0, 1(mod 2017), tức y ≡ 1, 2(mod 2017). Mặt khác, ta cũng có B = y2014 + y2013 + . . . + y + 1 cũng là ước của A. Nếu y ≡ 1(mod 2017) thì B ≡ 2015(mod 2017), mâu thuẫn với (2). Do đó y ≡ 2(mod 2017). Tuy nhiên, trong trường hợp này, ta lại có
B ≡ 22014 + 22013 + . . . + 2 + 1 = 22015 − 1 ≡ 1009(mod 2017)
là số chính phương. Bài tập 2. Tìm tất cả các số nguyên tố p sao cho cũng mâu thuẫn với (2). Do đó, nếu x > 1 thì không tồn tại cặp số nào thỏa mãn yêu cầu. Vậy chỉ có một cặp số duy nhất như đã nêu ở trên. 3p−1 − 1 p
Giải. Rõ ràng p = 2 thỏa mãn yêu cầu đề bài. Xét trường hợp p > 2, lúc này p
30
lẻ nên ta có thể đặt p = 2k + 1 với k ∈ Z+. Khi đó, ta có
= a2 (3k − 1)(3k + 1) p
với a ∈ Z+. Rõ ràng a chẵn và (3k − 1, 3k + 1) = 2 nên ta có thể đặt a = 2b với b ∈ Z+ và viết phương trình trên thành
· 3k − 1 2 3k + 1 2 = b2. (1) p
Xét hai trường hợp sau: Trường hợp 1. 3k − 1 chia hết cho p. Ta có
(cid:19) , = 1 (cid:18)3k − 1 2p 3k + 1 2
nên theo (1) thì
3k − 1 = 2px2
3k + 1 = 2y2
với x, y ∈ Z+ và (x, y) = 1. Dẫn đến y2 ≡ 2(mod 3) (vô lí). Trường hợp 2. 3k + 1 chia hết cho p. Tương tự như trên, ta cũng có
3k − 1 = 2x2,
3k + 1 = 2py2
với x, y ∈ Z+ và (x, y) = 1. Nếu k lẻ thì ta có 3k + 1 = 0(mod 4) nên y chia hết cho 2, từ đó suy ra 2py2 chia hết cho 8. Điều này vô lí vì 3k + 1 ≡ 4(mod 8). Do đó k chẵn, k = 2t(t ∈ Z+). Ta có
2x2 = 32t − 1 = (3t − 1)(3t + 1).
31
Chú ý rằng (3t − 1)(3t + 1) = 2 nên một trong hai số 3t − 1 và 3t + 1 phải là số chính phương. Tuy nhiên, 3t − 1 ≡ 2(mod 3) nên 3t − 1 không thể là số chính phương, suy ra
3t + 1 = c2
với c ∈ Z+, hay
3t = (c − 1)(c + 1).
Từ đây, ta suy ra c − 1 = 3m và c + 1 = 3n với m, n ∈ N, m < n và m + n = t. Do đó
2 = 3n − 3m = 3m(3n−m − 1).
Suy ra m = 0, n = 1 và t = 1. Ta tính được k = 2 và p = 5. Thử lại, ta thấy thỏa mãn. Bài tập 3. Tìm nghiệm nguyên của phương trình x2004 − y3003 = 7. Giải. Đặt X = x1002,Y = y1001, khi đó đưa phương trình đã cho về dạng:
X 2 −Y 3 = 7.
0 −Y 3 X 2
0 + 8
0 = 7 → X 2 → X 2
0 + 1 = Y 3 0 + 1 = (Y0 + 2)(Y 2
0 − 2Y0 + 4).
Ta sẽ chứng minh rằng phương trình không có nghiệm nguyên dương. Thật vậy, giả sử phương trình có nghiệm nguyên dương X0,Y0. Khi đó:
Chỉ có 2 khả năng xảy ra: 1) Nếu Y0 chẵn, tức là Y0 = 2k, ta có
Y 2 0 − 2Y0 + 4 = 4k2 − 4k + 4 → (Y 2 → (X 2 → X 2 ...4 0 − 2Y0 + 4) ...4 0 + 1) 0 ≡ −1(mod 4).
0 ≡ 1(mod 4), vậy
...4 hoặc là X 2
Ta biết rằng nếu X0 là số nguyên thì hoặc là X 2 0 từ phương trình trên suy ra điều vô lí. Vậy trường hợp 1 không thể xảy ra.
32
0 − 2Y0 + 4) ≡
0 + 1 ≡ −1(mod 4) → X 2 X 2
0 + 1 ≡ −2(mod 4).
2) Nếu Y0 lẻ, tức là Y0 = 4k + 1 hoặc Y0 = 4k − 1. a) Nếu Y0 ≡ −1(mod 4). Lúc này ta có (Y0 + 2) ≡ 1(mod 4) và (Y 2 −1(mod 4). Ta suy ra
Từ lập luận trên suy ra điều vô lí. Vậy trường hợp a) không thể xảy ra. b) Nếu Y0 ≡ 1(mod 4). Khi đó (Y0 + 2) ≡ 3(mod 4), suy ra Y0 + 2 có ít nhất một ước nguyên tố p có dạng 4k + 3. Suy ra
0 + 1)
0 ≡ −1(mod p) → (X 2
0 )2k+1 ≡ −1(mod p)
(X 2 ...p → X 2
0 ≡ −1(mod p).
≡ −1(mod p) → X p−1 → X (4k+3)−1 0
Do p là số nguyên tố, nên theo Định lý Fermat nhỏ, ta có
0 − X0)
0 − 1)
(X p ...p. ...p → X0(X p−1
0 ≡ 1(mod p) → X0 (cid:54)
Vì X 2 ...p và vì p nguyên tố nên (X0, p) = 1, do vậy đi đến
0 ≡ 1(mod p).
0 − 1)
(X p−1 ...p → X p−1
Dẫn đến điều vô lí. Vậy trong mọi trường hợp ta đề gặp mâu thuẫn, do đó giả thiết có nghiệm
nguyên dương là sai, tức là phương trình không có nghiệm nguyên dương. Vì lẽ ấy phương trình đã cho không có nghiệm nguyên dương. Bài tập 4. Tìm nghiệm nguyên dương của phương trình:
2 + · · · + x4
14 = 1599.
x4 1 + x4
Giải. Để ý rằng nếu a chẵn thì a4 = (2k)4 = 16k4, suy ra
a4 ≡ 0(mod 16).
33
Nếu a lẻ thì
a4 = (2k + 1)4 = 16k4 + 32k2 + 8k(3k + 1) + 1.
...2, do đó suy ra khi a lẻ thì a4 ≡ 1(mod 16).
Dễ thấy với mọi k ∈ Z, thì k(3k + 1) Vì lẽ đó, với mọi a ∈ Z thì
a4 ≡ 0(mod 16)
a4 ≡ 1(mod 16).
1 + x4 x4
2 + · · · + x4
14 ≡ m(mod 16),
Từ đó suy ra với mọi xi ∈ Z, i = 1, 2, . . . , 14, thì
trong đó m ∈ {0, 1, 2, . . . , 14}. Mặt khác:
1599 ≡ 15(mod 16).
1 + x4
2 + · · · + x4
14 = 1599 không có nghiệm nguyên.
Vì lẽ ấy phương trình x4
Bài tập 5. Cho n ≥ 5 là số tự nhiên. Chứng minh rằng
(cid:21) ...(n − 1) (cid:20)(n − 1)! n
...n.
Lời giải. a) Trường hợp 1: n là số nguyên tố. Theo Định lí Wilson, ta có (n − 1)! ≡ −1(mod n). Suy ra ((n − 1)! + 1) Ta có
(cid:21) (cid:21) − = − 1 (Vì 0 < < 1) (cid:20)(n − 1)! n (cid:20)(n − 1)! + 1 = n 1 n (n − 1)! + 1 n 1 n
= . (n − 1)! − (n − 1) n
Nên (cid:21) ...(n − 1).(Vì gcd(n, n − 1) = 1) (cid:20)(n − 1)! n
34
b) Trường hợp 2: n là hợp số. +/ Nếu n không là bình phương của một số nguyên tố. Khi đó n = rs với 1 < r < s < n. Do gcd(n, n − 1) = 1, nên s < n − 1 → (n − 1)! = kn(n − 1) suy ra
(cid:21) = k(n − 1) ...(n − 1). (cid:20)(n − 1)! n
+/ Nếu n không là bình phương của một số nguyên tố. Khi đó n = p2 với p là một số nguyên tố. Do p2 = n, n ≥ 5, suy ra p ≥ 3 → p2 ≥ 3p > 2p + 1 → 2p < p2 − 1, hay 2p < n − 1. Nên 1 < p < 2p < n − 1.
(cid:21) ...(n − 1). Từ đó suy ra
(cid:20)(n − 1)! n Vậy ta được điều phải chứng minh.
35
Chương 2
Mở rộng Định lý Fermat nhỏ và Định lý
Wilson
Mục đích của chương này là trình bày một dạng mở rộng của Định lý Fermat nhỏ và Định lý Wilson và ứng dụng của hai định lý đó.
2.1 Một dạng tổng quát của Định lý Fermat nhỏ
Trước tiên ta cần nắm vững một số vấn đề sau làm cơ sở nghiên cứu dạng
mở rộng của Định lý Fermat nhỏ và Định lý Wilson.
Định nghĩa 2.1.1. Phi hàm Euler ϕ(n) được định nghĩa là số các số nguyên k sao cho 1 ≤ k ≤ n và nguyên tố cùng nhau với n. Euler định nghĩa phi hàm Euler vào năm 1970.
Bổ đề 2.1.2. Với mỗi số nguyên a, d, n, nếu gcd(d, n) = 1 thì khi đó n hạng tử a, a + d, a + 2d, . . . , a + (n − 1)d khi chia cho n sẽ có số dư lần lượt là 0, 1, . . . , n − 1, phần dư nhỏ nhất (mod n) là 0, 1, . . . , n − 1 theo thứ tự.
Chứng minh. Xét tập {a, a + d, a + 2d, . . . , a + (n − 1)d}. Giả sử rằng
a + kd ≡ a + jd (mod n)
36
với k, d ∈ Z sao cho 0 ≤ k < j < n. Khi đó kd ≡ jd (mod n). Vì gcd(d, n) = 1 khi đó giản ước ta được k ≡ j (mod n), mâu thuẫn. Do đó các số trong dãy là đồng dư với {0, 1, . . . , n − 1} theo thứ tự.
Bổ đề 2.1.3. Φ(pm) = pm−1(p − 1).
Chứng minh. Chú ý rằng gcd(n, pm) = 1 khi và chỉ khi p (cid:45) n. Sẽ có pm−1 số nguyên giữa 1 và pm chia hết cho p : {p, 2p, 3p, . . . , (pm−1)p}. Do đó sẽ có pm − pm−1 số nguyên giữa 1 và pm mà chúng nguyên tố cùng nhau với pm. Như vậy ϕ(pm) = pm − pm−1 = pm−1(p − 1).
Bổ đề 2.1.4. Phi hàm Euler là hàm nhân tính.
Chứng minh. Một hàm số học được định nghĩa là hàm nhân tính nếu f (mn) = f (m) f (n) khi m, n nguyên tố cùng nhau [7, p.15]. Để chỉ ra phi hàm Euler là hàm nhân tính ta cần chỉ ra rằng với m và n là nguyên tố cùng nhau thì ϕ(mn) = ϕ(m)ϕ(n). Vì ϕ(1) = 1, kết quả sẽ được giữ nguyên nếu m hoặc n bằng 1. Do đó ta sẽ giả sử m, n > 1. Tiếp theo sắp xếp các số nguyên từ 1 tới mn vào m cột như sau:
· · ·
· · · · · ·
1 m + 1 2m + 1 ... 2 m + 2 2m + 2 ... r m + r 2m + r ... · · · m · · · 2m · · · 3m ...
(n − 1)m + 1 (n − 1)m + 2 · · · (n − 1)m + r · · · nm
Vì gcd(a, bc) = 1 ⇔ gcd(a, b) = 1 và gcd(a, c) = 1, ϕ(mn) không chỉ bằng với các phần tử bên trên mà nguyên tố cùng nhau với mn mà ϕ(mn) còn bằng với số nguyên tố cùng nhau với cả m và n. Chú ý rằng gcd(qm + nr) = gcd(r, m), như vậy cho một cột r nhất định, phần tử trong cột nguyên tố cùng nhau với m khi và chỉ khi r nguyên tố cùng nhau với m. Có ϕ(m) cột như vậy. Bây giờ cho gcd(r, m) = 1 với một số cột r. Các phần tử trong cột thứ r là:
r, m + r, 2m + r, . . . , (n − 1)m + r
37
Có n số nguyên trong dãy trên và không có hai số nào đồng dư với nhau. Rõ ràng hơn, ta giả sử sm + r ≡ tm + r (mod n). Khi đó sm ≡ tm (mod n). Suy ra cột thứ r chứa các số nguyên mà chúng nguyên tố cùng nhau với n như tập {0, 1, 2, . . . , n − 1}, gọi là số nguyên ϕ(n). Do đó tổng các số nguyên tố cùng nhau với cả m và n là ϕ(m)ϕ(n).
Ví dụ 1. ϕ(945) = ϕ(33 · 5 · 7) = 32 · 50 · 70 · (3 − 1) · (5 − 1) · (7 − 1) = 432
Ví dụ 2.
13433 ≡? (mod 945)
Chú ý rằng gcd(13, 945) = 1 và theo như bên trên, ϕ(945) = 432. Do đó
13433 = 13432 · 13 ≡ 13 (mod 945).
Định lý 3. (Tổng quát về Định lý Fermat nhỏ) Nếu n = ϕ(N) là số các số nguyên dương không vượt quá N và nguyên tố cùng nhau với N, khi đó xn − 1 chia hết cho N với bất kì số nguyên x nào nguyên tố cùng nhau với N.
Đầu tiên chúng ta nghiên cứu chứng minh của Euler [4, p.61]
Chứng minh 3.1 (Euler, 1760) Cho v là bậc của x. Khi đó theo bổ đề 2.2.2, hệ {1, x, x2, . . . , xn−1} là phân biệt (mod N) và nguyên tố cùng nhau với N. Do đó v ≤ ϕ(N). (Chứng minh bằng phản chứng. Giả sử v > ϕ(N). Khi đó có nhiều hơn ϕ(N) số nguyên mà chúng nguyên tố cùng nhau với N, mâu thuẫn). Nếu v = ϕ(N), chứng minh hoàn tất. Nếu v < ϕ(N) khi đó có một số nguyên dương a nhỏ hơn N và nguyên tố cùng nhau với N. Khi đó {a, ax, ax2, . . . , axv−1} là phân biệt với bất kì lũy thừa nào của x: (Chứng minh bằng phản chứng. Giả sử axm ≡ axn(mod N) với n < m. Khi đó xm−n ≡ 1 (mod N), mâu thuẫn. Nếu axm ≡ xn (mod N), khi đó a ≡ 1 (mod N) và ta biết rằng {1, x, x2, . . . , xv−1} là phân biệt). Do đó 2v ≤ n. Nếu 2v = n. chứng minh hoàn tất. Nếu không thì xét 3v ≤ n. Tiếp tục tính toán, ta thấy rằng v chia hết ϕ(N) suy ra Φ(N) = vm với một số
38
số nguyên m. Khi đó
xn = xvm = (xv)m ≡ 1m ≡ 1 (mod N).
k với pi (cid:54)= p j với i (cid:54)= j với mỗi pi là nguyên tố. Cho a ∈ Z và
Lapace cũng cung cấp một chứng minh dạng tổng quát [4, p.63], đó là: Nếu
gcd(a, n) = 1 thì khi đó aϕ(n) ≡ 1 (mod n). Chứng minh 3.2 (Laplace, 1776) 1 · · · pek Cho s = pe1 gcd(a, s) = 1. Cho
1
1 ) = (pe1−1
1
) · · · (pek−1 )(p1 − 1) · · · (pk − 1)
k )(p1 − 1) )(p2 − 1) · · · (pek−1
k
2
v = ϕ(s) = (pe1−1 q = ϕ(pe1 r = (pe2−1 )(pk − 1).
Khi đó
) · · · ( )( ). v = qr = s( pk − 1 pk p2 − 1 p2
p1 − 1 p1 Cho x = aq. Khi đó av − 1 = aqr − 1 = xr − 1 chia hết cho x − 1 bởi vì
e1 1 ) − 1. Bây giờ bằng quy nạp ta chỉ ra x − 1
1
(x − 1)(xr−1 + xr−2 + · · · + x + 1) = xr − 1.
1
e1−1 1
e1−2 1
Nghĩa là, aϕ(s) − 1 chia hết cho aϕ(p chia hết cho pe1 1 . Đầu tiên, cho e1 = 1. Khi đó x − 1 = aq − 1 = ap(1−1) (p1−1) − 1 = ap1−1 − 1 ≡ 0 (mod p1) theo như Định lý Fermat nhỏ. bây giờ ta giả sử nó đúng với e1 − 1 ≡ 1 (mod pe1−1 ) và
(p1−1)) = aϕ(p
) = 1 + mpe1−1
1
a(p
39
)(p1−1)
e1−1 1
với m ∈ Z. Khi đó
e1−2 1
)(p1−1))p1 )p1
e1 1 ) = a(p = (a(p = (1 + mpe−1−1 (cid:32)
aΦ(p
1 + mpe1
1 Q
1 (cid:33) p1 1 1 + mpe1 = 1 + mpe1 1 Q = 1 + pe1 1 (m + mQ).
i
k chia hết (xr − 1). Vì mỗi pei
1 | (x − 1) và (x − 1) | (xr − 1), suy rra 3 , · · · , pek là
mpe1−1 = 1 +
Khi đó x − 1 chia hết cho pe1 1 . Vì pe1 2 , pe3 1 | (xr − 1). Tương tự, mỗi pe2 pe1 nguyên tố cùng nhau, tích của chúng s cũng chia hết (xr − 1). Do đó
aϕ(s) = av = xr ≡ 1 (mod s).
2.2 Một dạng tổng quát của Gauss về Định lý Wilson
1 pe2
2 · · · pek
Gauss [4, p.65] là người đầu tiên công bố một cách khái quát nhất Định lý Wilson: Định lý 4. Cho P là tích của Φ(A) số nguyên n1, n2, . . . , nΦ(A), tất cả đều nhỏ hơn A và gcd(ni, A) = 1 với mọi i. Cho A = 2 j pe1 k với pi là các số nguyên tố lẻ phân biệt và ϕ(A) > 0. Nếu A = 4 hoặc A = 2 j pm với j = 0 hoặc j = 1, khi đó P ≡ −1 (mod A). Nếu không thì P ≡ 1 (mod A). Chứng minh 4.1. (Minding, 1832) Bình phương t của p1 và sử dụng Định lý phần dư Trung Hoa để xác định số a sao cho a ≡ t (mod p1) and a ≡ 1 (mod 2p2 p3 · · · pk). Khi đó a là một căn bậc lẻ không dư của A. Cho n1x ≡ a (mod A) và n2y ≡ a (mod A) sao cho n1 (cid:54)= n2 và n2 (cid:54)= a. Khi đó y (cid:54)= n1, x, n2. Theo cách này ϕ(A) số nguyên n1, n2, . . . , nϕ(A) có thể kết hợp với nhau n1x, n2y, . . . sao cho tích của của hai trong bất kì cặp nào đồng dư với a (mod A). Vì thế sẽ có ϕ(A)/2 cặp, P ≡ aϕ(A)/2 (mod A).
40
Trường hợp 1. A = 2 j pm với j = 0 hoặc j = 1. Khi đó
ϕ(A) = ϕ(2 j pm) = ϕ(2 j)ϕ(pm) = (pm−1)(p − 1),
và aΦ(A) = a(pm−1)(p−1) = aϕ(pm) ≡ 1 (mod pm) vì gcd(a, pm) = 1 theo như Định lý Fermat nhỏ. Do đó theo tiêu chuẩn Euler
p−1 2
(cid:17)pm−1 (cid:16) a aϕ(A)/2 = ≡ (−1)pm−1 ≡ −1 (mod p).
Do đó pm chia hết aϕ(A)/2 − 1 hoặc aϕ(A)/2 + 1. Ta biết rằng p chia hết aϕ(A)/2 + 1. Nếu p|(aϕ(A)/2 − 1 khi đó p|[(aϕ(A)/2 + 1) − (aϕ(A)/2 − 1)], suy ra p|2, mâu thuẫn vì p là số lẻ. Do đó p|(aϕ(A)/2 + 1) suy ra pm|(aϕ(A)/2 + 1). Do đó
aϕ(A)/2 ≡ −1 (mod pm) ≡ −1 (mod A).
Nếu A = 2pm khi đó vì a là số lẻ, aϕ(A)/2 ≡ (−1) (mod 2). Do đó P = aϕ(A)/2 ≡ −1 (mod A). Trường hợp 2. A = 2 j pm với j ≥ 2. Khi đó ϕ(A) = 2 j−1(pm−1)(p − 1), và
pm−1(p−1) 2
(cid:19)2 j−1 (cid:18) a aϕ(A)/2 = a(2 j−1)(pm−1)(p−1)/2 = ≡ (−1)2 j−1 ≡ 1 (mod pm,
và
aϕ(A)/2 = (a2 j−1 )(pm−1)(p−1)/2 ≡ 1pm−1(p−1)/2 ≡ 1 (mod 2 j).
Chú ý: Theo như Định lý Fermat nhỏ a2 j−1 ≡ 1 (mod 2 j). Do đó P ≡ aϕ(A)/2 ≡ 1 (mod A). Trường hợp 3. A = 2 j pmqn · · · với m, n, j > 0 và p, q phân biệt. Khi đó
aϕ(A)/2 =
a(pm−1)(p−1)/2(cid:105)2 j−1qn−1(q−1)··· (cid:104) qn−1(q − 1) · · · ≡ (−1)2 j−1
≡ 1 (mod pm)
41
vì q − 1 là số chẵn. Tương tự:
aqn−1(q−1)(cid:105)2 j−1 pm−1(p−1)/2··· (cid:104) aϕ(A)/2 =
(mod qn)
≡ 1 ≡ 12 j−1 pm−1(p−1)/2 · · · (mod qn)
2 (qn−1)(q−1)···
và
a2 j−1(cid:17)pm−1 p−1 (cid:16) aϕ(A)/2 = ≡ 1(mod 2 j).
Do đó P ≡ aϕ(A)/2 ≡ 1 (mod A) theo như Định lý phần dư Trung Hoa. Trường hợp 4. A = 2 j với j ≥ 2. Vì x2 ≡ −1 (mod 4) là vô lí, x2 ≡ −1 (mod 2 j) cũng vô lí vì 4|2 j. Do đó ta có thể ghép cặp các số nguyên lẻ nhỏ hơn 2 j sao cho x1 · x2 ≡ −1 (mod 2 j). Vì ϕ(2 j) = 2 j − 1, ta có 2 j − 2 cặp. Do đó Nếu A = 22:
P ≡ aϕ(A)/2 ≡ (−1)2 j−2 ≡ −1 (mod A)
và nếu A = 2 j với j > 2:
P ≡ aϕ(A)/2 ≡ (−1)2 j−2 ≡ +1 (mod A).
Tổng quát về Định lý Wilson cũng có thể bắt đầu bằng cách dưới đây:
Định lý 4. Giả sử n > 1 và Q là
{a|1 ≤ a ≤ n − 1, gcd(a, n) = 1}.
Cho P là tích các phần tử của Q. Nếu n = 2, 4, pe, hoặc 2pe, với p là số nguyên lẻ, khi đó P ≡ −1 (mod n) hoặc P ≡ 1 (mod n). Chứng minh 4.2. (Howard and Turnage, 2007)
Chứng minh này có sử dụng ý tưởng của Crelle (1840), Prouhot (1845), và
Arndt (1846). Trường hợp 1: n = 2, 4, pe, hoặc 2pe
42
Khi đó theo Bổ đề 1.1.12, n có một căn nguyên thủy, gọi nó là r. Khi đó sử dụng bổ đề 11, Q ≡ {r, r2, . . . , rΦ(n)} (mod n), vì thế tích của các phần tử là đồng dư P, và ta có
ϕ(n)(1+ϕ(n)) 2
P ≡ r · r2 · · · rϕ(n) (mod n) = r1+2+3+···+ϕ(n)
= r (cid:16) rϕ(n)/2(cid:17)(1+ϕ(n)) = ≡ (−1)(1+ϕ(n))
≡ −1 (mod n).
Ta sử dụng: •ϕ(n) là chẵn với n > 2.
(cid:17) 1 − 1 p
Chứng minh [5, p.128] Nếu n là lũy thừa 2, cho n = 2k với k ≥ 2. Khi đó (cid:1) = 2(k−1)là một số nguyên chẵn. Nếu n không phải ϕ(n) = ϕ(2k) = 2k (cid:0)1 − 1 2 là một lũy thừa của 2, khi đó nó sẽ chia hết cho một vài số nguyên tố lẻ p. Khi đó n = pkm với k ≥ 1 và gcd(pk, m) = 1. Vì ϕ là hàm nhân tính nên ϕ(n) = ϕ(pk) · ϕ(m) = pk (cid:16) · ϕ(m) = (cid:0)pk − pk−1(cid:1) ϕ(m) = pk−1(p − 1)ϕ(m). Do đó 2|(p − 1), ϕ(n) là số chẵn. •rϕ(n)/2 ≡ −1 (mod n).
Chứng minh Các trường hợp n = 2 và n = 4 là đơn giản, vì thế cho n = pe.
Khi đó
(rϕ(n)/2 − 1)(rϕ(n)/2 + 1) = rϕ(n) − 1 ≡ 0 (mod n)
suy ra p|(rϕ(n)/2 − 1) hoặc p|(rϕ(n)/2 + 1). Lưu ý rằng p không chia hết cho cả 2 nhân tử: nếu p chia hết cho cả hai nhân tử, nó sẽ chia hết cho liên hợp của nó, suy ra p|2, mâu thuẫn. Vì r là một căn nguyên thủy (mod n) nên ta không có (rϕ(n)/2 − 1) ≡ 0 (mod n). Do đó với n = pe,
rϕ(n)/2 + 1 ≡ 0 (mod n).
Chứng minh tương tự nếu n = 2pe. Trong trường hợp r là lẻ, do đó 2|(rϕ(n)/2 ± 1). Tóm lại ta có rϕ(n)/2 + 1 ≡ 0 (mod n). Trường hợp 2: 4|n and n > 4.
43
Xét x2 ≡ −1 (mod 4). Vì x2 ≡ −1 (mod 4) là không có nghiệm, x2 ≡ −1 (mod n) cũng không có nghiệm, vì 4 chia hết n. Do đó với mỗi phần tử a của Q, đồng dư ax ≡ −1 (mod n) có nghiệm duy nhất x = b trong Q, và b (cid:54)= a. Ghép cặp các phần tử a và b trong Q sao cho ab ≡ −1 (mod n). Khi đó vì n chia hết cho 4, n = 2 jm với số nguyên m và j ≥ 2. Khi đó
2 jm j ≥ 3, m ∈ Z n = 4p|n p là số nguyên tố lẻ
và do đó
2 j−1ϕ(m) ϕ(n) = 2(p − 1) · · ·
là chẵn. Khi đó Suy ra 4|ϕ(n), vì thế ϕ(n) 2
k , với j = 0 hoặc j = 1, với mỗi pi là số
1 pe2
2 · · · pek
P ≡ (−1)ϕ(n)/2 ≡ 1 (mod n).
Trường hợp 3: n = 2 j pe1 nguyên tố lẻ, và k ≥ 2. Bây giờ ta chỉ ra rằng x2 ≡ 1 (mod n) có 2k nghiệm. Để nhận thấy điều này, ta sử dụng x2 ≡ 1 (mod pei i ) có chính xác hai nghiệm x = 1 và x = −1. Lưu ý rằng 1 · · · pek x2 ≡ 1 (mod 2 j pe1 k ) nếu và chỉ nếu x2 ≡ 1 (mod 2 j) và x2 ≡ 1 (mod pei i ) for i = 1, . . . , k. Do đó sử dụng định lý phần dư Trung Hoa vào hệ
i ), i = 1, . . . , k
x ≡ 1 (mod 2 j) x ≡ ±1 (mod pei
ta thấy rằng các nghiệm xuất hiện là a và (n − a) với a(n − a) ≡ −(a)2 ≡ −1 (mod n).
Cho S là tích của tất cả các nghiệm của x2 ≡ 1 (mod n). Vì có 2k−1 cặp, S ≡ (−1)2k−1 ≡ 1 (mod n). Nếu a là phần tử của Q không thuộc S khi đó ax ≡ 1 (mod n) có nghiệm duy nhất x = b trong Q, và b (cid:54)= a. Ta ghép cặp các phần tử a và b trong Q − S để được ab ≡ 1 (mod n). Do đó P ≡ 1 (mod n).
44
Chú ý 1. Theo như Dickson [7, p.65], Gauss công bố định lý tổng quát và nhận xét rằng các căn nguyên thủy có thể sử dụng trong định lý. Đó là lí do mà
chúng tôi có cả Trường hợp 1 trong phần chứng minh của chúng tôi. Tuy nhiên chúng tôi lưu ý rằng phương pháp của Trường hợp 3 có thể dễ dàng sử dụng với n = p3 và n = 2pe. Trong những trường hợp đó, x2 ≡ 1 (mod n) có hai nghiệm, x ≡ ±1 (mod n). Chúng ta có thể ghép cặp các phần tử a, b khác sao cho ab ≡ 1 (mod n), vì vậy P ≡ −1 (mod n). Do đó ta có thể chứng minh ngắn gọn hơn khi xét trường hợp 4 | n và 4 (cid:45) n.
Chú ý 2. Trong trường hợp 3, giả sử pe1
1 |n với p1 ≡ 3 (mod 4). Khi đó x2 ≡ −1 (mod n) không có nghiệm, vì x2 ≡ −1 (mod pi) không có nghiệm. Trong trường hợp 2, chúng ta có thể kết hợp tất cả các phần tử a và b trong Q sao cho ab ≡ −1 (mod n). Do đó P ≡ (−1)ϕ(n)/2 ≡ 1 (mod n). Điều đó có nghĩa là trong trường hợp 3 chúng ta có thể giả định rằng pi là đồng dư với 1 (mod 4). Ví dụ. Giả sử n = 130 = 2 · 5 · 13. Khi đó k = 2. Ta muốn chỉ ra rằng x2 ≡ 1 (mod 130) có 2k = 4 nghiệm. Để làm điều đó, ta sử dụng định lí phần dư Trung Hoa để xét hệ
x ≡ 1 (mod 2)
x ≡ 1 (mod 2) x ≡ 1 (mod 5)
x ≡ 1 (mod 2) x ≡ 1 (mod 5) x ≡ 1 (mod 13) x ≡ −1 (mod 13) x ≡ 1 (mod 13) x ≡ 1 (mod 2) x ≡ −1 (mod 5) x ≡ −1 (mod 5) x ≡ −1 (mod 13)
Khi đó ta có bốn nghiệm để x2 ≡ 1 (mod n):
1, 51, −51 ≡ 79, −1 ≡ 129.
2.3 Một số chứng minh tổ hợp
Những chứng minh sau của Định lý Fermat nhỏ và Định lý Wilson chứng tỏ
rằng những định lý này vẫn đang được xem xét hiện nay. Những chứng minh đầu tiên đến từ cuốn Combinatorial Proofs of Fermat’s, Lucas’s and Wilson by Peter G. Anderson, Arthu T. Benjamin và Jeremy A. Rouse [2]. Những chứng minh dưới cùng được viết trong Proofs that Really Count by Arthur T. Benjamin and Jennifer J. Quinn [3].
45
Chúng ta sẽ bắt đầu với bổ đề sau: Bổ đề 17. Cho S là một tập hữu hạn, p là một số nguyên tố, giả sử f : S → S có tính chất f p(x) = x với mọi x thuộc S, với f p là p lần thành phần của f . Khi đó |S| ≡ |F| (mod p), trong đó F là tập các điểm bất động của f . Chứng minh. Đầu tiên ta chỉ ra rằng S là hợp rời nhau của tập có dạng {x, f (x), . . . , f p−1(x)}. Giả sử điều trên không đúng, nghĩa là giả sử ta có hai tập con riêng biệt của S sao cho
{x, f (x), . . . , f p−1(x)} ∩ {y, f (y), . . . , f p−1(y)} (cid:54)= ∅.
Khi đó tồn tại i, j ∈ Z với 0 ≤ j < i ≤ p − 1 sao cho
f i(x) = f j(y).
Khi đó:
f i+1(x) = f j+1(y) f i+2(x) = f j+2(y) ... f p(x) = f j+k(y), j + k < p, và p = i + k.
Khi đó:
x = f j+k(y) f (x) = f j+k+1(y) f 2(x) = f j+k+2(y)
...
i.e. {x, f (x), . . . , f p−1(x)} = {y, f (y), . . . , f p−1(y)}.
Do đó hoặc {x, f (x), . . . , f p−1(x)} ∩ {y, f (y), . . . , f p−1(y)} = ∅ hoặc
{x, f (x), . . . , f p−1(x)} = {y, f (y), . . . , f p−1(y)}. Bây giờ ta cần chỉ ra rằng mọi độ dài chu trình của x hoặc là bằng 1 hoặc là bằng p. Cho x ∈ S. Khi đó hoán vị
46
f (x) f 2(x) f k−1(x) x f k−1(x) x f (x) f p−1(x) . . . . . . . . .
tạo bởi x là tập {x, f (x), . . . , f p−1(x)}. Nếu x là điểm bất động của f thì f (x) = x suy ra độ dài chu trình của x bằng 1. Giả định rằng f p(x) = x với mọi x ∈ S, suy ra độ dài chu trình của x sẽ lớn hơn p. Bây giờ, giả sử độ dài chu trình của x là k sao cho 1 < k ≤ p − 1. Khi đó {x, f (x), . . . , f k−1(x)} là hoán vị của x, và ta có: f (x) x Có tất cả p ô chia cho m tập hợp của k số hạng. Do đó p = mk mâu thuẫn với p là số nguyên tố. Do đó độ dài của chu trình x sẽ bằng 1 hoặc bằng p. Cuối cùng ta chỉ ra rằng |S| ≡ |F| (mod p). Theo như bên trên, độ dài chu trình x là bằng 1 hoặc bằng p. Trong S thì hoặc x là điểm bất động hoặc không. Độ lớn S là tổng số của điểm bất động, |F|, cộng thêm số điểm khác |N|. Vì độ dài của điểm bất động là p,số điểm bất động là bội của p. Do đó
|S| = |F| + |N| = |F| + pn ≡ |F| (mod p).
Bây giờ ta có thể sử dụng bổ đề này để chứng minh Định lý Fermat nhỏ:
Chứng minh 1.10. (Anderson, Benjamin, and Rouse, 2005) Cho S là tập tất cả các vòng màu có độ dài là p, với a màu được chọn và mỗi màu có độ dài bằng một. Cho f : S → S sao cho f (x) = x1,với x1 là x quay theo chiều kim đồng hồ 1 đơn vị. Do đó |S| = ap. Ta có a vòng màu và độ dài p với cùng một màu. Vì mỗi vòng quay của vòng màu sẽ cùng màu, i.e f (x) = x là điểm bất động của ta. Tức là |F| = a. Do đó với bổ đề trước đó, ap ≡ a (mod p ). Ví dụ. Cho p = 3 = là độ dài của vòng và a = 2 = là số màu trên vòng đó. Ta muốn minh họa rằng số vòng màu có độ dài p với a cách chọn màu với độ dài ap = 8. Hình 2.1 minh họa tất cả các trường hợp có thể.
Do đó số lượng vòng với độ dài bằng 3 và có 2 màu là 23 = 8. Có 2 vòng mà
chỉ có một màu duy nhất. Vì mỗi vòng đều có cùng một màu theo như bổ đề
23 = 8 ≡ 2(mod 3).
Bây giờ ta có thể sử dụng cùng bổ đề đó để chứng minh Định lý Wilson:
47
Hình 2.1:
Chứng minh 3.8. (Anderson, Benjamin, and Rouse, 2005)
1
Đầu tiên, một hỏi được đặt ra là: Có bao nhiêu hoán vị của {0, 1, . . . , p − 1} có duy nhất một chu trình? 0 p − 1 p − 2 p − 3 . . . Chú ý rằng: Mỗi cách chọn một ô xác định số cách chọn khi chúng ta xây dựng hoán vị. Tất cả các hoán vị bắt đầu với 0, do đó ta có (p−1)! hoán vị của {0, 1, . . . , p−1} có duy nhất một chu trình.
Cho S là tập (p − 1)! hoán vị với {0, 1, . . . , p − 1} với chính xác một chu
trình,và xác định hàm f trên S như dưới đây:
Cho (0, a1, a2, . . . , ap−1) là một hoán vị trong S. Khi đó f ((0, a1, a2, . . . , ap−1)) =
(1, a1 + 1, a2 + 1, . . . , ap−1 + 1) ∈ S trong đó tổng tất cả đồng dư mô đun p. Chú ý rằng
f p((0, a1, a2, . . . , ap−1)) = (0, a1, a2, . . . , ap−1).
Từ bổ đề trước đó ta biết rằng |S| ≡ |F| (mod p). Do đó ta phải chỉ ra rằng
có p − 1 điểm bất động của f . Yêu cầu: Ta chứng minh (0, a1, a2, . . . , ap−1) là điểm bất động của của f khi và chỉ khi tồn tại a sao cho 1 ≤ a ≤ p − 1, thỏa mãn (0, a1, a2, . . . , ap−1)=(0, a, 2a, ..., (p− 1)a).
Đầu tiên ta chỉ ra rằng (0, a, 2a, ..., (p − 1)a) là một điểm bất động: vì theo
48
như định nghĩa của f , ta có
f (0, a, ..., (p − 1)a) = (1, 1 + a, 1 + 2a, ..., 1 + ka, 1 + (k + 1)a, ..., 1 + (p − 1)a).
Ta có 1 + ka ≡ 0 (mod p) với mỗi k, do đó
1 + (k + 1)a = 1 + ka + a ≡ a (mod p)
1 + (k + 2)a = 1 + ka + 2a ≡ 2a (mod p)
. . .
1 + (k + (p − 1))a = 1 + ka − a ≡ (p − 1)a (mod p)
Do đó (0, a, ..., (p − 1)a) là điểm bất động. Bây giờ giả sử (0, a1, a2, ..., ap−1) là điểm bất động của f . Do đó
f (0, a1, a2, . . . , ap−1) = (1, 1 + a1, . . . , 1 + ap−1)
f (2)(0, a1, a2, . . . , ap−1) = (2, 2 + a1, . . . , 2 + ap−1)
. . .
f (a1)(0, a1, a2, . . . , ap−1) = (a1, 2a1, . . . , a1 + ap−1)
với a2 = 2a1. Tiếp tục tính toán ta được
f (2a1)(0, a1, a2, . . . , ap−1) = (2a1, 3a1, . . . , 2a1 + ap−1)
với a3 = 3a1. Tổng quát lên ta được
f (ka1)(0, a1, a2, . . . , ap−1) = (ka1, (k + 1)a1, . . . , ka1 + ap−1)
với ak+1 = (k + 1)a1. Vì (0, a1, a2, . . . , ap−1) là một điểm bất động, ta có
(0, a1, a2, . . . , ak+1, . . . , ap−1) = (0, a1, 2a1, . . . , (k + 1)ak+1, . . . , (p − 1)a1)
suy ra tất cả các điểm bất động của S có dạng như trên.Vì có tất cả (p − 1) cách
49
chọn với a1, có (p − 1) điểm bất động của f . Do đó
|S| ≡ |F| (mod p)
(p − 1)! ≡ (p − 1) (mod p)
≡ −1 (mod p)
Ví dụ. Minh họa cho chứng minh trên, cho p = 5 và đặt Π = (0, 3, 1, 4, 2). Chú ý rằng f (Π) = (1, 4, 2, 0, 3) = (0, 3, 1, 4, 2), vì vậy Π là một điểm bất động với Π(0) = 3. Khi đó
Π = f (3)(Π) = (3, 6, 4, 7, 5), so Π(3) = 6 Π = f (6)(Π) = (6, 9, 7, 10, 8), so Π(6) = 9 Π = f (9)(Π) = (9, 12, 10, 13, 11), so Π(9) = 12 Π = f (12)(Π) = (12, 15, 13, 16, 14) = (12, 0, 13, 16, 14)
với Π(12) = 0. Do đó (0, 3, 1, 4, 2) = (0, 3, 6, 9, 12) điều này minh họa cho chứng minh trên với a1 = 3. Bây giờ ta nhìn vào một chứng minh khác của định lí Fermat nhỏ:
Chứng minh 1.11. (Benjamin and Quinn, 2003)
Đầu tiên, một câu hỏi được đặt ra là: Có bao nhiêu cách để các số {1, 2, . . . , p} chọn một màu mà không được số nào trùng màu với số kia? Bây giờ ta sẽ chứng
minh câu hỏi của Định lý Fermat nhỏ.
Một cách khác để dễ hiểu hơn là ta có một hộp gồm có p ô, mỗi ô sẽ chưa một số trong tập {1, 2, . . . , p}. Khi đó với một ô ta có thể chọn bất kì một màu. Do đó tổng số màu kết hợp là ap, nhưng ta phải tìm ra trường hợp a mà chỉ có duy nhất một màu. Do đó cách để các số {1, 2, . . . , p} có duy nhất một màu ap − a.
50
2.4 Ứng dụng
Các công việc chi tiết trước đó đã cho thấy sự đa dạng về các cách chứng minh của Định lý Fermat nhỏ và Định lý Wilson. Tuy nhiên điều quan trọng là cần
lưu ý những ứng dụng thực tế của các định lý này.
Trong cuốn sách An Introduction to Cryptography, Richard A. Mollin đã định nghĩa về mật mã là nghiên cứu các phương pháp để gửi tin nhắn . . . bằng cách trá hình . . . sao cho chỉ có những người nhận . . . có thể giải mã nó. Một loại cụ thể của mật mã là mật mã Public-Key. Mollin định nghĩa nó như một hệ mật bao gồm một tập hợp các mã biến đổi . . . và một bộ giải mã biến đổi . . . [ mà ] mỗi cặp (e, d) thì e được gọi là khóa công khai, được công bố công khai, trong khi chìa khóa giải mã d được giữ bí mật. Hệ thống mật mã phải thỏa mãn điều kiện rằng các tính toán là không khả thi để tìm ra d và e [7].
Việc sử dụng hệ thống mật mã khóa công khai dựa vào thuật toán RSA, đặt
theo tên nhà phát triển của nó R. Rivest, A. Shamir và Adleman. Thuật toán được phát minh vào năm 1978 và chủ yếu dựa vào Định lý Fermat nhỏ và Định
lý phần dư Trung Hoa.
Các mô tả sau đây của mật mã RSA có thể được tìm thấy trong Elementary
Number Theory [5] của Burton, và nó đã được hoàn thiện :
Đầu tiên, người sử dụng hệ thống mã RSA chọn một cặp số nguyên tố phân biệt p và q đủ lớn và tích của nó là n, và n là một số nguyên tố có thể nhiều hơn 100 chữ số; n được gọi là the enciphering modulus. Tiếp theo, phải chọn một số nguyên k, gọi là số mũ phục hồi sao cho gcd(k, Φ(n)) = 1. Khi đó cặp (n, k) được đặt trong một tập tin công cộng như là chìa khóa mã hóa của người dùng. Trước khi một thông điệp được mã hóa, một "bảng chữ cái kỹ thuật số" phải
được xác định, trong đó mỗi chữ cái, không gian, và dấu chấm câu được đưa ra
51
một mô tả bằng số. Burton [5, p.142] đã đưa ra một tiêu chuẩn như sau:
A = 01 K = 11 U = 21 1 = 31
B = 02 L = 12 V = 22 2 = 32
C = 03 M = 13 W = 23 3 = 33
D = 04 N = 14 X = 24 4 = 34
E = 05 O = 15 Y = 25 5 = 35
F = 06 P = 16 Z = 26 6 = 36
G = 07 Q = 17 , = 27 7 = 37
H = 08 R = 18 . = 28 8 = 38
I = 09 S = 19 ? = 29 9 = 39
J = 10 T = 20 0 = 30 ! = 40
với 00 chỉ ra một khoảng trống giữa các từ. Như vậy với bảng chữ cái này, thông điệp
Leibniz deserves more credit.
được chuyển thành
M = 1205090214092600040519051822051900131518050003180504092028.
Đối với một người có nhu cầu gửi tin nhắn đến một người sử dụng khác, trước tiên phải có được khóa công khai của người dùng đó và sau đó chuyển M với số mã hóa r bằng cách lũy thừa M với số mũ k và sau đó làm giảm kết quả theo modulo n:
Mk ≡ r (mod n).
Người nhận đầu tiên cần phải xác định số nguyên j, số mũ phục hồi sao cho
k j ≡ 1 (mod Φ(n)).
Từ gcd(k, Φ(n)) = 1, thì phải có một nghiệm duy nhất theo modulo Φ(n). Sử
52
dụng thuật toán Euclide, người ta có thể tìm thấy j này. Vì các số mũ phục hồi chỉ có thể được tìm thấy bởi những người biết kv các nguyên tố của n (cần thiết để tìm Phi(n), giá trị của k là bí mật. Cuối cùng, để dịch r trở lại M, người nhận có thể tìm thấy M, cho
r j ≡ (Mk) j ≡ M(1+Φ(n)t) ≡ M(MΦ(n))t ≡ M 1t ≡ M (mod n).
Lưu ý rằng bước quan trọng này là nơi sử dụng đến Định lý nhỏ Fermat. Ta giả định rằng gcd(M, n) = 1. Nếu M và n không phải là nguyên tố cùng nhau, khi đó ta có thể đi đến kết luận tương tự thông qua các Định lý phần dư Trung Hoa. (Xem [5, tr. 143])
Ví dụ sau đây sẽ cho thấy các hoạt động của Thuật toán RSA, nhưng sẽ sử dụng số nguyên tố nhỏ để hiểu cho rõ ràng. Ví dụ. Cho p = 13 và q = 29. Khi đó n = 377 suy ra
Φ(n) = (13 − 1)(29 − 1) = 336.
Bây giờ chúng ta phải chọn một số nguyên k, số mũ phục hồi, sao cho gcd(k, Φ(n)) = 1. Số 67 sẽ là lựa chọn đúng đắn. Số j phải đáp ứng
k j ≡ 1 (mod Φ(n)).
Do đó bằng các thuật toán Euclide, chúng ta có thể đặt j = −5 ≡ 331 (mod 336). Ta có thể mã hóa thông báo sau đây bằng cách sử dụng bảng chữ cái kỹ thuật số được liệt kê ở trên:
HELP!
thành
M = 0805121640.
Sau đó chia M thành các khối mã, do mỗi khối mã nhỏ hơn Φ(n) = 336. Do đó chúng ta có thể chia M thành các khối có độ dài 2. Khối đầu tiên, 08 mã hóa
53
như sau
867 ≡ 148 (mod 377).
Tổng tin nhắn mã hóa đọc như sau:
148216220315300.
Để giải mã tin nhắn, với b, người nhận tính
b331 (mod 377).
Ví dụ, chúng ta có thể giải mã 148:
148331 ≡ 8 (mod 377).
Một ứng dụng thực tế của Định lý nhỏ Fermat xuất hiện trong Contemporary
Abstract Algebra, Sixth Edition, by Joseph A. Gallian [8, p.142]:
Sử dụng kết hợp Định lý Fermat và máy tính để kiểm tra tính nguyên tố của các số tự nhiên. Một trường hợp liên quan đến số p = 2257 − 1. Nếu p là số nguyên tố, theo Định lý Fermat nhỏ thì 10p ≡ 10 (mod p) và do đó 10p+1 ≡ 100 (mod p). Với độ chính xác cao và các vòng lặp đơn giản máy tính sẽ tính toán ra rằng 10p+1 ≡ 102257 (mod p) trong vài giây. Kết quả không phải là 100 modunlo p, và do đó p không là số nguyên tố. Chúng tôi đã chứng minh hai ứng dụng thực tế của Định lý Fermat nhỏ, công
việc mà đã được phát triển trong những năm 1970 và vẫn còn liên quan đến công việc toán học ngày nay.
Định lý Wilson cũng là rất có giá trị vì nó được sử dụng để chứng minh nhiều định lý quan trọng khác. Chứng minh của Dirichlet về Định lý Wilson đã chứng
tỏ điều này. Định lý Wilson có thể được sử dụng để chứng minh tính nguyên tố
của một số nguyên.
Một kết quả thú vị cũng phát sinh khi xem xét về định lý đảo của Định lý
Fermat nhỏ và Định lý Wilson. Định lý 5.1. (Định lý Wilson đảo)
54
Giả sử (p − 1)! ≡ −1 (mod p). Khi đó p là một số nguyên tố. Chứng minh. Giả sử p không là số nguyên tố. Với p = 4 ta có 3! ≡ 2 (mod 4). Giả sử p > 4. Khi đó p có thể được biểu diễn bởi hai số không tầm thường m, n sao cho p = mn. Đầu tiên, giả sử rằng 1 < m < n < p. Khi đó mn phải chia hết (p − 1)!. Khi đó mn (cid:45) [(p − 1)! + 1], và (p − 1)! ≡ 0 (mod p). Tiếp theo, giả sử 1 < m = n < p. Khi đó m|(p − 1)! suy ra m (cid:45) [(p − 1)! + 1]. Khi đó mn (cid:45) [(p − 1)! + 1], và vì 2m < m2 = p, (p − 1)! ≡ 0 (mod p). Do đó trong cả hai trường hợp ta đều thấy mâu thuẫn, vì vậy p là số nguyên tố.
Ta cũng xét đến mệnh đề đảo của Định lý Fermat nhỏ tuy nhiên nó không
đúng. Nói cách khác, mệnh đề sau không đúng: Cho p > 1 là một số tự nhiên, với mọi số tự nhiên a với gcd(a, p) = 1 và ap−1 ≡ 1 (mod p). Khi đó p là một số nguyên tố.
Năm 1909 Carmichael chứng minh được rằng có giá trị của n sao cho an−1 ≡ 1 (mod n) cố định với tất cả số a nguyên tố cùng nhau với n [5, p.94]. Những số n như vậy được đặt tên là số Carmichael. Ví dụ như số 561 = 3 · 11 · 17. Chú ý rằng do gcd(a, 561) = 1 khi đó
(mod 3)
(mod 11)
a560 = (a2)280 ≡ 1 a560 = (a10)56 ≡ 1 a560 = (a16)35 ≡ 1 (mod 17).
theo Định lý phần dư Trung Hoa, a560 ≡ 1 (mod 561).
55
Kết Luận
Một số kết quả chính trong luận văn đã được tác giả thể hiện
(1) Hệ thống các chứng minh ban đầu của Định lý Fermat nhỏ.
(2) Hệ thống các chứng minh ban đầu của Định lý Wilson.
(3) Một dạng mở rộng của Định lý Fermat nhỏ và Định lý Wilson và chứng
minh tương ứng.
(4) Ứng dụng của Định lý Fermat nhỏ và Định lý Wilson.
56
Tài liệu tham khảo
Tài liệu tiếng Việt.
[1] Hà Huy Khoái (2006). Chuyên đề bồi dưỡng số học THPT, NXB Giáo
Dục.
[2] Hà Huy Khoái (2003). Số học thuật toán: Cơ sở lý thuyết và tính toán thực hành, Bộ sách toán cao cấp, Viện Toán học Hà Nội, Trung tâm KHTN và CN Quốc gia.
Tài liệu tiếng Anh.
[3] Benjamin, Arthur T. and Jennifer J. Quinn (2003), Proofs that Really
Count, The Mathematical Association of America.
[4] Dickson, L.E (1952), History of the Theory of Numbers, 1, Chelsea Pub-
lishing Company, New York.
[5] Burtun, David M (1994), Elementary Number Theory, Third Edition, Wm.
C. Brown Publishers.
[6] Comtet, Louis (1974), Advanced Combinatorics, D. Reidel Publishing
Company, Dordrecht, Holland.
[7] Caroline LaRoche Turnage (2008), Selected Proofs of Fermat’s Theorem,
Wake Forest University. Department of Mathematics.
