Luận văn Thạc sĩ Toán học: Thặng dư toàn phương và ứng dụng

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

Thêm vào BST

Báo xấu

44
lượt xem 7
download

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

Nội dung chính của luận văn được trình bày trong ba chương: Chương 1 - Đồng dư và phương trình đồng dư; Chương 2 - Thặng dư toàn phương và Chương 3 - Một số ứng dụng của thặng dư toàn phương. Mời các bạn 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: Thặng dư toàn phương và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- PHAN THỊ MỪNG THẶNG DƢ TOÀN PHƢƠNG VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- PHAN THỊ MỪNG THẶNG DƢ TOÀN PHƢƠNG VÀ ỨNG DỤNG 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 GS.TSKH. ĐẶNG HÙNG THẮNG THÁI NGUYÊN - 2019
iii Mục lục Bảng ký hiệu 1 Mở đầu 2 1 Đồng dư và phương trình đồng dư 4 1.1 Đồng dư thức . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Khái niệm đồng dư . . . . . . . . . . . . . . . . . . . 4 1.1.2 Tính chất của đồng dư thức . . . . . . . . . . . . . . 5 1.2 Hệ thặng dư và lớp thặng dư . . . . . . . . . . . . . . . . . . 8 1.3 Định lý Euler và định lý Fermat . . . . . . . . . . . . . . . . 9 1.3.1 Định lý Euler . . . . . . . . . . . . . . . . . . . . . . 9 1.3.2 Định lý Fermat . . . . . . . . . . . . . . . . . . . . . 10 1.4 Phương trình đồng dư một ẩn . . . . . . . . . . . . . . . . . 10 2 Thặng dư toàn phương 14 2.1 Thặng dư toàn phương . . . . . . . . . . . . . . . . . . . . . 14 2.2 Ký hiệu Legendre . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Định luật tương hỗ . . . . . . . . . . . . . . . . . . . . . . . 22 2.4 Ký hiệu Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Một số ứng dụng của thặng dư toàn phương 32 3.1 Kiểm tra tính chất nguyên tố của số Fermat . . . . . . . . . . 32 3.2 Khái niệm số giả nguyên tố Euler . . . . . . . . . . . . . . . 33 3.3 Giải một số bài toán khó trong số học phổ thông . . . . . . . 41 Kết luận 46 Tài liệu tham khảo 47
1 Bảng ký hiệu (a, b): Ước chung lớn nhất của a và b [a, b]: Bội chung lớn nhất của a và b a|b: a là ước của b a 6 |b: a không là ước của b [x]: Phần nguyên của số thực x n P ai : a1 + ... + an i=1 Qn ai : a1 ...an i=1 a ≡ b(modn): a đồng dư với b modulo n a 6≡ b(modn): a không đồng dư với b modulo n ordm a: cấp của a modulo m Fn : Số Fermat thứ n φ(n): Hàm Euler a : Ký hiệu Legendre p a : Ký hiệu Jacobi n
2 Mở đầu Lý thuyết thặng dư - lý thuyết đặc biệt quan trọng trong số học và đã được nhiều nhà Toán học nghiên cứu, vận dụng trong việc giải nhiều bài toán hay, khó và có ứng dụng thực tế. Trong các kì thi Olympic Toán học ở Việt Nam và các nước trên thế giới thì lý thuyết thặng dư là phần được quan tâm đáng kể, vì thế việc có những hiểu biết ban đầu về thặng dư sẽ giúp ta giải nhiều bài toán khó trong số học một cách nhẹ nhàng, ngắn gọn và đẹp. Tuy nhiên, trong nhà trường phổ thông thì thời lượng giảng dạy cho phần lý thuyết thặng dư chưa nhiều nên học sinh thường thấy phần kiến thức này rất khó, vượt ra hiểu biết của các em. Vì vậy để giúp bản thân có những hiểu biết sâu sắc hơn về lý thuyết thặng dư, phục vụ tốt hơn cho công tác bồi dưỡng học sinh giỏi, tôi chọn đề tài "Thặng dư toàn phương và ứng dụng" để nghiên cứu. Ngoài phần mở đầu và kết luận, nội dung chính của luận văn được trình bày trong ba chương: Chương 1. Đồng dư và phương trình đồng dư 1.1. Đồng dư thức 1.2. Hệ thặng dư và lớp thặng dư 1.3. Định lý Euler và định lý Fermat 1.4. Phương trình đồng dư một ẩn Chương 2. Thặng dư toàn phương 2.1. Thặng dư toàn phương 2.2. Ký hiệu Legendre 2.3. Định luật tương hỗ 2.4. Ký hiệu Jacobi
3 Chương 3. Một số ứng dụng của thặng dư toàn phương 3.1. Kiểm tra tính chất nguyên tố của số Fermat 3.2. Khái niệm số giả nguyên tố Euler 3.3. Giải một số bài toán khó trong Số học phổ thông Để hoàn thành bản luận văn này, tôi xin được bày tỏ lòng biết ơn sâu sắc tới GS. TSKH Đặng Hùng Thắng, người thầy nhiệt huyết đã truyền thụ kiến thức, đã chỉ ra hướng đề tài và tận tình hướng dẫn trong suốt quá trình làm luận văn. Đồng thời, tôi xin chân thành cảm ơn các thầy, cô phản biện đã dành thời gian đọc và đóng góp những ý kiến quý báu cho bản luận văn này. Tôi 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. Qua luận văn này, tôi cũng muốn gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ tôi trong thời gian làm luận văn. Mặc dù đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả sự nhiệt tình và năng lực của mình. Tuy nhiên, luận văn không thể tránh khỏi những thiếu sót, tôi rất mong nhận được những đóng góp quý báu của thầy cô và các bạn. Thái Nguyên, ngày 29 tháng 12 năm 2019 Tác giả luận văn Phan Thị Mừng
4 Chương 1 Đồng dư và phương trình đồng dư 1.1 Đồng dư thức 1.1.1 Khái niệm đồng dư Cho trước số tự nhiên m lớn hơn 1. Ta nói các số nguyên a, b đồng dư với nhau theo modulo m nếu khi chia a và b cho m ta được cùng một số dư. Kí hiệu: a ≡ b(modm) (1.1) Nói cách khác, a đồng dư với b theo modulo m nếu a và b biểu diễn được dưới dạng: a = pm + r b = qm + r (0 ≤ r < m) Từ đó suy ra: a ≡ b(modm) khi và chỉ khi m/a − b. khi và chỉ khi tồn tại số nguyên t sao cho a = b + mt. Hệ thức (1.1) được gọi là một đồng dư thức.
5 1.1.2 Tính chất của đồng dư thức a) • a ≡ a(modm)∀a. a ≡ b(modm) • Nếu thì a ≡ c(modm) b ≡ c(modm) a1 ≡ b1 (modm) • Nếu thì a1 ± a2 ≡ b1 ± b2 (modm) a2 ≡ b2 (modm) Chứng minh. Ta chỉ chứng minh với phép toán cộng, phép trừ hoàn toàn tương tự. Từ giả thiết ta có: a1 = b1 + mt1 a2 = b2 + mt2 Cộng từng vế của hai đẳng thức ta có: (a1 + a2 ) = (b1 + b2 ) + m(t1 + t2 ) Chứng tỏ a1 + a2 ≡ b1 + b2 (modm). Từ tính chất này ta suy ra: * Có thể thêm, bớt cùng một số ở hai vế của một đồng dư thức. Nghĩa là: Nếu a ≡ b(modm) thì a + c ≡ b + c(modm) với c là số nguyên tùy ý. * Có thể chuyển vế (phải đổi dấu) các số hạng của một đồng dư thức. Nghĩa là: a + c ≡ b(modm) khi và chỉ khi a ≡ b − c(modm) * Có thể thêm, bớt một vế của đồng dư thức một bội số của m. Nghĩa là: a ≡ b(modm) thì a + tm ≡ b(modm) b) Nếu a1 ≡ b1 (modm) a2 ≡ b2 (modm) thì a1 .a2 ≡ b1 .b2 (modm)
6 Chứng minh. Từ giả thiết ta có: a1 = b1 + mt1 a2 = b2 + mt2 (t1 , t2 ∈ Z) Nhân từng vế của hai đẳng thức ta được: a1 .a2 ≡ b1 .b2 + mT trong đó T là một số nguyên. ⇒ a1 .a2 ≡ b1 .b2 (modm) Từ tính chất này ta có thể suy ra các tính chất sau: * Có thể nhân cả hai vế của một đòng dư thức với cùng một số nguyên. Chính xác hơn: Nếu a ≡ b(modm) thì ak ≡ bk(modm) * Có thể nâng lên lũy thừa nguyên dương hai vế của một đồng dư thức. Tức là: Nếu a ≡ b(modm) thì an ≡ bn (modm) trong đó n nguyên dương bất kì. c) Đặc biệt khi m = p là số nguyên tố, a = a1 .a2 . Ta có khẳng định sau: a ≡ 0(modp) khi và chỉ khi: a1 ≡ 0(modp) a2 ≡ 0(modp) Chứng minh. a ≡ 0(modp) ⇔ p/a ⇔ p/a1 a2 p/a1 ⇔ p/a2 a1 ≡ 0(modp) ⇔ a2 ≡ 0(modp)
7 d) Nếu a ≡ b(modm), d/a, d/b, (d, m) = 1 thì a b = (modm) d d Chứng minh. Giả sử a = a1 d, b = b1 d. Ta có: a ≡ b(modm) ⇒ m/a − b ⇒ m/d(a1 − b1 ), mà (d, m) = 1 nên m/a1 − b1 . ⇒ a1 ≡ b1 (modm). e) a ≡ b(modm) khi và chỉ khi ak ≡ bk(modmk) trong đó k nguyên dương bất kì. Chứng minh. a ≡ b(modm) ⇔ a = b + mt ⇔ ak = bk + mkt ⇔ ak ≡ bk(modmk) a ≡ b(modm1 ) g) Nếu thì a ≡ b(modm) trong đó m = [m1 , m2 ] a ≡ b(modm2 ) Chứng minh. Từ giả thiết ta có: m1 /a − b m2 /a − b tức là a − b là bội chung của m1 và m2 . Theo định nghĩa bội chung nhỏ nhất ta có m/a − b ⇒ a ≡ b(modm) h) Nếu a ≡ b(modm) thì a ≡ b(modd) trong đó d là ước số của m với d > 1. Chứng minh. a ≡ b(modm) ⇒ m/a − b,
8 mà d/hm ⇒ d/a − b. ⇒ a ≡ b(modd). k) Nếu a ≡ b(modm) thì tập hợp các ước số chung của a, m trùng với tập hợp các ước số chung của b, m. Đặc biệt (a, m) = (b, m). Chứng minh. Tính chất này trực tiếp suy ra từ định nghĩa a ≡ b(modm). 1.2 Hệ thặng dư và lớp thặng dư • Xét m là một số nguyên dương lớn hơn 1. Ta có mỗi số nguyên a đều viết được duy nhất dưới dạng a = qm + r, với 0 ≤ r ≤ m − 1. Với mỗi r(0 ≤ r ≤ m − 1), tập hợp Ar tất cả các số nguyên khi chia cho m có cùng số dư r được gọi là lớp thặng dư modulo m và mỗi phần tử của Ar được gọi là một thặng dư modulo m. Vì mỗi số nguyên a, có duy nhất q và r với 0 ≤ r ≤ m − 1 sao cho a = qm + r, nên a thuộc và chỉ thuộc duy nhất một lớp thặng dư modulo m là Ar . Hơn nữa hợp tất cả các lớp thặng dư modulo m chính là tập m−1 S hợp Z các số nguyên. Nghĩa là Ar = Z, r=0 Ai ∩ Aj = φ, với mọi i 6= j, 0 ≤ i, j ≤ m − 1. • Trong mỗi lớp thặng dư modulo m lấy một thặng dư đại diện. Tập hợp m phần tử đó được gọi là một hệ thặng dư đầy đủ modulo m. Nói cách khác, hệ thặng dư đầy đủ modulo m là tập hợp m số nguyên đôi một không đồng dư modulo m. Đặc biệt hệ H = {0, 1, ..., m − 1} được gọi là hệ thặng dư đầy đủ modulo m không âm nhỏ nhất. Nhận xét 1.2.1. Tất cả các số nguyên thuộc một lớp thặng dư modulo m có cùng ước chung lớn nhất với m. Thật vậy, giả sử a, b ∈ Ar , tức là a = q1 m + r, b = q2 m + r(q1 , q2 ∈ Z).
9 Khi đó (a, m) = (q1 m + r, m) = (r, m) = (q2 m + r, m) = (b, m) • Bây giờ đặt ϕ(m) là số các số tự nhiên nhỏ hơn m và nguyên tố với m. Theo nhận xét ở trên có đúng ϕ(m) lớp thặng dư, trong đó mọi thặng dư đều nguyên tố với m. Trong mỗi lớp thặng dư đó lấy một thặng dư đại diện, ta được một hệ thặng dư thu gọn modulo m. Nói cách khác hệ thặng dư thu gọn modulo m là tập hợp gồm ϕ(m) số nguyên, nguyên tố cùng nhau với m và đôi một không đồng dư với nhau modulo m. Nếu tập hợp ϕ(m) phần tử này được chọn từ hệ thặng dư đầy đủ modulo m không âm nhỏ nhất ta được hệ thặng dư thu gọn không âm nhỏ nhất modulo m. 1.3 Định lý Euler và định lý Fermat 1.3.1 Định lý Euler Nếu m > 1 và (a, m) = 1 thì aϕ(m) ≡ 1(modm) Chứng minh. Cho x chạy qua hệ thặng dư thu gọn không âm nhỏ nhất: r1 , r2 , ..., rϕ(m) . Khi đó ax cũng chạy qua một hệ thặng dư thu gọn. Giả sử s1 , s2 , ..., sϕ(m) là các thặng dư không âm nhỏ nhất cùng lớp với ax1 , ax2 , ..., axϕ(m) . Ta có: ar1 ≡ s1 (modm) ar2 ≡ s2 (modm) ... arϕ(m) ≡ sϕ(m) (modm) Nhân từng vế các đồng dư thức ta được: aϕ(m) r1 r2 ...rϕ(m) ≡ s1 s2 ...sϕ(m) (modm) Vì r1 , r2 , ..., rϕ(m) và s1 , s2 , ..., sϕ(m) cùng là hệ thặng dư thu gọn không âm nhỏ nhất nên chúng chỉ khác nhau về thứ tự. Đồng thời mỗi số trong đó đều nguyên tố với m. Chia hai vế của đồng dư thức nhận được cho tích r1 , r2 , ..., rϕ(m) ta được: aϕ(m) ≡ 1(modm) Xét trường hợp đặc biệt của định lý Euler khi m là số nguyên tố và a không chia hết cho m. Khi đó ta có định lý Fermat.
10 1.3.2 Định lý Fermat Nếu p là số nguyên tố và a không chia hết cho p thì: ap−1 ≡ 1(modp) Bằng cách nhân cả hai vế của đồng dư thức này với a ta được một dạng khác của định lý Fermat phát biểu như sau: ap ≡ a(modp) Với p là số nguyên tố và a là số nguyên bất kì (Để ý rằng khi a chia hết cho p định lý hiển nhiên đúng). 1.4 Phương trình đồng dư một ẩn • Đồng dư thức có dạng f (x) ≡ 0(modm) trong đó f (x) = ao xn + a1 xn−1 + ... + an với ao không chia hết cho m, được gọi là phương trình đồng dư bậc n. • Giải một phương trình đồng dư là tìm tất cả các giá trị của ẩn số để khi thay vào, đồng dư thức bằng số được thỏa mãn. Ta cũng nói giá trị đó nghiệm đúng phương trình đồng dư đang xét. Áp dụng các phép biến đổi tương đương đồng dư thức, ta thấy rằng nếu r nghiệm đúng phương trình đồng dư f (x) ≡ 0(modm) thì mọi số cùng lớp thặng dư với r modulo m đều nghiệm đúng phương trình đó. Thật vậy: Giả sử y thuộc lớp thặng dư với r: y ≡ r(modm) ⇒ y i ≡ ri (modm), (i ∈ N) ⇒ an−i y i ≡ an−i ri (modm) với mọi 1 ≤ i ≤ n − 1. Mặt khác an ≡ an (modm) Cộng từng vế n + 1 đồng dư thức ta được:
11 f (y) ≡ f (r)(modm) (Vì f (r) ≡ 0(modm)). ⇒ f (y) ≡ 0(modm) Mỗi lớp đồng dư modulo m như vậy được gọi là một nghiệm của phương trình đồng dư. • Ta có: f (x) ≡ 0(modm) khi và chỉ khi f (x) = mt hay f (x) − mt = 0. Do vậy việc giải phương trình đồng dư f (x) ≡ 0( mod m) tương đương với giải một phương trình bất định dạng f (x) + my = 0. • Xét phương trình đồng dư f (x) ≡ 0(modm), trong đó m = m1 .m2 , (m1 , m2 ) = 1. Theo tính chất g) và h) ở mục 1.1.2, đồng dư thức đang xét tương đương với hệ f (x) ≡ 0(modm1 ) f (x) ≡ 0(modm2 ) Như vậy về nguyên tắc, có thể chuyển việc nghiên cứu các phương trình đồng dư modulo bất kì về việc xét các phương trình đồng dư với modulo là lũy thừa của một số nguyên tố. • Xét phương trình f (x) ≡ 0(modpα ), p ∈ P, a ∈ N, α > 1. Do đó, có thể tìm nghệm của phương trình đồng dư modulo là lũy thừa của một số nguyên tố trong tập hợp các nghiệm của phương trình đồng dư tương tự với modulo là lũy thừa bậc nhỏ hơn của số nguyên tố đó. Ví dụ 1.4.1. Giải phương trình: x4 + 7x + 4 ≡ 0(mod32 )
12 Giải. Xét phương trình x4 + 7x + 4 ≡ 0(mod3). Dễ thấy phương trình có nghiệm là x ≡ 1(mod3). Tức là x = 3t + 1. 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(mod9) ⇔ 2t + 1 ≡ 0(mod3) ⇔ t ≡ 1(mod3) ⇔ t = 3k + 1. Kết luận: Vậy nghiệm của phương trình cần giải là x = 9k + 4, hay x ≡ 4(mod9). • Xét phương trình đồng dư modulo nguyên tố f (x) ≡ 0(modp) có bậc n > p. Bằng cách chia f (x) cho xp − x ta được các đa thức hệ số nguyên g(x) và r(x) sao cho: f (x) = (xp − x).g(x) + r(x) trong đó r(x) có bậc nhỏ hơn p hoặc r(x) = 0. Theo định lý Fermat ta có: xp − x ≡ 0(modp) nên phương trình đang xét hoặc tương đương với r(x) ≡ 0(modp) là phương trình có bậc nhỏ hơn p hoặc nghiệm đúng với mọi x. Do đó, để xét một phương trình đồng dư modulo nguyên tố bậc n bất kì, ta có thể đưa về xét một phương trình có bậc nhỏ hơn p.
13 Chú ý 1.4.2. Nếu phương trình đồng dư có dạng h(x).g(x) ≡ 0(modp) (1.2) trong đó p là một số nguyên tố, theo tính chất c) mục 1.1.2 ta sẽ có g(x) ≡ 0(modp) (1.2) ⇔ h(x) ≡ 0(modp). • Cuối cùng, chỉ cần xét phương trình đồng dư modulo p nguyên tố bậc n < p: f (x) ≡ 0(modp) (1.3) Giả sử x1 nghiệm đúng phương trình, tức là f (x1 ) ≡ 0(modp). Chia f (x) cho (x − x1 ) ta được f (x) = (x − x1 ).f1 (x) + r trong đó f1 (x) là đa thức hệ số nguyên có bậc nhỏ hơn n và hằng số r được xác định bởi r = f (x1 ). Vậy phương trình đang xét tương đương với x − x1 ≡ 0(modp) (x − x1 ).f (x) ≡ 0(modp) ⇔ f1 (x) ≡ 0(modp) Ta lại xét tiếp phương trình f1 (x) ≡ 0(modp), trong đó bậc của f1 (x) nhỏ hơn bậc của f (x)... Nhận xét 1.4.3. Sau mỗi lần chia bậc của phương trình lại nhỏ đi và số nghiệm của phương trình nhiều nhất là bằng số bậc.
14 Chương 2 Thặng dư toàn phương 2.1 Thặng dư toàn phương Định nghĩa 2.1.1. Giả sử m là một số dương, chúng ta nói rằng số nguyên dương a là một thặng dư bậc hai (còn gọi là thặng dư toàn phương) của m nếu (a, m) = 1 và phương trình đồng dư x2 ≡ a(modm) có nghiệm. Giả sử phương trình đồng dư x2 ≡ a(modm) không có nghiệm, ta nói a không phải là thặng dư bậc hai của m. Ví dụ 2.1.2. Để xác định số nguyên nào là thặng dư bậc hai của 11, chúng ta tính bình phương của các số nguyên 1, 2, 3, ..., 10. Chúng ta thấy rằng 12 ≡ 102 ≡ 1(mod11), 22 ≡ 92 ≡ 4(mod11), 32 ≡ 82 ≡ 9(mod11), 42 ≡ 72 ≡ 5(mod11), và 52 ≡ 62 ≡ 3(mod11). Như vậy thặng dư bậc hai của 11 là 1, 3, 4, 5, 9; các số nguyên 2, 6, 7, 8, 10 không phải thặng dư bậc hai của 11. Lưu ý rằng thặng dư bậc hai của thặng dư nguyên dương của m với k = 2. Chúng ta sẽ chỉ ra rằng nếu p là một số nguyên tố lẻ, thì có chính xác có nhiều thặng dư bậc hai như các phần tử bậc hai của p trong số các số nguyên 1, 2, ..., p − 1. Để chứng minh thực tế này, chúng ta sử dụng bổ đề sau đây. Bổ đề 2.1.3. Giả sử p là số nguyên tố lẻ và số nguyên không chia hết cho p. Khi đó, phương trình đồng dư x2 ≡ a(modp) hoặc không có nghiệm hoặc chính xác là có hai nghiệm modulo p. Chứng minh. Nếu x2 ≡ a(modp) là một nghiệm, giả sử x = x0 , thì chúng ta có thể dễ dàng chứng minh rằng nghiệm không phù hợp thứ hai. Vì (−x0 )2 = x20 ≡ a(modp), chúng ta thấy rằng −x0 là một nghiệm. Chúng ta lưu ý rằng x0 6≡ −x0 ( mod p), vì nếu x0 ≡ −x0 ( mod p), thì chúng ta có 2x0 ≡
15 0(modp). Điều này là không thể vì p là số lẻ và p 6 |x0 (sin x20 ≡ a(modp) và p 6 |a). Để chỉ ra rằng không có nhiều hơn hai nghiệm modulo p, giả sử rằng x = x0 và x = x1 là cả hai nghiệm của phương trình đồng dư x2 ≡ a( mod p). Khi đó ta có x20 = x21 ≡ a(modp), do đó x20 − x21 = (x0 + x1 )(x0 − x1 ) ≡ 0(modp). Vì thế, p|(x0 + x1 ) hoặc p|(x0 − x1 ), do đó x1 ≡ −x0 (modp) hoặc x1 ≡ x0 (modp). Vì thế nếu đó là một nghiệm của phương trình đồng dư x2 ≡ a(modp) đó chính xác là có hai nghiệm. Định lý 2.1.4. Nếu p là một số nguyên tố lẻ, thì có đúng (p − 1)/2 thặng dư bậc hai của p và (p − 1)/2 không là thặng dư bậc hai của p trong các số nguyên 1, 2, ..., p − 1 . Chứng minh. Tìm tất cả các thặng dư bậc hai của p trong các số nguyên 1, 2, ..., p − 1 chúng ta tính toán thặng dư nhỏ nhất modulo p của bình phương của các số nguyên 1, 2, ..., p − 1. Vì có p − 1 để xét và phương trình đồng dư x2 ≡ a(modp) có không hoặc hai nghiệm, phải có chính xác một bình phương để xem xét và vì mỗi thặng dư (p − 1)/2 dư của p trong các số nguyên 1, 2, ..., p − 1. Các số nguyên dương p − 1 − (p − 1)/2 = (p − 1)/2 còn lại nhỏ hơn p − 1 là các giá trị không bậc hai của p. Ký hiệu đặc biệt liên quan đến thặng dư bậc hai được mô tả trong định nghĩa sau: 2.2 Ký hiệu Legendre Định nghĩa 2.2.1. (Ký hiệu Legendre) Giả sử p nguyên tố lẻ và a là là số a số nguyên không chia hết cho p. Ký hiệu Legendre được định nghĩa như p sau: a 1 nếu a là thặng dư bậc hai của p = p −1 nếu a không là thặng dư bậc hai của p a Ví dụ 2.2.2. Ví dụ trước cho thấy các ký hiệu Legendre , a = 1, 2, ..., 10, 11 có các giá trị sau: 1 3 4 5 9 = = = = =1 11 11 11 11 11 2 6 7 8 10 = = = = = −1 11 11 11 11 11
16 Định lý 2.2.3. (Tiêu chuẩn của Euler) Giả sử p là số nguyên tố lẻ và để a là số nguyên dương không chia hết cho p. Khi đó a ≡ a(p−1)/2 (modp). p a Chứng minh. Đầu tiên, giả sử rằng = 1. Khi đó, phương trình p đồng dư x2 ≡ a(modp) có một nghiệm, giả sử x = x0 . Sử dụng định lý nhỏ của Fermat, chúng ta thấy a(p−1)/2 = (x20 )(p−1)/2 = xp−1 0 ≡ 1(modp). a a Do đó, nếu = 1, chúng ta biết rằng = a(p−1)/2 (modp). p p a Bây giờ hãy xem xét trường hợp = −1. Khi đó, phương trình đồng dư p x2 ≡ a( mod p) không có nghiệm. Cho mỗi số nguyên i sao cho 1 ≤ i ≤ p − 1, có một số nguyên j duy nhất có 1 ≤ j ≤ p − 1, sao cho ij ≡ a(modp). Hơn nữa, vì phương trình đồng dư x2 ≡ a(modp) không có nghiệm, chúng ta biết rằng i 6= j . Do đó, chúng ta có thể nhóm các số nguyên 1, 2, ..., p − 1 thành (p − 1)/2 cặp với mỗi sản phẩm a. Nhân các cặp này với nhau, chúng ta thấy rằng (p − 1)! ≡ a(p−1)/2 (modp). Vì định lý của Wilson cho chúng ta biết (p − 1)! ≡ −1(modp), chúng ta thấy −1 ≡ a(p−1)/2 (modp). a Trong trường hợp này, chúng ta cũng có = a(p−1)/2 (modp). p Định lý 2.2.4. Giả sử p là số nguyên tố lẻ và số nguyên a, b không chia hết cho p. Khi đó: a b (i) Nếu a ≡ b(modp), thì = . p p a b ab (ii) = . p 2 p p a (iii) = 1. p
17 Chứng minh. (i) Nếu a ≡ b(modp), thì x2 ≡ a(modp) có một nghiệm khi và chỉ khi a b x2 ≡ b(modp) có một nghiệm. Do đó, = . p p a (ii) Theo tiêu chuẩn của Euler, chúng ta biết rằng ≡ a(p−1)/2 (mod p b p), ≡ b(p−1)/2 (modp), p ab ≡ (ab)(p−1)/2 (modp). p Do đó, a b ab ≡ a(p−1)/2 b(p−1)/2 ≡ (ab)(p−1)/2 ≡ (modp). p p p Vì các giá trị duy nhất có thể có của ký hiệu Legendre là ±1, nên chúng ta kết luận rằng a b ab = . p p p a (iii) Vì = ±1, từ phần (ii) ta có p 2 a a a = =1 p p p Phần (ii) của Định lý 2.2.4 có kết quả thú vị sau đây. Tích của hai thặng dư bậc hai là thặng dư bậc hai, hoặc tích của hai thặng dư không bậc hai là thặng dư bậc hai của số nguyên tố, trong khi tích của thặng dư bậc hai và thặng dư không bậc hai là một thặng dư không bậc hai. Sử dụng tiêu chuẩn của Euler, chúng ta có thể phân loại các số nguyên tố đó có −1 là thặng dư bậc hai. Định lý 2.2.5. Nếu p là số nguyên tố lẻ, thì −1 1 nếu p ≡ 1(mod4) = p −1 nếu p ≡ −1(mod4) Chứng minh. Theo tiêu chuẩn của Euler, chúng ta biết rằng −1 = (−1)(p−1)/2 (modp) p