Tài liệu Phương trình diophant trong lớp đồng dư bậc hai và áp dụng

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN THỊ MÁT PHƢƠNG TRÌNH DIOPHANT TRONG LỚP ĐỒNG DƢ BẬC HAI VÀ ÁP DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN THỊ MÁT PHƢƠNG TRÌNH DIOPHANT TRONG LỚP ĐỒNG DƢ BẬC HAI VÀ ÁP DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành : Phƣơng pháp toán sơ cấp Mã số : 60. 46. 01. 13 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. Nguyễn Văn Mậu THÁI NGUYÊN - 2016 i Mục lục MỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 ĐỒNG DƯ VÀ ĐỒNG DƯ BẬC HAI 1 3 1.1 Đồng dư và các lớp đồng dư . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Định lí Euler và định lí Fermat . . . . . . . . . . . . . . . . . . . . 16 1.2.1 Hàm số Euler ϕ(n) . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.2 Định lý Fermat . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Phương pháp đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 MỘT SỐ LỚP PHƯƠNG TRÌNH DIOPHANT TRONG LỚP ĐỒNG DƯ BẬC HAI 28 2.1 Phương trình Pell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Biểu diễn số nguyên dương thành tổng của hai số chính phương . 32 2.3 Phương trình dạng toàn phương ax2 + bxy + cy 2 = n . . . . . . . . 36 3 CÁC DẠNG TOÁN LIÊN QUAN ĐẾN ĐỒNG DƯ BẬC HAI 38 3.1 Một số bài toán tìm nghiệm nguyên của phương trình . . . . . . . 38 3.2 Tính toán tổng và hiệu . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3 Một số bài toán từ các đề thi học sinh giỏi và Olympic các nước . 48 KẾT LUẬN 54 TÀI LIỆU THAM KHẢO 56 1 MỞ ĐẦU Chuyên đề “Phương trình Diophant trong lớp đồng dư bậc hai” là một nội dung quan trọng của số học. Các dạng toán liên quan đến đồng dư thường khó và phức tạp. Trong chương trình trung học phổ thông, những bài toán giải phương trình trong đồng dư thường rất khó và trừu tượng đối với hầu hết học sinh. Trong các kỳ thi học sinh giỏi quốc gia, thi Olympic toán khu vực và quốc tế, các bài toán liên quan đến đồng dư cũng hay được đề cập và thường thuộc loại khó song chưa được dạy nhiều ở phổ thông, ít có trong các tài liệu tham khảo. Các bài toán về đồng dư trong chương trình phổ thông nhiều kiến thức chưa được đề cập đến. Với mong muốn nâng cao trình độ nghiệp vụ chuyên môn, đáp ứng việc bồi dưỡng học sinh giỏi cùng với những lí do trên, tôi chọn đề tài: “Phương trình diophant trong lớp đồng dư bậc hai và áp dụng” để làm đề tài luận văn thạc sĩ của mình. Chuyên đề “Phương trình Diophant trong lớp đồng dư bậc hai và áp dụng” gồm ba chương: Đồng dư và đồng dư bậc hai; Một số lớp phương trình Diophant trong lớp đồng dư bậc hai; các dạng toán liên quan đến đồng dư bậc hai. Các kết quả của luận văn được tham khảo từ [1] đến [7] và các bài toán chọn lọc từ các kì thi học sinh giỏi quốc gia, Olympic quốc tế. Luận văn được hoàn thành dưới sự hướng dẫn khoa học đầy nhiệt tình, nghiêm túc và trách nhiệm của GS. TSKH Nguyễn Văn Mậu. Nhân dịp này, tác giả xin được bày tỏ lòng biết ơn chân thành và kính trọng sâu sắc đối với giáo sư - Người Thầy đã truyền đạt nhiều kiến thức quý báu cùng với kinh nghiệm nghiên cứu khoa học trong suốt thời gian tác giả theo học và nghiên cứu đề 2 tài. Đồng thời tác giả cũng xin bày tỏ lòng biết ơn sâu sắc đến Ban giám hiệu trường Đại học Khoa học - Đại học Thái Nguyên; Phòng Đào tạo, Khoa Toán - Tin, các anh em, bạn bè lớp K8B - Đại học Khoa học - Đại học Thái Nguyên; Ban giám hiệu trường THCS Thành Nhân - Ninh Giang, Hải Dương và gia đình đã tạo mọi điều kiện thuận lợi, động viên tác giả trong suốt quá trình học tập, công tác và thực hiện đề tài luận văn. Thái Nguyên, ngày 15 tháng 5 năm 2016 Tác giả luận văn Nguyễn Thị Mát 3 Chương 1 ĐỒNG DƯ VÀ ĐỒNG DƯ BẬC HAI Trong chương này ta xét các tính chất cơ bản của đồng dư và đồng dư bậc hai và các dạng toán về phép chia hết và phép chia có dư (xem [2]-[5]). 1.1 Đồng dư và các lớp đồng dư Trong phần này ta xét các lớp đồng dư bậc một và bậc hai theo modulo m, trong đó m là số nguyên dương cho trước. Định nghĩa 1.1.1 (xem [2]-[5]). Cho m là một số nguyên dương. Ta nói hai số nguyên a, b là đồng dư với nhau theo modulo m nếu trong phép chia a và b cho m ta được cùng một số dư. Ký hiệu a ≡ b (mod m). (1.1) Hệ thức (1.1) gọi là đồng dư thức. Định lý 1.1.2. Định lý Thue Cho p là một số nguyên tố. Khi đó với mọi số √ nguyên a thỏa mãn p - a luôn tồn tại x, y ∈ {1, 2, . . . , [ p]} sao cho ax ≡ y (mod p) hoặc ax ≡ −y (mod p). Chứng minh. Ta định nghĩa √ √ S = {1, 2, . . . , [ p]} × {1, 2, . . . , [ p]}, 4 √ √ √ S chứa ([ p] + 1)2 cặp có thứ tự. Bình phương hai vế của p < [ p] + 1 ta nhận √ được p < ([ p] + 1)2 , vì thế S có nhiều hơn p phần tử. Giả sử cho trước a ∈ Z sao cho p - a. Do (x, y) biến thiên trên S, cho nên có nhiều hơn p biểu thức dạng ax−y . Lưu ý rằng ax−y là một số nguyên và mọi số nguyên là đồng dư modulo p với duy nhất một phần tử trong FpX = {0, 1, . . . , p−1}. Có p phần tử thuộc FpX và nhiều hơn p biểu thức ax − y . Do đó theo nguyên lý chuồng chim bồ câu, phải có ít nhất hai biểu thức ax − yy cùng đồng dư modulo p. Lấy cặp (x1 , y1 ) 6= (x2 , y2 ) mà ax1 − y1 ≡ ax2 − y2 (mod p). Ta rút gọn để được a(x1 − x2 ) ≡ y1 − y2 (mod p). Đặt x = |x1 − x2 |, y = |y1 − y2 | thì (x, y) ∈ S . Ta muốn loại trừ khả năng x = 0 √ hoặc y = 0 để x, y ∈ {1, 2, . . . , [ p]}. Đầu tiên giả sử x = |x1 − x2 | = 0, tức là x1 = x2 . Khi đó a(x1 − x2 ) = 0 ≡ y1 − y2 √ (mod p). Vì y1 , y2 ∈ {1, 2, . . . , [ p]} nên y1 < p, y2 < p. Khi đó, ta phải có y1 = y2 , mâu thuẫn với (x1 , y1 ) 6= (x2 , y2 ). Bây giờ giả sử y = |y1 − y2 | = 0, do đó y1 = y2 . Khi đó a(x1 − x2 ) ≡ 0 (mod p). Vì p - a nên từ tính chất của các phép toán đồng dư đã nêu trước đây thì x1 − x2 ≡ 0 (mod p). Lập luận tương tự như trên ta kết luận rằng x1 = x2 , mâu thuẫn với (x1 , y1 ) 6= (x2 , y2 ). Như vậy ta có ax ≡ ±y (mod p) và đó là điều cần chứng minh. Tính chất 1.1.3 (xem [2]-[5]). a. Với mọi số nguyên a ta có a ≡ a (mod m). b. Nếu a ≡ b (mod m) thì b ≡ a (mod m). c. Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m). Tính chất 1.1.4 (xem [2]-[5]). Nếu a ≡ b (mod m) và c là một số nguyên tùy ý thì a ± c ≡ b ± c (mod m). Tính chất 1.1.5 (xem [2]-[5]). a. Nếu a1 ≡ a2 (mod m); b1 ≡ b2 (mod m) thì (a1 ± b1 ) ≡ (a2 ± b2 ) (mod m). 5 b. Nếu a1 ≡ a2 (mod m); b1 ≡ b2 (mod m) thì (a1 × b1 ) ≡ (a2 × b2 (mod m). Tính chất 1.1.6 (xem [3]-[5]). a. Nếu a + c ≡ b (mod m) thì a ≡ b − c (mod m). b. Nếu a ≡ b (mod m) thì a + km ≡ a (mod m). c. Nếu a ≡ b (mod m) thì ak ≡ bk (mod m). d. Giả sử f (x) = an xn−1 + · · · + a1 x + a0 là một đa thức với hệ số nguyên. Nếu ta có α ≡ β (mod m) thì ta cũng có f (α) ≡ f (β) (mod m). Đặc biệt nếu ta có f (α) ≡ 0 (mod m) thì ta cũng có f (α+km) ≡ 0 (mod m) (k ∈ Z). Tính chất 1.1.7 (xem [2]-[5]). Nếu ac ≡ bc (mod m) (c, m) = 1 thì a ≡ b (mod m). Tính chất 1.1.8 (xem [2]-[5]). Nếu a ≡ b (mod m) thì ac ≡ bc (mod m). Tính chất 1.1.9 (xem [2]-[5]). Nếu a ≡ b (mod m) và d | (a, b, m) (d > 0) thì ta có a b ≡ d d (mod m ). d Tính chất 1.1.10 (xem [2]-[5]). Nếu a ≡ b (mod mi ), i = 1, 2, 3, . . . k thì a ≡ b (mod m); m = m1 m2 . . . mk . Cho tập A = {a1 , a2 , . . . , an }. Giả sử 0 ≤ ri ≤ n − 1 là số dư khi chia ai cho n. Nếu tập các số dư {r1 , r2 , . . . , rn } trùng với tập {0, 1, . . . , n − 1} thì ta nói A là một hệ thặng dư đầy đủ (modulo n). Dễ thấy: Tập A lập thành một hệ đầy đủ (modulo m) nếu và chỉ nếu i 6= j ⇒ ai 6= aj (mod n). Nếu A = {a1 , a2 , . . . , an } là hệ đầy đủ mod n thì từ định nghĩa dễ suy ra • Với mọi m ∈ Z tồn tại và duy nhất ai ∈ a sao cho ai ≡ m (mod n). • Với mọi a ∈ Z tập A + a = {a1 + a, a2 + a, . . . , an + a}, cũng lập thành hệ đầy đủ mod n. 6 • Nếu c ∈ Z, (c, n) = 1 thì tập cA = {ca1 , ca2 , . . . , can } cũng lập thành hệ đầy đủ mod n. Ví dụ 1.1.11. Cho hai hệ đầy đủ mod n: A = {a1 , a2 , . . . , an } và B = {b1 , b2 , . . . , bn }. Chứng minh rằng nếu n là số chẵn thì tập A + B = {a1 + b1 , . . . , an + bn } không lập thành một hệ đầy đủ mod n. Có thể nói gì nếu n là số lẻ? Lời giải. Ta nhận xét rằng nếu C = {c1 , . . . , cn } là hệ đầy đủ mod n, thì ta có n X c1 ≡ n X i= i=1 i=1 n(n + 1) ≡0 2 (do n chẵn). Ta có n X n X i=1 i=1 (ai + bi ) ≡ ai + n X i=1 = n(n1 ) ≡ 0 bi ≡ n(n + 1) n(n + 1) + 2 2 (mod n). Vậy nên A + B = {a1 + b1 , . . . , an + bn } không lập thành một hệ đầy đủ. Nếu n lẻ thì chưa kết luận được. Nghĩa là A + B có thể là hệ đầy đủ, có thể không là hệ đầy đủ. Chẳng hạn, xét n = 3. Nếu A = {1, 2, 3}, B = {4, 5, 6} thì A + B = {5, 7, 9} là hệ đầy đủ mod 3. Tuy nhiên với B 0 = {5, 4, 6} thì A + B 0 = {6, 6, 9} lại không là hệ đầy đủ mod 3. Ví dụ 1.1.12. Cho hai số nguyên dương m, n và hai tập A = {a1 , . . . , an } và B = {b1 , . . . , bn } trong đó A là hệ đầy đủ mod n và B là hệ đầy đủ mod m. Chứng minh rằng nếu (m, n) > 1 thì tập AB = {ai bj } i = 1, 2, . . . , n, j = 1, 2, . . . , m không lập thành một hệ đầy đủ mod mn. Có thể nói gì nếu (m, n) = 1. Lời giải. Ta có nhận xét sau: Nếu A = {a1 , . . . , an } là hệ đầy đủ mod n và p là n số không chia hết cho p. Thật p vậy, giả sử ai = qi n + ri , 1 ≤ ri ≤ n. Do A là hệ đầy đủ nên các ri phân biệt. Ta uớc nguyên tố của n thì trong A có đúng n − có ai chia hết cho p khi và chỉ khi ri chia hết cho p. Số phần tử của A chia hết cho p bằng số các số nguyên dương k, k ≤ n là bội của n, Dễ thấy số đó là n p đó số các số không chia hết cho p trong A là n − . n . Do p 7 Một phần tử ai bj ∈ AB không chia hết cho p khi và chỉ khi cả ai và bj đều không chia hết cho p. Nếu AB là một hệ đầy đủ mod mn thì từ nhận xét trên ta suy ra đẳng thức mn − mn n m mn mn = (n − )(m − ) ⇔ = 2 . p p p p p Đây là điều vô lý vì p > 1. Nếu (m, n) = 1 thì chưa kết luận được. Nghĩa là A + B có thể là hệ đầy đủ, có thể không là hệ đầy đủ. Ví dụ n = 2, m = 3. Nếu A = {1, 2}, B = {5, 7, 9} thì AB = {5, 7, 9, 10, 14, 18} là hệ đầy đủ mod 6. Nếu A = {1, 2}, B = {5, 6, 7} thì AB = {5, 6, 7, 10, 12, 14} không là hệ đầy đủ mod 6. Ví dụ 1.1.13. Một số nguyên dương T gọi là số tam giác nếu nó có dạng k(k + 1) . Tìm tất cả các số nguyên dương n có tính chất: Tồn tại một hệ 2 đầy đủ mod n gồm n số tam giác. T = Lời giải. Ta chứng minh số n có dạng n = 2s . k(k + 1) . Ta có A là 2 ⇒ (i − j)(2i + 2j − 1) chia hết cho n. i) Nếu n = 2s . Ta xét tập A = {T2i−1 }ni=1 ở đó Tk = hệ đầy đủ mod n vì nếu T2i−1 ≡ T2j−1 Vì n không có ước lẻ nên i − j chia hết cho n. Mâu thuẫn. Đảo lại giả sử tồn tại một hệ đầy đủ A mod n gồm n số tam giác với n = 2s m ở đó m > 1 là số lẻ. Xét tập B = {Ti }m i=1 . Ta chứng minh B là hệ đầy đủ mod m. Thật vậy, lấy x ∈ {1, 2, . . . , m}. Vì A là hệ đầy đủ mod n nên tồn tại số tam giác Tk ∈ A sao cho Tk ≡ x (mod n) ⇒ Tk ≡ (mod m). Giả sử k ≡ i (mod m), i ∈ {1, 2, . . . , m}. Khi đó k(k + 1) ≡ i(i + 1) (mod m). Vì m lẻ nên từ đó suy ra Ti ≡ Tk ≡ x (mod m). Vậy m(m + 1) B là hệ đầy đủ mod m. Nhưng điều này là mâu thuẫn, vì Tm = ≡0 2 m(m − 1) (mod m), Tm−1 = ≡ 0 (mod m). 2 Nhận xét 1.1.14. Ví dụ trên có thể phát biểu dưới dạng một bài toán vui như sau: Một lớp gồm n học sinh đứng thành vòng tròn để chuyền bóng ngược chiều kim đồng hồ theo quy tắc sau: Lớp trưởng (coi là học sinh mang số một) bỏ qua học sinh bên cạnh (học sinh mang số hai) chuyền bóng cho học sinh mang số ba. Học sinh mang số ba có bóng, bỏ qua hai học sinh kế tiếp (mang số bốn và số năm) chuyền bóng cho học sinh mang số sáu. Học sinh mang số sáu có bóng, bỏ qua ba học sinh kế tiếp (mang số 7,8,9) chuyền bóng cho học sinh mang số 8 10 và cứ tiếp tục như thế. Chứng minh rằng nếu n không có ước lẻ thì luôn tồn tại ít nhất một học sinh không bao giờ nhận được bóng. Thật vậy, bằng quy nạp dễ dàng chứng minh được em mang số thứ i nhận được bóng khi và chỉ khi tồn tại k ∈ N∗ để Tk ≡ i (mod n). Như vậy tất cả mọi học sinh đều có bóng khi và chỉ khi tồn tại một hệ đầy đủ mod n gồm các số tam giác. Cho B = {b1 , . . . , bk } là một tập gồm k số nguyên và (bi , n) = 1 với mọi i = 1, 2, . . . , k . Giả sử bi = qi n + ri , 1 ≤ ri < n. Khi đó dễ thấy (ri , n) = 1. Nếu tập {r1 , r2 , . . . , rk } bằng tập K gồm tất cả các số nguyên dương bé hơn n và nguyên tố với n thì B được gọi là hệ thặng dư thu gọn mod n. Dễ thấy một tập B = {b1 , . . . , bk } gồm k số nguyên lập thành một hệ thu gọn khi và chỉ khi 1. (bi , n) = 1; 2. bi ≡ bj (mod n); 3. Số phần tử của B là ϕ(n) ở đó ϕ(n) là hàm Euler. Điều kiện 3) tương đương với 3’. Với mọi số x ∈ Z, (x, n) = tồn tại duy nhất bi ∈ B sao cho x ≡ bi (mod n). Từ định nghĩa ta suy ra nếu B = {b1 , . . . , bk } là một hệ thu gọn mod n, c là số nguyên với (c, n) = 1 thì tập cB = {cb1 , . . . , cbk } cũng là hệ thu gọn mod n. Ví dụ 1.1.15. Cho hai số nguyên dương m, n với (m, n) = 1. Giả sử A = {a1 , . . . , ah } và B = {b1 , . . . , bk } tương ứng là các hệ thu gọn mod m và mod n. Xét tập C = {ai n + bj m}, 1 ≤ i ≤ h, 1 ≤ j ≤ k. a) Chứng minh rằng C là hệ thu gọn mod mn; b) Suy ra công thức tính hàm Euler ϕ(n). Lời giải. a) Đầu tiên ta chứng minh (ai n + bj m, mn) = 1. Giả sử trái lại p là ước nguyên tố chung của ai n + bj m và mn. Do (m, n) = 1 nên chẳng hạn p | n và p không là ước của m. Suy ra p | bj m ⇒ p | bj . Vậy p là ước chung của n và bj , mâu thuẫn. 9 Ta chứng minh 2). Giả sử có a, a0 ∈ A, b, b0 ∈ B sao cho an + bm ≡ a0 n + b0 m (mod mn) ⇒ an ≡ a0 n (mod m) ⇒ a ≡ a0 (mod n) (do (m, n) = 1). Điều này mâu thuẫn. Ta chứng minh 3’). Giả sử (x, mn) = 1. Suy ra (x, m) = 1, (x, n) = 1. Vì (m, n) = 1 nên tập B = {mb1 , . . . , mbk } là hệ thu gọn mod n. Vậy tồn tại b ∈ B để x ≡ mb (mod n). Tương tự tồn tại a ∈ A để x ≡ na (mod m). Từ đó suy ra x ≡ na + mb (mod n), x ≡ na + mb (mod m). Từ đó do (m, n) = 1 ta rút ra x ≡ na + mb (mod mn). b) Theo định nghĩa hàm Euler, ta có h = ϕ(m) · k = ϕ(n) và |C| = ϕ(mn). Từ a) suy ra |C| = hk ⇔ ϕ(mn) = ϕ(m)ϕ(n). Như vậy ϕ(n) là một hàm nhân tính. Nếu p là một số nguyên tố thì i là nguyên tố với ps khi và chỉ khi i không chia hết cho p. Số các số chia hết cho p và không vượt quá ps là ps−1 . Thảnh 1 p thử ϕ(ps ) = ps − ps−1 = ps−1 (p − 1) = ps (1 − ). Nếu n có phân tích nguyên tố n = p1s1 · · · pskk thì do ϕ(n) là hàm nhân tính nên ϕ(n) = ϕ(ps11 ) · · · ϕ(pskk ) 1 1 = ps11 (1 − ) · · · pskk (1 − ) p1 pk 1 1 = n(1 − ) · · · (1 − ). p1 pk Ví dụ 1.1.16. Cho p > 3 là số nguyên tố dạng p = 3k + 2. Chứng minh rằng tập A = {23 − 1, 33 − 1, . . . , p3 − 1} là hệ thu gọn mod p và p Y (i2 + i + 1) ≡ 3 (mod p). i=1 Lời giải. Hiển nhiên mỗi phần tử của A đều không chia hết cho p. Giả sử i3 − 1 ≡ j 3 − 1 (mod p) ⇒ i3 ≡ j 3 (mod p) ⇒ i3k ≡ j 3k (mod p). Theo định lý Fecma, i3k+1 ≡ j 3k+1 ≡ 1 (mod p). Từ đó suy ra i ≡ j ⇒ i = j . Vì ϕ(p) = p−1 = |A| nên A là hệ thu gọn mod p. Vì B = {1, 2, . . . , p − 1} là thu gọn mod p nên ta có p Y 3 (i − 1) ≡ (p − 1)! ⇔ i=2 p Y p Y i=2 i=2 p Y 2 (i − 1) ⇔ (p − 1)! (i2 + i + 1) ≡ (p − 1)! (i + i + 1) ≡ (p − 1)! i=2 (mod p) (mod p) 10 ⇔ p Y (i2 + i + 1) ≡ 1 (mod p). i=2 Suy ra p Y (i2 + i + 1) ≡ 3 (mod p). i=1 Định lý 1.1.17 (Định lý Euler, [5]). Cho n là số nguyên dương và a ∈ Z sao cho (a, n) = 1. Khi đó aϕ(n) ≡ 1 (mod n). Một cách tổng quát, với mọi số nguyên a ∈ Z, ta có an ≡ an−ϕ(n) (mod n). Chứng minh. Lấy một hệ thu gọn B (mod n). Giả sử B = {b1 , . . . bm } ở đó m = ϕ(n). Vì (a, n) = 1 nên tập aB = {ab1 , . . . , abm } cũng là hệ thu gọn (mod n). Thành tử (ab1 )(ab2 ) . . . (abm ) ≡ b1 · b2 · · · bm (mod n). Suy ra am b 1 · b 2 · · · b m ≡ b 1 · b 2 · · · b m (mod n) ⇔ aϕ(n) ≡ 1 (mod n). b) Ta phải chứng minh T = an − an−ϕ(n) = an−ϕ(n) (aϕ(n) − 1) ≡ 0 (mod n). Giả sử n có phân tích tiêu chuẩn n = pt11 · · · ptkk . Với mỗi i cố định ta chứng minh T chia hết cho ptii . Để cho gọn ta đặt p = pi , t = ti . t Nếu (a, p) = 1 theo phần a) ta có aϕ(p ) − 1 chia hết cho pt . Vì hàm ϕ(n) là t nhân tính nên ϕ(n) chia hết cho ϕ(pt ). Suy ra aϕ(n) − 1 chia hết cho aϕ(p ) − 1 do đó aϕ(n) − 1 chia hết cho pt . Vậy T chia hết cho pt . Nếu p | a. Khi đó an−ϕ(n) chia hết cho pn−ϕ(n) . Mặt khác, n − ϕ(n) ≥ t bởi vì có ít nhất t số không nguyên tố với p là p1 , p2 , . . . , pt . Suy ra an−ϕ(n) chi hết cho pt ⇔ T chia hết cho pt . Tóm lại, với mọi i = 1, 2, . . . , k ta đều có T ≡ 0 (mod ptii ), suy ra T chia hết cho n. 11 Hệ quả 1.1.18 ( xem [2]-[5]). Giả sử p là một số nguyên tố và a ∈ Z sao cho (a, p) = 1. Khi đó ap−1 ≡ 1 (mod p). Với số nguyên a bất kỳ ap ≡ a (mod p). Thật vậy, nếu p là số nguyên tố thì ϕ(p) = p − 1. Định nghĩa 1.1.19 (xem [2]-[5]). Ta gọi a là một thặng dư toàn phương mod p nếu tồn tại số nguyên x sao cho x2 ≡ a (mod p). Trái lại nếu không tồn tại số nguyên x để x2 ≡ a (mod p) thì a gọi là bất thặng dư toàn phương (mod p) trong đó a là số nguyên dương và (a, p) = 1. Định lý 1.1.20 (xem [2]-[5]). 1. a là một thặng dư toàn phương (mod p) thì khi và chỉ khi a(p−1)/2 ≡ 1 (mod p). 2. a là bất thặng dư toàn phương (mod p) thì khi và chỉ khi a(p−1)/2 ≡ −1 (mod p). Chứng minh. 1. Giả sử a là một thặng dư toàn phương (mod p), suy ra (a, p) = 1 và a = x2 (mod p). Từ đó ta có (x, p) = 1 ⇒ a(p−1)/2 ≡ (x2 )(p−1)/2 ≡ xp−1 ≡ 1 (mod p) (định lý Fermat). Ngược lại, giả sử a(p−1)/2 ≡ 1 (mod p) ⇒ (a, p) = 1. Giả sử ngược lại với mọi x ∈ Z thì x2 6= a (mod p). Xét Zp = {1, 2, . . . , p − 1}. Với mọi k ∈ Zp thì k, 2k, . . . , (p − 1)k, 0 là hệ thặng dư đầy đủ (mod p). Từ đó tồn tại duy nhất K̃ ∈ Zp sao cho K.K̃ ≡ a (mod p) (K̃ 6= K) Xét 1.2 . . . ..(p − 1)! = 1.1.2.2 . . . . ≡ ap−1/2 ≡ −1 (mod p) (theo định lý Wilson) trái với giả thiết. Vậy tồn tại x ∈ Z sao cho x2 ≡ a (mod p). 2. Giả sử a là bất thặng dư toàn phương (mod p) thế thì a 6= x2 (mod p) với mọi x ∈ Z. Suy ra a(p−1)/2 ≡ (p − 1)! ≡ −1 (mod p) (định lý Wilson). Ngược lại, nếu a(p−1)/2 ≡ −1 suy ra a là bất thặng dư toàn phương (modp) vì nếu không thì a là thặng dư toàn phương. Suy ra a(p−1)/2 ≡ 1 (mod p) trái giả thiết. 12 Hệ quả 1.1.21 ( xem [2]-[5]). 1. TDTP × TDTP = TDTP, 2. TDTP × BTDTP = BTDTP, 3. BTDTP × BTDTP = TDTP. Ở đây TDTP = thặng dư toàn phương BTDTP = bất thặng dư toàn phương. Chứng minh. 1. Giả sử a, b là thặng dư toàn phương (mod p) suy ra a(p−1)/2 ≡ 1 (mod p); b(p−1)/2 ≡ 1 (mod p). Vậy (a.b)(p−1)/2 = a(p−1)/2 .b(p−1)/2 ≡ 1.1 ≡ 1 (mod p). 2. Giả sử a là thặng dư toàn phương (mod p), b là một bất thặng dư toàn phương. Thế thì a(p−1)/2 ≡ 1 (mod p); b(p−1)/2 ≡ −1 (mod p) nên (a.b)(p−1)/2 = a(p−1)/2 .b(p−1)/2 ≡ 1.(−1) ≡ −1 (mod p). 3. Giả sử a, b đều là bất thặng dư toàn phương (mod p). Thế thì a(p−1)/2 ≡ −1 (mod p); b(p−1)/2 ≡ −1 (mod p) nên (a.b)(p−1)/2 = a(p−1)/2 .b(p−1)/2 ≡ (−1).(−1) ≡ 1 (mod p). Định lý 1.1.22. Cho p là số nguyên tố lẻ. Gọi n là số các số chẵn nằm trong p 2 khoảng ( , p) khi đó 2(p−1)/2 ≡ (−1)n (mod p). p 2 Chứng minh. Giả sử r1 , r2 , . . . , rn là tập tất cả các số chẵn trong khoảng ( , p). p 2 p (p − 1) (p − 1) các số chẵn thuộc (0, ). Suy ra m + n = do có cả thảy số chẵn 2 2 2 trong khoảng (0, p) Vì A = s1 , s2 , . . . , sm , p − r1 , p − r2 , . . . , p − rn thuộc khoảng (p − 1) (p − 1) (0, p) có số nên A = 1, 2, ..., . Vậy 2 2 Khi đó p − r1 , p − r2 , ..., p − rn là các số lẻ trong ( , p). Giả sử s1 , s2 , . . . , rm là tập s1 .s2 . . . . .sm .(p − r1 )(p − r2 )...(p − rn ) = p−1 ! 2 13 s1 s2 . . . sm (r1 )(r2 ) . . . (rn ) = (−1)n ≡ p−1 ! (mod p) 2 s1 s2 . . . sm r1 r2 . . . rn = 2 (p−1) 2 .( p−1 )!. 2 Vậy suy ra 2 (p−1) 2 ≡ (−1)n (mod p). Ký hiệu Lagrange: Cho p là số nguyên tố lẻ, a là số nguyên. Khi đó   1 nếu (a, p) = 1 và a là thặng dư toàn phương (mod p)  a  = −1 nếu (a, b) = 1 và a không là thặng dư toàn phương (mod p) p    0 nếu a chia hết cho p. Mệnh đề 1.1.23. 2.  a  b  p p = 1.  ab  p 3. a ≡ b (mod p) thì 4. 5.  a2  p 1 p a p−1 2 (mod p). (mod p). a p = 1 (mod p); = 1 (mod p); p =a =  a2 b   p − 1 p  b p = (mod p) b p = (−1) (mod p) p−1 2 (mod p). a Chứng minh. 1. Nếu a là thặng dư toàn phương mod p thì ta có = p   p−1 p−1 a 1 và a 2 ≡ 1 (mod p). Từ đó suy ra = a 2 (mod p). p a p−1 Nếu a là một bất thặng dư toàn phương mod p thì ta có = −1 và a 2 ≡ −1 p a p−1 (mod p). Từ đó suy ra = a 2 (mod p). p  ab   ab  p−1 p−1 p−1 2. Theo tính chất 1. ta có = (ab) 2 (mod p). Hay = a 2 b 2 p a b  a  b p p−1 p−1 p−1 p−1 (mod p). Mặt khác ta có = a 2 ; = b 2 . Vậy = a 2 b 2 = p p p p  ab  p . 14 3. Như chúng ta đã biết nếu a ≡ b (mod p) thì a, b đồng thời là thặng dư toàn phương (mod p) hoặc đồng thời là bất thặng dư toàn phương (mod p) nên a  b  = . p p 4. Theo tính chất 2. ta có  a2  p  a2 b  p = =  a  a  p p  a2  b  p p = 1, ∀a. = 1. b p = b p . 1 5. Hiển nhiên 1 là thặng dư toàn phương mod p nên = 1. Theo tính chất p  1 p−1 1. ta có − = (−1) 2 (mod p). Hai vế của đồng dư thức này chỉ lấy giá trị p  1 p−1 1 hoặc -1 nhưng vì 1 6= −1 nghĩa là − = (−1) 2 (mod p). p Bổ đề 1.1.24. (Gauss) Cho p là số nguyên tố lẻ, a là số nguyên sao cho (a, p) = p−1 2 . Giả sử ka ≡ kt (mod p). Gọi n là số các số tk mà tk > 1. Xét dãy (ka)k=1 đó a p−1 2 p khi 2 ≡ (−1)n (mod p). p−1 2 Chứng minh. Ký hiệu r1 , r2 , . . . , rn là các thặng dư của dãy (ka)k=1 khi chia p 2 p−1 p . Ta có n + k = và ri 6= sj , ∀i, j. 2 2 Mặt khác ta có p − ri 6= sj , thật vậy nếu p − ri = sj suy ra cho p mà lớn hơn . Còn s1 , s2 , . . . , sk là các thặng dư khi chia cho p mà nhỏ hơn (1.2) sj + ri = p. Mà ta có p−1 2   p−1 (mod p) 1 ≤ β ≤ 2  (mod p) 1 ≤ α ≤ ri = αa sj = βa  (1.3) (1.4) Từ đó suy ra 2 ≤ α + β ≤ p − 1. Từ (1.2) và (1.3) ta có . . . (αa + βa)..p ⇒ a(α + β)..p ⇒ (α + β)..p Vì (a, p) = 1, từ (1.4) và (1.5) suy ra mâu thuẫn vậy ri 6= sj . Ta có p p < ri < p, 0 < p − ri < p, 0 < sj < . 2 2 (1.5) 15 Vậy s1 , s2 , . . . , sk , p − r1 , p − r2 , . . . , p − rn = 1, 2, . . . , p−1 . 2 Suy ra s1 .s2 . . . sk .(p − r1 ).(p − r2 ) . . . (p − rn ) = ⇒ s1 .s2 . . . sk .r1 .r2 .rn ≡ ( p−1 2 Hay Q ka(−1)n k=1 Suy ra a p−1 2 ( ≡ p − 1 2 p−1 )!(−1)n ≡ 2 p − 1 2 ! p−1 )!. 2 ! p − 1 2 !. Suy ra a p−1 2 ≡ (−1)n (mod p). Ta xét một số bài toán liên quan. Bài toán 1.1.25. Cho đa thức P (x) = (x2 − 2)(x2 − 3)(x2 − 6). Chứng minh rằng . với mọi số nguyên tố p đều tìm được số nguyên dương n sao cho P (n)..p. Lời giải. Với p = 2, 3 tương ứng ta chọn n = 2, 3, hiển nhiên thỏa mãn. Giả sử . tồn tại số nguyên tố p > 3 sao cho P (n) 6 ..p ∀n ∈ Z hay (n2 − 2)(n2 − 3)(n2 − 6) 6≡ 0 (mod p) ∀n ∈ Z. Suy ra 2, 3, 6 đều không là số chính phương (mod p), hay 2 p−1 2 2 p−1 2 ≡ −1 (mod p), 3 ·3 p−1 2 p−1 2 ≡ −1 (mod p), 6 p−1 2 ≡ −1 (mod p). Nhưng rõ ràng 6 p−1 2 = ≡ (−1) · (−1) ≡ 1 (mod p). Vô lý. Bài toán 1.1.26. Chứng minh rằng số 2n + 1 không có ước nguyên tố dạng 8k − 1. Lời giải. Giả sử rằng tồn tại số nguyên tố p có dạng 8k − 1 (k ∈ N∗ ) sao cho p | (2n + 1). • Nếu n chẵn, ta có −1 ≡ 2 n 2
2 (modp) ⇒  −1 p  = 1 ⇒ p ≡ 1 (mod4) mâu thuẫn với p có dạng 8k − 1. • Nếu n lẻ, ta có  −2 ≡ 2 n+1 2 2  (modp) ⇒ 1 = −2 p   = −1 p   2 p = (−1) 2 p−1 + p 8−1 2 vô lý do p ≡ −1 (mod 8). Vậy 2n + 1 (n ∈ N) không có ước nguyên tố dạng 8k − 1 (k ∈ N∗ ). = −1, 16 1.2 Định lí Euler và định lí Fermat Trong phần này ta xét hai định lý quan trọng của lý thuyết số, liên quan đến hai định lý đó là hàm số Euler ϕ(n). Bởi vậy trước hết ta nhắc lại định nghĩa hàm số Euler và công thức tính nó. 1.2.1 Hàm số Euler ϕ(n) Định nghĩa 1.2.1. Cho số tự nhiên n ≥ 1. Ta ký hiệu ϕ(n) là số các số tự nhiên bé hơn n và nguyên tố với n. Quy ước ϕ(1) = 1. Định lý 1.2.2. Hàm ϕ(n) có tính chất nhân tính theo nghĩa: Nếu a, b là hai số nguyên tố cùng nhau thì ϕ(ab) = ϕ(a)ϕ(b). Chứng minh. Rõ ràng ta có thể giải thiết a > 1, b > 1. Các số nguyên dương không vượt quá ab được liệt kê như sau: Các số đó sắp thành bảng có dạng 1 2 a+1 a+2 2a + 1 2a + 2 ka + 1 ka + 2 (b − 1)a + 1 (b − 1)a + 2 a .................. 2a 3a .................. (k + 1)a ba ax + y , trong đó 0 ≤ x ≤ b − 1, 1 ≤ y ≤ a. Xét các số ở cột thứ y . Ta có (ax + y, a) = (y, a). Vì một số nguyên tố với ab khi và chỉ khi nó nguyên tố với a và b, do đó các số này phải nằm ở cột thứ y mà (y, a) = 1. Có cả thảy ϕ(a) cột như vậy. Xét một cột thứ y , với (y, a) = 1. Các số ở trong cột này là y, a + y, 2a + y, . . . , (b − 1)a + y. 17 Giả sử rx là số dư khi chia ax + y cho b. Như vậy (ax + y, b) = (rx , b). Dễ dàng thấy rằng vì (a, b) = 1 nên rx1 6= rx2 với x1 6= x2 . Như vậy ta có đẳng thức tập hợp r0 , r1 , . . . , rb−1 = 0, 1, . . . , b − 1. Vậy số các x mà (ax + y, b) = 1 chính là số các x mà (rx , b) = 1 tức chính là ϕ(b). Vậy cả thảy có ϕ(a)ϕ(b) số nguyên tố với a và nguyên tố với b. Đó chính là các số nguyên tố với ab. Nói cách khác ϕ(ab) = ϕ(a)ϕ(b). Từ định lý này ta suy ra công thức tính ϕ(n) như sau. Định lý 1.2.3. Giả sử n = pα1 1 . . . pαk k là phân tích tiêu chuẩn của n > 1. Khi đó      1 1 1 ϕ(n) = n 1 − 1− p1 p2 ... 1 − pk . Chứng minh. Theo định lý 1.2.2, ta có ϕ(n) = ϕ(pα1 1 ) . . . ϕ(pαk k ). Định lý sẽ được chứng minh nếu ta chứng tỏ rằng ứng với p là một số nguyên 1 tố thì ϕ(pα ) = pα (1 − ). Thật vậy, vì p là nguyên tố nên với mỗi k ≤ pα thì p .. (k, p) = 1 hoặc k . p. h pα i α Số các số k ≤ p và là bội của p là = pα−1 . p Vậy 1 ϕ(pα ) = pα − pα−1 = pα (1 − ). p Ví dụ 1.2.4. Với n = 250 = 2.53 thì  1 ϕ(250) = 250 1 − 2  1 1− 5  = 100. Tầm quan trọng của hàm ϕ(n) trong số học được thể hiện trong định lý Euler. Sau đây là một sự suy rộng của định lý Euler. Định lý 1.2.5 (Định lý Euler mở rộng). Cho a và m là hai số tự nhiên. Khi đó ta có: am ≡ am−ϕ(m) (mod m).