Luận văn Thạc sĩ Toán học: Ứng dụng của luật thuận nghịch và thặng dư bậc hai

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

Thêm vào BST

Báo xấu

30
lượt xem 5
download

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

Đề tài luận văn "Ứng dụng của luật thuận nghịch và thặng dư bậc hai" có mục đích là hệ thống lại mảng kiến thức liên quan đến luật thuận nghịch và thặng dư bậc hai, từ đó trình bày một số ví dụ ứng dụng hay của chúng nhằm cung cấp một tài liệu tốt để dạy và học chó giáo viên và học sinh trung học phổ thông. Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Ứng dụng của luật thuận nghịch và thặng dư bậc hai

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– ĐỖ THỊ THOA ỨNG DỤNG CỦA LUẬT THUẬN NGHỊCH VÀ THẶNG DƯ BẬC HAI THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– ĐỖ THỊ THOA ỨNG DỤNG CỦA LUẬT THUẬN NGHỊCH VÀ THẶNG DƯ BẬC HAI CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP MÃ SỐ: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. NGUYỄN VĂN HOÀNG THÁI NGUYÊN - 2019
i Mục lục Mở đầu 1 1 Kiến thức chuẩn bị 3 1.1 Định lý Fermat nhỏ và định lý Euler . . . . . . . . . . . . . . . . . 3 1.2 Sơ lược về phương trình đồng dư . . . . . . . . . . . . . . . . . . . 5 2 Ứng dụng của luật thuận nghịch và thặng dư bậc hai 10 2.1 Thặng dư bậc hai và ứng dụng . . . . . . . . . . . . . . . . . . . . 10 2.1.1 Phương trình đồng dư bậc hai . . . . . . . . . . . . . . . . 10 2.1.2 Thặng dư bậc hai . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.3 Tiêu chuẩn Euler và ký hiệu Legendre . . . . . . . . . . . . 16 2.1.4 Bổ đề Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.5 Một số ứng dụng khác . . . . . . . . . . . . . . . . . . . . . 27 2.2 Luật thuận nghịch bậc hai và ứng dụng . . . . . . . . . . . . . . . 32 2.2.1 Luật thuận nghịch bậc hai . . . . . . . . . . . . . . . . . . . 32 2.2.2 Ứng dụng của luật thuận nghịch bậc hai . . . . . . . . . . 37 Kết luận 46 Tài liệu tham khảo 47
1 Mở đầu Có thể nói Số học là lĩnh vực xuất hiện sớm nhất trong lịch sử Toán học, nó ra đời từ khi con người bắt đầu làm việc với những con số. Số học là một phân môn quan trọng trong toán học đã gắn bó với tất cả chúng ta xuyên suốt quá trình học toán từ bậc Tiểu học đến Trung học phổ thông. Sự kì diệu của Số học thường tiềm ẩn những thử thách sâu sắc để thách thức trí tuệ của con người. Trong các thành tựu của số học thì luật thuận nghịch và thặng dư bậc hai là một nội dung quan trọng. Đây là những mảng kiến thức liên quan đến lý thuyết đồng dư và có nhiều ứng dụng trong việc giải các bài toán số học hay và khó liên quan đến tính giải được của phương trình đồng dư bậc hai. Nội dung này cho phép ta xác định tính giải được của phương trình đồng dư bậc hai bất kỳ, tuy nhiên nó không cung cấp một phương pháp hiệu quả để tìm nghiệm. Luật thuận nghịch bậc hai (hay còn gọi là luật thuận nghịch của các thặng dư bậc hai) được tiên đoán bởi Euler và Legendre và lần đầu tiên được chứng minh thuyết phục bởi Gauss. Gauss gọi đó là "định lý vàng" và rất tự hào về nó đến mức ông tiếp tục tìm ra tám chứng minh khác cho nó cho đến cuối đời. Đề tài luận văn "Ứng dụng của luật thuận nghịch và thặng dư bậc hai" có mục đích là hệ thống lại mảng kiến thức liên quan đến luật thuận nghịch và thặng dư bậc hai, từ đó trình bày một số ví dụ ứng dụng hay của chúng nhằm cung cấp một tài liệu tốt để dạy và học cho giáo viên và học sinh phổ thông trung học. Luận văn ngoài phần mở đầu, kết luận thì nội dung chính gồm 2 chương trình bày lại một cách hệ thống về luật thuận nghịch và thặng dư bậc hai cùng một số ứng dụng của chúng, với bố cục cụ thể như sau: Chương 1. Kiến thức chuẩn bị. trình bày phát biểu và chứng minh định
2 lý Fermat nhỏ, định lý Euler. Trình bày khái niệm và cách giải phương trình đồng dư tuyến tính, hệ phương trình đồng dư tuyến tính (định lý thặng dư Trung Hoa). Chương 2. Ứng dụng của luật thuận nghịch và thặng dư bậc hai. Chương 2 trình bày định nghĩa và các tính chất của phương trình đồng dư bậc hai, thặng dư bậc hai, cách tính bằng định nghĩa, cách tính thông qua ký hiệu Legendre, cách tính thông qua luật thuận nghịch bậc hai. Sau đó ứng dụng thặng dư bậc hai và luật thuận nghịch bậc hai để tính toán và giải một số bài toán chứng minh, tìm căn nguyên thủy, kiểm tra tính nguyên tố. Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên. Lời đầu tiên tác giả xin được bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS. Nguyễn Văn Hoàng. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc mắc của tôi trong suốt quá trình làm luận văn. Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy. Tác giả xin chân thành cảm ơn toàn thể các thầy cô trong Khoa Toán - Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã tận tình hướng dẫn, truyền đạt kiến thức trong suốt thời gian theo học, thực hiện và hoàn thành luận văn. Cảm ơn sự giúp đỡ của bạn bè, người thân và các đồng nghiệp trong thời gian làm luận văn. Thái Nguyên, tháng 05 năm 2019 Người viết luận văn Đỗ Thị Thoa
3 Chương 1 Kiến thức chuẩn bị Chương 1 trình bày phát biểu và chứng minh định lý Fermat nhỏ, định lý Euler. Trình bày khái niệm và cách giải phương trình đồng dư tuyến tính, hệ phương trình đồng dư tuyến tính (định lý thặng dư Trung Hoa). Các kiến thức ở chương này giúp việc trình bày ở chương sau được hệ thống và dễ theo dõi hơn. 1.1 Định lý Fermat nhỏ và định lý Euler Mục này trình bày hai định lý quan trọng trong lý thuyết đồng dư là định lý Fermat nhỏ và định lý Euler. Định lý 1.1.1 (Định lý Fermat nhỏ). Cho p là số nguyên tố và a là số nguyên. Nếu p - a thì ap−1 ≡ 1 (mod p). Chứng minh. Xét p − 1 số nguyên a, 2a, 3a, . . . , (p − 1)a. Chú ý rằng p - ia với mọi i = 1, 2, . . . , p − 1 (vì nếu ngược lại, tồn tại 1 ≤ i ≤ p − 1 để p | ia, kéo theo p | a hoặc p | i; nhưng vì p - a, nên ta có p | i điều này mâu thuẫn). Cũng chú ý rằng không có hai số nào trong p − 1 số nguyên a, 2a, 3a, . . . , (p − 1)a đồng dư modulo p (vì nếu ngược lại, thì tồn tại nghịch đảo a0 của a modulo p; nên từ ia ≡ ja (mod p) với i 6= j thì iaa0 ≡ jaa0 (mod p), từ đó i ≡ j (mod p), điều này là không thể). Do đó tập các số dư trong phép chia cho p của các số nguyên a, 2a, 3a, . . . , (p − 1)a phải là {1, 2, 3, . . . , p − 1}. Khi đó, (a)(2a)(3a) · · · (p − 1)a ≡ (1)(2)(3) · · · (p − 1) (mod p)
4 hay tương đương với ap−1 (p − 1)! ≡ (p − 1)! (mod p). Mặt khác ta thấy (p − 1)! và p là hai số nguyên tố cùng nhau, nên từ đồng dư bên trên cho ta thấy ap−1 ≡ 1 (mod p), điều phải chứng minh. Ví dụ 1.1.2. Với a = 3, p = 5 suy ra 34 = 81 ≡ 1 (mod 5). Tương tự, ta tính được 910 ≡ 1 (mod 11). Tiếp theo ta trình bày định lý Euler đó là một dạng tổng quát hoá của định lý Fermat nhỏ. Định lý 1.1.3 (Định lý Euler). Nếu m là số nguyên dương và a là số nguyên sao cho a nguyên tố cùng nhau với m, thì aφ(m) ≡ 1 (mod m), trong đó φ(m) là ký hiệu của phi hàm Euler (hàm này đếm số các số nguyên trong phạm vi từ 1 đến m mà nguyên tố cùng nhau với m). Chứng minh. Gọi r1 , r2 , . . . , rφ(m) là φ(m) số nguyên dương không lớn hơn m sao cho (ri , m) = 1 với i = 1, 2, . . . , φ(m). Xét φ(m) số nguyên xác định bởi r1 a, r2 a, . . . , rφ(m) a. Chú ý rằng (ri a, m) = 1 với mọi i = 1, 2, . . . , φ(m) (vì nếu ngược lại, tồn tại i để (ri a, m) > 1 thì tồn tại ước nguyên tố p của (ri a, m), từ đó p | ri a và p | m. Ta có p | ri a kéo theo p | ri hoặc p | a; nên hoặc ta có p | ri và p | m hoặc ta có p | a và p | m. Nhưng p | ri và p | m là không thể vì (ri , m) = 1; còn lại nếu p | a và p | m thì đó cũng là không thể vì (a, m) = 1). Ngoài ra cũng chú ý rằng không có hai số nào trong các số r1 a, r2 a, . . . , rφ(m) a đồng dư modulo m (vì nếu ngược lại thì do (a, m) = 1, nên tồn tại nghịch đảo modulo a0 của a. Do đó, nếu ri a ≡ rj a (mod m) với i 6= j, kéo theo ri aa0 ≡ rj aa0 (mod m), từ đó ri ≡ rj (mod m), điều này là không thể). Do đó tập các số dư khi chia cho m của các số nguyên r1 a, r2 a, . . . , rφ(m) a là {r1 , r2 , . . . , rφ(m) }. Do đó, ta có (r1 a)(r2 a) · · · (rφ(m) a) ≡ r1 r2 · · · rφ(m) (mod m),
5 hay tương đương với aφ(m) r1 r2 · · · rφ(m) ≡ r1 r2 · · · rφ(m) (mod m). Bây giờ, m | (aφ(m) r1 r2 · · · rφ(m) − r1 r2 · · · rφ(m) ) kéo theo m | (r1 r2 · · · rφ(m) ) × (aφ(m) − 1). Chú ý vì (ri , m) = 1 với i = 1, 2, . . . , φ(m) nên (r1 r2 . . . rφ(m) , m) = 1. Do đó ta suy ra m | (aφ(m) − 1) và do đó aφ(m) ≡ 1 (mod m), điều phải chứng minh. Định lý Euler là tổng quát hóa của định lý nhỏ Fermat vì nếu n = p là số nguyên tố thì φ(p) = p − 1. Định lý này có thể được sử dụng để dễ dàng giản ước với những modulo m rất lớn. Ví dụ 1.1.4. Ví dụ tìm chữ số tận cùng của số 7222 . Giải. Chú ý rằng 7 và 10 là nguyên tố cùng nhau và φ(10) = 4. Bởi vậy 74 ≡ 1 (mod 10). Và ta có 7222 ≡ 74.55+2 72 ≡ 155 72 ≡ 49 ≡ 9 (mod 10). Vậy 7222 có chữ số tận cùng là 9. 1.2 Sơ lược về phương trình đồng dư Định nghĩa 1.2.1. Phương trình đồng dư đại số bậc n là một đồng dư thức có dạng f (x) = a0 xn + a1 xn−1 + . . . + an ≡ 0 (mod m) (1.1) trong đó x là ẩn, ai ∈ Z (với i = 1, 2, . . . , n) và a0 6≡ 0 (mod m). Chú ý 1.2.2. (i) Giải phương trình (1.1) là tìm tất cả các giá trị nguyên của x thoả mãn đồng dư thức (1.1). Nếu x = x0 thoả mãn phương trình (1.1) thì mọi số x ≡ x0 (mod m) đều thoả mãn (1.1); trong trường hợp này tập hợp {x ∈ Z | x ≡ x0 (mod m)} được gọi là một nghiệm của phương trình đồng dư (1.1), kí hiệu là x0 hoặc x ≡ x0 (mod m).
6 (ii) Số nghiệm của phương trình (1.1) là số các phần tử trong một hệ thặng dư đầy đủ theo modulo m mà thỏa mãn (1.1). (iii) Hai phương trình đồng dư được gọi là tương đương nếu tập hợp các số nguyên thỏa mãn các phương trình đó là trùng nhau. Ví dụ 1.2.3. Xét phương trình x2 ≡ 1 (mod 5). Giải. Ta thấy trong các số 0, 1, 2, 3, 4 của hệ thặng dư không âm bé nhất theo modulo 5, có hai số 1 và 4 thỏa mãn phương trình đã cho. Vậy phương trình có hai nghiệm là x ≡ 1 (mod 5) và x ≡ 4 (mod 5). Ví dụ 1.2.4. Giải phương trình đồng dư x4 + 7x + 4 ≡ 0 (mod 9). Giải. Dễ thấy phương trình x4 + 7x + 4 ≡ 0 (mod 3) có nghiệm là x ≡ 1 (mod 3) (hay x = 3t + 1 với t ∈ Z). Thay x vào phương trình cần giải và bỏ đi những số hạng chia hết cho 9 ta được 6t + 3 ≡ 0 (mod 9) ⇔ 2t + 1 ≡ 0 (mod 3) ⇔t≡1 (mod 3) ⇔ t = 3k + 1. Vậy phương trình có nghiệm là x = 3(3k + 1) + 1 hay x ≡ 4 (mod 9). Định nghĩa 1.2.5. Phương trình đồng dư ax ≡ b (mod m) được gọi là phương trình đồng dư tuyến tính với a, b, m là các số nguyên đã biết. Khi đó x ≡ x0 (mod m) là một nghiệm của phương trình khi và chỉ khi ax0 ≡ b (mod m). Định lý 1.2.6 ([6]). Phương trình đồng dư tuyến tính ax ≡ b (mod m) có nghiệm khi và chỉ khi d | b, trong đó d = (a, m). Nếu d | b thì phương trình có d nghiệm. Hệ quả 1.2.7 ([6]). Phương trình đồng dư tuyến tính ax ≡ b (mod m) có nghiệm duy nhất khi và chỉ khi (a, m) = 1. Hệ quả 1.2.8 ([6]). Cho phương trình đồng dư tuyến tính ax ≡ b (mod m) và gọi d = (a, m). Nếu d | b thì d nghiệm modulo m của phương trình là mt (x0 + ) (mod m) với t = 0, 1, 2, . . . , d − 1 d
7 trong đó x0 là một số nguyên thỏa mãn của phương trình ad x ≡ b d (mod m d ). Ví dụ 1.2.9. Giải phương trình đồng dư 12x ≡ 7 (mod 23). Giải. Ta có (12, 23) =1 nên phương trình có nghiệm duy nhất. Phương trình đã cho tương đương với 12x = 23t + 7 (t ∈ Z). Lấy t = 7 suy ra x = 14. Vậy nghiệm của phương trình đã cho là x ≡ 14 (mod 23). Ví dụ 1.2.10. Giải phương trình đồng dư 17x ≡ 13 (mod 11). Giải. Ta có 17 ≡ 6 (mod 11) suy ra 17x ≡ 6x (mod 11). (1.2) Mặt khác 13 ≡ 2 (mod 11). (1.3) Từ (1.2) và (1.3) và theo tính chất bắc cầu ta có 6x ≡ 2 (mod 11). Do (2, 11) =1 nên giản ước hai vế cho 2 ta được 3x ≡ 1 (mod 11) hay 3x = 11t + 1. Lấy t = 1 suy ra x = 4. Do (3, 11) = 1 nên phương trình có nghiệm duy nhất là x ≡ 4 (mod 11). Định lý 1.2.11 (Định lý thặng dư Trung Hoa, [5]). Cho m1 , m2 , . . . , mn là các số nguyên dương đôi một nguyên tố cùng nhau và cho b1 , b2 , . . . , bn là các số nguyên bất kỳ. Khi đó hệ phương trình đồng dư tuyến tính    x ≡ b1 (mod m1 ) x ≡ b2 (mod m2 )   ········· x ≡ bn (mod mn )  có nghiệm duy nhất modulo m1 m2 · · · mn . Chứng minh. Đầu tiên ta xây dựng một số nguyên thỏa mãn hệ đã cho. Đặt M = m1 m2 · · · mn . Với mỗi i = 1, 2, . . . , n đặt Mi = M/mi . Bây giờ với mỗi i = 1, 2, . . . , n ta có (Mi , mi ) = 1. Do đó theo Hệ quả 1.2.7, phương trình Mi x ≡ 1 (mod mi ) có một nghiệm xi (mod mi ). Đặt x = b1 M1 x1 + b2 M2 x2 + · · · + bn Mn xn .
8 Chú ý rằng x là một nghiệm của hệ đã cho vì với mỗi i = 1, 2, . . . , n, ta có x = b1 M1 x1 + b2 M2 x2 + · · · + bn Mn xn ≡ 0 + 0 + · · · + bi + · · · + 0 (mod mi ) ≡ bi (mod mi ). Ta còn phải chứng minh tính duy nhất của nghiệm modulo M . Gọi x0 là một nghiệm khác của hệ. Khi đó, với mọi i, ta có x0 = bi (mod mi ); vì x ≡ bi (mod mi ) với mọi i, ta có x ≡ x0 (mod mi ) với mọi i, hay tương đương, mi | (x − x0 ) với mọi i. Khi đó, M | (x − x0 ), từ đó x ≡ x0 (mod M ). Định lý được chứng minh. Ví dụ 1.2.12. Giải hệ phương trình đồng dư  x ≡ 2 (mod 3) x≡1 (mod 4) x≡3 (mod 5).  Giải. Sử dụng các ký hiệu trong chứng minh của Định lý 1.2.11, ta có M = 3 · 4 · 5 = 60 M 60 M1 = = = 20 m1 3 M 60 M2 = = = 15 m2 4 M 60 M1 = = = 12 m3 5 Ta giải các phương trình đồng dư Mi xi ≡ 1 (mod mi ), i = 1, 2, 3. M1 x1 ≡ 1 (mod m1 ) trở thành 20x1 ≡ 1 (mod 3), hay 2x1 ≡ 1 (mod 3), từ đó x1 ≡ 2 (mod 3). M2 x2 ≡ 1 (mod m2 ) trở thành 15x2 ≡ 1 (mod 4), hay 3x2 ≡ 1 (mod 4), từ đó x2 ≡ 3 (mod 4). Cuối cùng, M3 x3 ≡ 1 (mod m3 ) trở thành 12x3 ≡ 1 (mod 5), hay 2x3 ≡ 1 (mod 5), từ đó x3 ≡ 3 (mod 5). Do đó, ta đặt x1 = 2, x2 = 3, x3 = 3. Cuối cùng, ta tính nghiệm x của hệ x = b1 M1 x1 + b2 M2 x2 + b3 M3 x3
9 = 2 · 20 · 2 + 1 · 15 · 3 + 3 · 12 · 3 = 233 ≡ 53 (mod 60). Vậy 53 (mod 60) là nghiệm của hệ đã cho.
10 Chương 2 Ứng dụng của luật thuận nghịch và thặng dư bậc hai Chương này trình bày định nghĩa và các tính chất của thặng dư bậc hai: cách tính thặng dư bằng định nghĩa, cách tính thặng dư thông qua ký hiệu Legendre, cách tính thông qua luật thuận nghịch bậc hai. Sau đó ứng dụng thặng dư bậc hai và luật thuận nghịch bậc hai để tính toán và giải một số bài toán chứng minh, tìm căn nguyên thủy, kiểm tra tính nguyên tố. 2.1 Thặng dư bậc hai và ứng dụng Thặng dư bậc hai đóng vai trò rất quan trọng trong lý thuyết số. Chẳng hạn, thuật toán phân tích số nguyên ra thừa số nguyên tố. Ngoài ra thặng dư bậc hai cũng ứng dụng lớn trong mật mã cũng như trong các giao thức mã hóa.... Ở đây ta xét ứng dụng liên quan đến giải phương trình đồng dư bậc hai trong lý thuyết và thực hành. 2.1.1 Phương trình đồng dư bậc hai Xét phương trình đồng dư bậc hai theo modulo nguyên tố (theo tài liệu [5]). Ax2 + Bx + C ≡ 0 (mod p), (2.1) trong đó p nguyên tố lẻ và A, B, C ∈ Z với p - A. (Nếu p | A thì quay về phương trình tuyến tính). Vì p nguyên tố lẻ và p - A, nên p - 4A. Ta nhân hai vế của
11 phương trình với 4A ta được 4A(Ax2 + Bx + C) ≡ 0 (mod p). (2.2) Nhưng ta có 4A(Ax2 + Bx + C) = 4A2 x2 + 4ABx + 4AC = (2Ax + B)2 − (B 2 − 4AC). Do đó đồng dư thức (2.2) được viết lại thành (2Ax + B)2 ≡ (B 2 − 4AC) (mod p) nó có dạng y 2 ≡ a (mod p) (2.3) trong đó y = 2Ax + B và a = B 2 − 4AC . Nếu phương trình y 2 ≡ a (mod p) có nghiệm, thì ta suy ra phương trình 2Ax + B = y có nghiệm x modulo p (vì (2A, p) = 1). Do đó phương trình (2.1) có nghiệm nếu và chỉ nếu phương trình (2.3) có nghiệm. Ví dụ sau sẽ minh họa điều này. Ví dụ 2.1.1. Giải phương trình đồng dư bậc hai 3x2 − 4x + 7 ≡ 0 (mod 13). Giải. Nhân hai vế của phương trình với 4.3 = 12 ta được 36x2 − 48x + 84 ≡ 0 (mod 13). Tức là (6x − 4)2 ≡ (16 − 84) (mod 13) (6x − 4)2 ≡ 10 (mod 13) Đặt y = 6x − 4. Khi đó y 2 ≡ 10 (mod 13). Phương trình đồng dư này có chính xác hai nghiệm y ≡ 6 (mod 13) và y ≡ 7 (mod 13). Do đó, các nghiệm của phương trình được cho bởi các phương trình bậc nhất. Ta có 6x − 4 ≡ 6 (mod 13) và 6x − 4 ≡ 7 (mod 13), chúng có hai nghiệm là x ≡ 6 (mod 13) và x ≡ 4 (mod 13).
12 Chú ý rằng ví dụ trên có chính xác hai nghiệm. Nhưng ví dụ tiếp theo chỉ ra rằng không phải mọi phương trình đồng dư bậc hai đều có nghiệm. Ví dụ 2.1.2. Giải phương trình đồng dư bậc hai 3x2 + 7x + 5 ≡ 0 (mod 13). Giải. Ta có 3x2 + 7x + 5 ≡ 0 (mod 13) ⇔ 36x2 + 84x + 60 ≡ 0 (mod 13) ⇔ (6x + 7)2 ≡ (49 − 60) (mod 13) ⇔ (6x + 7)2 ≡ −11 (mod 13) ⇔ (6x + 7)2 ≡ 2 (mod 13). Nhưng không có bình phương của thặng dư dương nhỏ nhất nào theo modulo 13 là bằng 2. Do đó phương trình đã cho không có nghiệm. 2.1.2 Thặng dư bậc hai Từ kết quả trình bày ở Mục 2.1.1, ta thấy rằng có các câu hỏi mới nảy sinh đó là: “Khi nào thì phương trình đồng dư x2 ≡ a (mod p) (đã đề cập ở (2.3)) có nghiệm? Khi phương trình đó có nghiệm, thì số nghiệm của nó là bao nhiêu?” Để dần dần trả lời cho câu hỏi trên ta sẽ tìm hiểu khái niệm thặng dư bậc hai và nghiên cứu tính chất của nó để áp dụng vào giải phương trình đồng dư bậc hai x2 ≡ a (mod p). Trước tiên là định nghĩa thặng dư bậc hai như sau. Định nghĩa 2.1.3 ([5]). Cho m là một số nguyên và a là một số nguyên sao cho (m, a) = 1. Khi đó số a được gọi là một thặng dư bậc hai của m nếu tồn tại một số nguyên x sao cho x2 ≡ a (mod m); trường hợp ngược lại ta nói a thặng dư không bậc hai của m. Chú ý rằng nếu b ≡ a (mod m), và nếu a là một thặng dư bậc hai của m, thì b cũng là một thặng dư bậc hai của m. Do đó, không mất tính tổng quát, ta chỉ cần tập trung vào xét các thặng dư dương nhỏ nhất modulo m. Ví dụ sau đây sẽ minh họa cho định nghĩa trên. Ví dụ 2.1.4. Tìm các thặng dư bậc hai và thặng dư không bậc hai của p = 6.
13 Giải. Ta có 12 ≡ 1 (mod 6) 22 ≡ 4 (mod 6) 33 ≡ 3 (mod 6) 42 ≡ 4 ≡ 22 (mod 6) 52 ≡ 1 (mod 6). Theo đó, 6 có chính xác 3 thặng dư bậc hai là 1, 3, 4. Và nó có 2 thặng dư không bậc hai là 2, 5. Ví dụ 2.1.5. Tìm các thặng dư bậc hai và thặng dư không bậc hai của p = 13. Giải. Ta nhận thấy rằng 12 ≡ 1 ≡ 122 (mod 13) 22 ≡ 4 ≡ 112 (mod 13) 32 ≡ 9 ≡ 102 (mod 13) 42 ≡ 3 ≡ 92 (mod 13) 52 ≡ 12 ≡ 82 (mod 13) 62 ≡ 10 ≡ 72 (mod 13). Theo đó, 13 có chính xác 6 thặng dư bậc hai là 1, 3, 4, 9, 10 và 12; và nó có 6 thặng dư không bậc hai là 2, 5, 6, 7, 8 và 11. Ví dụ 2.1.5 cho ta hai nhận định thú vị sau: • Số nguyên tố 13 có cùng số các thặng dư bậc hai và số thặng dư không bậc hai (đều bằng 6) và • chúng lập thành một phân hoạch của tập hợp các thặng dư dương của 13 (xem Hình 2.1) Hình 2.1: Tập các thặng dư dương của 13
14 Tiếp theo ta sẽ chỉ ra không chỉ riêng số 13 là có cùng con số thặng dư bậc hai và con số thặng dư không bậc hai. Trước hết ta cần bổ đề sau đây. Bổ đề 2.1.6. ([5, Lemma 11.1]) Cho p là số nguyên tố lẻ và a là số nguyên sao cho p - a. Khi đó phương trình đồng dư bậc hai x2 ≡ a (mod p) (2.4) hoặc là vô nghiệm hoặc là có đúng hai nghiệm. Chứng minh. Giả sử α là một nghiệm của phương trình (2.4), ta có α2 ≡ a (mod p). Đặt β = p − α. Khi đó β 2 = (p − α)2 ≡ (−α)2 ≡ α2 ≡ a (mod p). Do đó β cũng là một nghiệm của phương trình đã cho. Ngoài ra, ta thấy α và β không đồng dư với nhau (vì nếu ngược lại β ≡ α (mod p) thì ta có p − α ≡ α (mod p), tức là −α ≡ α (mod p), nên 2α ≡ 0 (mod p). Nhưng ta biết (2, p) = 1, do đó α ≡ 0 (mod p), điều này mâu thuẫn. Do đó α và p − α là hai đại diện cho hai nghiệm của phương trình (2.4). Giả sử phương trình (2.4) còn có nghiệm thứ ba là γ. Khi đó γ 2 ≡ α2 (mod p), suy ra p | (γ 2 − α2 ). Kéo theo γ ≡ α (mod p) hoặc γ ≡ −α (mod p). Điều đó có hệ quả là phương trình đồng dư không có nhiều hơn 2 nghiệm. Định lý 2.1.7. ([5, Theorem 11.1]) Mọi số nguyên tố lẻ p đều có đúng (p − 1)/2 thặng dư bậc hai và (p − 1)/2 thặng dư không bậc hai. Chứng minh. Giả sử p có k thặng dư bậc hai (không đồng dư nhau từng đôi một). Theo Bổ đề 2.1.6, mỗi một thặng dư bậc hai a của p đều kéo theo có 2 nghiệm của phương trình đồng dư x2 ≡ a (mod p); nên tổng số các nghiệm của phương trình đồng dư dạng x2 ≡ a (mod p) là 2k . Nhưng ta đã biết có tất cả p−1 bình phương của các thặng dư dương nhỏ nhất của p (đó là từ 12 , 22 , . . . , (p−1)2 ). Do đó 2k = p − 1, tức là k = (p − 1)/2. Do vậy, có (p − 1)/2 thặng dư bậc hai và (p − 1)/2 thặng dư không bậc hai. Ví dụ 2.1.8. Theo định lý trên ta thấy số p = 17 có (17 − 1)/2 = 8 thặng dư bậc hai là 1, 4, 9, 16, 8, 2, 15, 13 và có 8 thặng dư không bậc hai là 3, 5, 6, 7, 10, 11, 12, 14, bởi vì 12 ≡ 162 ≡ 1 (mod 17) 22 ≡ 152 ≡ 4 (mod 17)
15 32 ≡ 142 ≡ 9 (mod 17) 42 ≡ 132 ≡ 16 (mod 17) 52 ≡ 122 ≡ 8 (mod 17) 62 ≡ 112 ≡ 2 (mod 17) 72 ≡ 102 ≡ 15 (mod 17) 82 ≡ 92 ≡ 13 (mod 17). Tương tự q = 23 có (23 − 1)/2 = 11 thặng dư bậc hai và có 11 thặng dư không bậc hai. Ví dụ 2.1.9. Tìm số thặng dư bậc hai của số nguyên tố Fermat. Giải. Hiện nay, chúng ta mới biết 5 số nguyên tố Fermat ứng với n = 0, 1, 2, 3 và 4. Theo đó, ta có: 0 • Số thặng dư bậc hai của f0 = 22 + 1 = 3 là f0 − 1 3−1 = = 1. 2 2 1 • Số thặng dư bậc hai của f1 = 22 + 1 = 5 là f1 − 1 5−1 = = 2. 2 2 2 • Số thặng dư bậc hai của f2 = 22 + 1 = 17 là f2 − 1 17 − 1 = = 8. 2 2 3 • Số thặng dư bậc hai của f3 = 22 + 1 = 257 là f3 − 1 257 − 1 = = 128. 2 2 4 • Số thặng dư bậc hai của f4 = 22 + 1 = 65537 là 4 4 f4 − 1 22 + 1 − 1 22 4 = = = 22 −1 = 215 . 2 2 2
16 2.1.3 Tiêu chuẩn Euler và ký hiệu Legendre Đến giờ ta vẫn chưa có câu trả lời cho câu hỏi “Khi nào thì phương trình đồng dư x2 ≡ a (mod p) là giải được?” Mục này sẽ tìm hiểu câu trả lời này. Định lý 2.1.10 (Tiêu chuẩn Euler, [5]). Cho p là số nguyên tố lẻ. Khi đó một số nguyên dương a (với p - a) là một thặng dư bậc hai của p khi và chỉ khi a(p−1)/2 ≡ 1 (mod p). Chứng minh. Giả sử a là một thặng dư bậc hai của p. Khi đó phương trình đồng dư x2 ≡ a (mod p) có một nghiệm α, tức là α2 ≡ a (mod p). Rõ ràng là (p, α) = 1, từ đó theo định lý Fermat nhỏ, ta suy ra αp−1 ≡ 1 (mod p). Vì thế cho nên a(p−1)/2 ≡ (α2 )(p−1)/2 = αp−1 ≡ 1 (mod p). Ngược lại, giả sử a(p−1)/2 ≡ 1 (mod p). Do đó p có căn nguyên thủy β (tức là β φ(p) ≡ 1 (mod p) và ordp β = φ(p)). Do đó β (mod p) là phần tử sinh của nhóm Z∗p , do đó tồn tại k để a ≡ β k (mod p). Kéo theo β k(p−1)/2 ≡ a(p−1)/2 ≡ 1 (mod p). Vì β là căn nguyên thủy modulo p, nên ordp β = (p − 1) | k(p − 1)/2. Suy ra k phải là số chẵn, và ta đặt k = 2i. Khi đó a ≡ β 2i ≡ (β i )2 (mod p), nên suy ra a là thặng dư bậc hai của p. Ví dụ 2.1.11. Kiểm tra 10 và 7 có là thặng dư bậc hai của 13 hay không? Giải. Ta có 10(13−1)/2 = 106 ≡ (−3)6 ≡ 1 (mod 13), nên theo tiêu chuẩn Euler ta suy ra 10 là thặng dư bậc hai của 13. Hệ quả là phương trình x2 ≡ 10 (mod 13) có nghiệm. Bây giờ, ta tính toán 7(13−1)/2 (mod 13), ta có 7(13−1)/2 ≡ 76 ≡ (73 )2 ≡ 52 ≡ −1 (mod 13). Vì 76 6≡ 1 (mod 13), nên theo tiêu chuẩn Euler ta suy ra 7 là thặng dư không bậc hai của 13. Chú ý 2.1.12. Trong Định lý 2.1.10, giả sử a(p−1)/2 6≡ 1 (mod p). Khi đó a là thặng dư không bậc hai của p. Khi đó ta có thể nói chính xác những gì về thặng dư nhỏ nhất của a(p−1)/2 modulo p. Để kết thúc điều này, chú ý rằng theo định lý Fermat nhỏ ta có ap−1 ≡ 1 (mod p). Vì p lẻ và ap−1 − 1 = [a(p−1)/2 + 1][a(p−1)/2 − 1], nên ta có hoặc là a(p−1)/2 ≡ 1 (mod p) hoặc là a(p−1)/2 ≡ −1 (mod p). Nhưng vì
17 a(p−1)/2 6≡ 1 (mod p) nên suy ra a(p−1)/2 ≡ −1 (mod p). Do đó, nếu a là thặng dư không bậc hai của p, thì ta phải có a(p−1)/2 ≡ −1 (mod p). Ngược lại, cho a là số nguyên thỏa mãn p - a và a(p−1)/2 ≡ −1 (mod p). Khi đó a không thể là thặng dư bậc hai (vì nếu ngược lại, theo tiêu chuẩn Euler, ta có a(p−1)/2 ≡ 1 (mod p); điều này kéo theo −1 ≡ 1 (mod p), tức là p = 2, mâu thuẫn). Do đó, nếu a(p−1)/2 ≡ −1 (mod p), thì a phải là thặng dư không bậc hai. Các lập luận trên đã chứng minh được kết quả sau. Hệ quả 2.1.13 ([5]). Cho p là số nguyên tố lẻ. Khi đó một số nguyên dương a (với p - a) là thặng dư không bậc hai khi và chỉ khi a(p−1)/2 ≡ −1 (mod p). Ví dụ 2.1.14. Cho số nguyên tố p = 1213. Ta tính được 5(1213−1)/2 ≡ 5606 ≡ (5101 )6 · 56 ≡ (−252)6 · 1069 ≡ 497 · 1069 ≡ −1 (mod 1213). Theo hệ quả trên, 5 là thặng dư không bậc hai của 1213. Chú ý 2.1.15. Như vậy ta đã khẳng định được rằng với một số nguyên tố lẻ p và một số nguyên dương a, ta thấy a là một thặng dư bậc hai của p nếu và chỉ nếu a(p−1)/2 ≡ 1 (mod p); ta cũng thấy a là thặng dư không bậc hai của p nếu và chỉ nếu a(p−1)/2 ≡ −1 (mod p). Theo tiêu chuẩn Euler, phương trình đồng dư (2.4) giải được khi và chỉ khi a(p−1)/2 ≡ 1 (mod p). Mặc dù Định lý 2.1.10 cho ta một công cụ kiểm tra tính giải được của phương trình đồng dư, nhưng công cụ này không khả thi khi số nguyên tố p thực sự lớn. Chẳng hạn, không dễ để áp dụng tiêu chuẩn xác định tính giải được của phương trình x2 ≡ 3797 (mod 7297). Vì vậy, bây giờ ta cần thêm công cụ khác để đơn giản hóa nhiệm vụ kiểm tra tính giải được của thặng dư (2.4), đó là công cụ về “ký hiệu Legendre” sẽ được nghiên cứu tiếp theo sau đây. Định nghĩa 2.1.16 ([5]). Cho p là số nguyên tố lẻ và a là số nguyên bất kỳ sao cho p - a. Ký hiệu Legendre (a/p) được xác định bởi công thức 1 nếu a là thặng dư bậc hai của p (a/p) = −1 cho trường hợp ngược lại