Luận văn Biểu diễn số nguyên tố bởi các dạng toàn phương bậc hai nguyên

Nội dung tài liệu: Luận văn Biểu diễn số nguyên tố bởi các dạng toàn phương bậc hai nguyên

1. - 1 - BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH ” ” ” NGUYỄN HUỲNH NGỌC XUÂN BIỂU DIỄN SỐ NGUYÊN TỐ BỞI CÁC DẠNG TOÀN PHƯƠNG BẬC HAI NGUYÊN Chuyên ngành: Đại số và lý thuyết số Mã số: 604605 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học: PGS.TS. Mỵ Vinh Quang Thành phố Hồ Chí Minh, năm 2006
2. - 2 - MỤC LỤC Trang Trang phụ bìa .............................................................................................................1 Mục lục.......................................................................................................................2 Mở đầu .......................................................................................................................3 Chương 1: Kiến thức cơ bản ....................................................................................4 1.1. Ký hiệu Legrendre ...........................................................................4 1.2 Ký hiệu Jacobi ...................................................................................10 1.3 vành các số nguyên đại số.................................................................11 Chương 2: Tình Euclide của vành các số nguyên đại số bậc hai..............................14 2.1 Miền Euclide .....................................................................................14 2.2 Ví dụ về miền Euclide.......................................................................15 2.3 Ví dụ về miền không Euclide............................................................27 Chương 3: Biểu diễn số nguyên tố dưới dạng toàn phương bậc hai nguyên ............33 3.1 Bổ đề .................................................................................................33 3.2 Bổ đề..................................................................................................34 3.3 Định lý ...............................................................................................36 3.4 Định lý ..............................................................................................37 3.5 Định lý ..............................................................................................39 3.6 Một số hàm số học.............................................................................41 Tài liệu tham khảo .....................................................................................................47
3. - 3 - MỞ ĐẦU Một số nguyên n được gọi là biểu diễn được dưới dạng toàn phương bậc hai nguyên: ax2 + bxy + cy2 (a, b, c ∈ Z) nếu có số nguyên x, y sao cho n = ax2 + bxy + cy2. Bài toán biểu diễn các số nguyên tố dưới dạng toàn phương bậc hai nguyên là một trong những bài toán quan trọng và có nhiều ứng dụng của lý thuyết số. Trong luận văn này chúng tôi nghiên cứu tính Euclide của các vành số nguyêncủa trường mở rộng bậc 2, của trường các số hữu tỉ Q và sau đó ứng dụng nó để nghiên cứu một số cách biểu diễn của số nguyên tố p bởi các dạng toàn phương bậc hai nguyên. Luận văn gồm có 3 chương: Chương 1: Kiến thức cơ bản. Nêu định nghĩa và tính chất của ký hiệu Legendre và Jacobi. Định nghĩa và mô tả vành số nguyên đại số của trường Q ( m ) Chương 2: Tính Euclide của vành các số nguyên đại số bậc hai. Chúng tôi nghiên cứu khi nào vành số nguyên đại số bậc hai là miền Euclide và không là miền Euclide. Chương 3: Biểu diễn số nguyên tố dưới dạng toàn phương bậc hai nguyên. Áp dụng chương 1 và chương 2 để xét xem khi nào số nguyên tố p biểu diễn được dưới dạng toàn phương bậc hai nguyên và cho trước một số n ta có thể tính được bao nhiêu ước d của n có thể biểu diễn được và tổng các ước đó. Tôi xin gởi lời cảm ơn đến các thầy, cô khoa toán trường ĐH Sư phạm TP.HCM và các thầy cô đã tham gia giảng dạy tôi trong suốt quá trình học tập. Đặc biệt là PGS.TS. Mỵ Vinh Quang đã nhiệt tình và dành nhiều thời gian để hướng dẫn, giúp đỡ tôi trong việc chọn đề tài và thực hiện luận văn.
4. - 4 - CHƯƠNG 1: KIẾN THỨC CƠ BẢN 1.1. Ký hiệu Legendre 1.1.1. Định nghĩa Đối với một phương trình đồng dư bậc 2 thì chúng ta hoàn toàn biết được phương trình đó có nghiệm hay không và khi có thì có bao nhiêu nghiệm. Ta cũng có rằng phương trình dạng Ax2 + Bx + C = 0 (mod P) (p là số nguyên tố lẻ) đều có thể đưa về dạng x2 = a (modp) (1). Do đó chúng ta chỉ xét đến dạng (1). Nếu phương trình (1) có nghiệm thì ta nó a là thặng dư bậc hai theo modun p còn nếu phương trình (1) vô nghiệm thì ta nói a là bất thặng dư bậc hai theo modun p. p1− Trong một hệ thặng dư thu gọn theo modun p có thặng dư bậc hai tương ứng 2 2 2 ⎛⎞p1− p1− đồng dư với các số 1, 2 ⎜⎟ và bất thặng dư bậc 2. ⎝⎠2 2 Ví dụ: Tìm thặng dư bậc hai theo modun 5. ⎧⎫2 ⎪⎪22⎛⎞p1− 22 Đặt s’ = ⎨⎬1,2...⎜⎟= 1,2 2 {} ⎩⎭⎪⎪⎝⎠ ⇒ 1, 4 là thặng dư và 2, 3 là bất thặng dư bậc 2 theo modun 5. Tìm thặng dư và bất thặng dư bậc 2 theo modun 7. 222 s’ = {1,2,3} ⇒ Thặng dư bậc 2 theo modun 7 là 1, 4, 2 và 3, 5, 6 là bất thặng dư 2 theo modun 7. Để xét xem phương trình x2 = a (modp), (a;p) = 1 có nghiệm hay không, ⎛⎞a Legendre đã đưa vào ký hiệu ⎜⎟ (ký hiệu Legendre) được xác định như sau: ⎝⎠p ⎛⎞a ⎜⎟ = 1 nếu a là thặng dư bậc 2 theo modun p. ⎝⎠p ⎛⎞a ⎜⎟ = -1 nếu a là bất thặng dư bậc hai theo modun p. ⎝⎠p 1.1.2. Tính chất của ký hiệu Legendre ⎛⎞a p1− 1. ⎜⎟ ≡ a 2 (modp) ⎝⎠p
5. - 5 - ⎛⎞a * Nếu a là thặng dư bậc 2 theo modun p thì ta có ⎜⎟ = 1 hay có x0 sao cho a ≡ ⎝⎠p p1− 2 2 p1− p1− x0 (modp) ⇒ a ≡ x0 (modp), mặt khác (xo, p) =1 nên theo định lý Fecma ta có x0 ≡ p1− p1− 2 p1− ⎛⎞a 2 ⎛⎞a 1 (modp) ⇒ a ≡ x0 ≡ 1 (modp) mà ⎜⎟ = 1 nên a ≡⎜⎟ (modp) ⎝⎠p ⎝⎠p ⎛⎞a p1− Vậy ⎜⎟ ≡ a 2 (modp) ⎝⎠p ⎛⎞a * Nếu a là bất thặng dư bậc 2 theo modun p thì ta có: ⎜⎟ = -1 ⎝⎠p (a, p) = 1 ⇒ ap-1 ≡ 1 (modp) ⎛⎞⎛⎞p1−− p1 ⇔ ⎜⎟⎜⎟a1a122−+ ≡ 0 (modp) ⎝⎠⎝⎠ p1− Ta lại có mọi thặng dư đều thỏa Z12 ≡ (modp) bất thặng dư đều không thỏa p1− Nên a 2 ≡ -1 (modp) (Vì a là bất thặng dư theo modun p) ⎛⎞a p1− Vậy ⎜⎟ ≡ a 2 (modp) ⎝⎠p ⎛⎞a ⎛⎞b 2. Nếu a ≡ b (modp) thì ta có ⎜⎟ = ⎜⎟ ⎝⎠p ⎝⎠p ⎛⎞1 3. ⎜⎟ = 1 với mọi p nguyên tố lẻ. ⎝⎠p Chứng minh: Thật vậy, phương trình x2 ≡ 1 (modp) bao giờ cũng có nghệim. ⎛⎞1 p1− 4. ⎜⎟− = ()−1 2 ⎝⎠p Chứng minh: Áp dụng tính chất (1) với a = -1. Ta có: ⎛⎞1 p1− ⎜⎟−≡−()1 2 (modp) ⎝⎠p Hai vế của đồng dư thức này chỉ lấy giá trị là 1 hoặc -1 và vì p là số nguyên tố lẻ nên 1 và -1 là khác lớp nhau theo modun p do đó ta có ⎛⎞1 p1− ⎜⎟−=−()1 2 ⎝⎠p ⎛⎞⎛⎞⎛⎞⎛⎞⎛⎞a12 a ...a k a 1 a 2a3 a k 5. ⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟= ... ⎝⎠⎝⎠⎝⎠⎝⎠⎝⎠ppppp
6. - 6 - Chứng minh: ⎛⎞a a ...a p1− 12 k 2 Ta có: ⎜⎟≡ ()a12 a ...a k (modp) (tính chất 1) ⎝⎠p p1−− p1 p1 − p1− ⎛⎞a12 a ...a k 22 2 ⎛⎞ai 2 ⇔ ⎜⎟≡ a.a...a12 k (modp) mà ⎜⎟≡ a(modp)i ⎝⎠p ⎝⎠p ⎛⎞⎛⎞⎛⎞⎛⎞a12k12k a ...a a a a nên ⎜⎟⎜⎟⎜⎟⎜⎟≡ ... (modp) ⎝⎠⎝⎠⎝⎠⎝⎠pppp ⎛⎞⎛⎞⎛⎞⎛⎞a12k12k a ...a a a a ⇒ ⎜⎟⎜⎟⎜⎟⎜⎟= ... ⎝⎠⎝⎠⎝⎠⎝⎠pppp ⎛⎞b2 ⎛⎞bbb2 ⎛⎞⎛⎞ ⎡1.1= 1 Hệ quả: ⎜⎟ = 1 vì ⎜⎟= ⎜⎟⎜⎟ = ⎢ ⎝⎠p ⎝⎠ppp⎝⎠⎝⎠ ⎣(1)(1)1− −= ⎛⎞ab2 a ⎛⎞ab22⎛⎞ a ⎛⎞ b ⎛⎞ a ⎛⎞ a ⎜⎟= vì ⎜⎟===⎜⎟ ⎜⎟ ⎜⎟.1 ⎜⎟ ⎝⎠pp⎝⎠pppp⎝⎠ ⎝⎠ ⎝⎠ ⎝⎠ p p1− 6. Bổ đề Gao-xơ: Gọi μ là các số trong dãy a, 2a .a mà có thặng dư giá trị 2 tuyệt đối nhỏ nhất theo modp là âm. ⎛⎞a μ Thế thì ta có: ⎜⎟ = (-1) ⎝⎠p Chứng minh: p1− Đặt p1 = 2 – Ta xét các đồng dư thức: 1.a ≡ ε1r1 (modp) 2.a ≡ ε2r2 (modp) (2) p1a ≡ εp1rp1 (modp) Trong đó: εi = ±1 và 1 ≤ ri ≤ p1. Trong p1 số ε1 có μ số âm, còn lại p1 – μ số dương. Để chứng minh mệnh đề trên ta sẽ ⎛⎞a chứng minh rằng ⎜⎟ = ε1.ε2 εp1 ⎝⎠p
7. - 7 - – Ta hãy xét dãy: a, -a, 2a, -2a p1a, -p1a Đó là một hệ thặng dư thu gọn theo modp, các thặng dư giá trị tuyệt đối nhỏ nhất theo mod p tương ứng là ε1r1, -ε1r1, ε2r2, -ε2r2 εp1rp1, -εp1rp1 Trong đó các thặng dư này phải trùng với các số 1, 2 p1 sai khác một thứ tự, như vậy ta có: r1.r2 rp = 1.2 p1 = p1! Nhân các đồng dư thức (2) từng vế với nhau ta được: p !ap1 ≡εε ... ε .p ! (mod p) 112p11 p1 ⇒ a ≡ ε1 ε2 εp1 (modp) p1− ⎛⎞a 2 p1 ⎛⎞a Mà ⎜⎟≡ a = a (modp) ⇒ ⎜⎟ ≡ ε1 ε2 εp1 (modp) vì hai vế của đống dư thức ⎝⎠p ⎝⎠p chỉ là 1 hoặc -1 và p là số nguyên tố lẻ nên 1 và -1 là hai lớp khác nhau theo modun p ⎛⎞a do đó ta có: ⎜⎟= ε1 ε2 εp1 ⎝⎠p p12 − p1 ⎡⎤ ka ⎛⎞a (a−+ 1) ⎢⎥ 8p∑ 7. ⎜⎟=−()1 k1= ⎣⎦ ⎝⎠p Chứng minh: để chứng minh công thức này ta chứng minh: p12 − p1 ⎡ ka⎤ μ ≡ (a−+ 1) ∑ ⎢ ⎥ (mod 2) 8pk1= ⎣ ⎦ – Ta xét dãy các đẳng thức: a = q1p + γ1 2a = q2p + γ2 (3) P1a = qp1p + γp1, 0 ≤ γi < p p1− Như vậy trong p1 số γi có μ số lớn hơn . Ta còn có γi hoặc bằng ri hoặc bằng 2 p – ri và vì thế ta có: p1 p1 ∑∑γ=iii εr + μp i1== i1 Nếu εi >0 => γi = ri εi γi = p - γi – Như vậy cộng đẳng thức (3) từng vế ta được:
8. - 8 - p1 p1 2 ()p1p11+ ⎡⎤ka p −1 + )1( pp 11 p −1 ap=+ε+μ∑∑⎢⎥ 1ir p(*) vì p 1 = nên = do đó 2pk1==⎣⎦i1 2 2 8 p12 − p1⎡⎤ ka p1 (*) ⇔ a.=+ε+μ p∑∑⎢⎥ 1ir p (4) 8pk1==⎣⎦ i1 Đặt A = ∑ ri ; -B = ∑ ri (A, B > 0) ε>i 0 ε<i 0 p1 2 pp11( + 1) p1− A + B = ∑ r12...p1i =++ + = = i1= 28 p1 p12 − ∑ε=−=+−iirABAB2B = − 2B i1= 8 Thay kết quả này vào đẳng thức (4), ta được: p122−−p1 ⎡⎤ kap1 a.=+− p∑ ⎢⎥ 2B + μp 8p8k1= ⎣⎦ p2 − 1p1⎡⎤ ka p1 ⎡⎤ ka ⇔ ()a1−+ p∑∑⎢⎥ = 2p ⎢⎥ - B + μp 8pk1==⎣⎦ k1 ⎣⎦ p Ta lại có p là số nguyên tố lẻ nên p ≡ 1 (mod2). Lấy đồng dư thức theo modun 2 hai vế của (4) ta được : ⎛⎞p12 − p1 ⎡ ka⎤ μ ≡ (a – 1).⎜⎟+ ∑ ⎢ ⎥ (mod2) ⎝⎠8pk1= ⎣ ⎦ Áp dụng công thức 6 ta được: p12 − p1 ⎡ ka⎤ ⎛⎞a μ−+.a() 1 ⎢ ⎥ 8p∑ ⎜⎟=−()11 =− () k1= ⎣ ⎦ ⎝⎠p ⎛⎞2 p12 − 8. ⎜⎟=−()1 8 ⎝⎠p Chứng minh: Áp dụng công thức 7 với a = 2 p1− Vì k = 1, 2 nên 2 p1− k < ⇒ ak = 2k ≤ (p – 1) < p 2 ⎡⎤ka p1− ⇒ ⎢⎥ = 0, ∀k = 1, 2 ⎣⎦p 2 p12 − p1 ⎡⎤ ka p12 − ⎛⎞2 .2()−+ 1 ⎢⎥ 8p∑ 8 ⎜⎟=−()1 k1= ⎣⎦ = ()−1 ⎝⎠p
9. - 9 - 9. Nếu p, q là hai số nguyên tố lẻ phân biệt thì ta có p1q1−− ⎛⎞qp. ⎛⎞ ⎜⎟=−()1.22 ⎜⎟ ⎝⎠pq ⎝⎠ Chứng minh: p1q1− − ⎛⎞⎛⎞qp . Ta sẽ chứng minh rằng ⎜⎟⎜⎟.1=−()22 ⎝⎠⎝⎠pq Theo công thức 7, ta có: p1−−p1 p12 − 22⎡⎤ kq ⎡⎤kq ⎛⎞q ()q1−+ ⎢⎥ ⎢⎥ 8p∑∑ p ⎜⎟=−()11k1==⎣⎦ =−()k1⎣⎦ (vì (q – 1) là số chẵn) ⎝⎠p p1−− q1 q1− 22⎡kq⎤⎡⎤ lp 2 ∑∑⎢ ⎥⎢⎥+ ⎡⎤lp ⎣ pq⎦⎣⎦ ⎛⎞p ⎢⎥ ⎛⎞⎛⎞qp k1== l1 ∑ q Tương tự: ⎜⎟=−()1 l1= ⎣⎦ nên ⎜⎟⎜⎟.1=−() ⎝⎠q ⎝⎠⎝⎠pq Ta chứng minh: p1−−q1 p1q1−− 22⎡ kq⎤⎡⎤ lp . =+∑∑⎢ ⎥⎢⎥ 22k1==⎣ p⎦⎣⎦l1 q p1q1−− p1− q1− Ta xét . số có dạng kq.lp với k = 1, 2 ; l = 1, 2 22 2 2 Trong đó các số kq - lp đó hiển nhiên không có số nào bằng 0. Gọi số các số dương trong đó là s1 và số các số âm là s2, ta có: p1q1− − s1 + s2 = . 22 p1− Mặt khác ta có s1 là số các số l sao cho kq – lp > 0 với k = 1, 2 nghĩa là số 2 p1− kq p1− 2 ⎡ kq ⎤ các số l sao cho l < , k = 1, 2 ⇒ s1 = ∑ ⎢ ⎥ p 2 k1= ⎣ p ⎦ q1− Và tương tự s2 là số các số k sao cho kq – lp < 0 với l = 1, 2 nghĩa là số 2 q1− lp q1− 2 ⎡lp⎤ các số k sao cho k < với l = 1, 2 ⇒ s2 = ∑ ⎢ ⎥ q 2 l1= ⎣ q ⎦ p1− q1− 2 ⎡⎤kq 2 ⎡⎤lp Vậy s1 + s2 = ∑ ⎢⎥ + ∑ ⎢⎥ k1= ⎣⎦p l1= ⎣⎦q
10. - 10 - p1− q1− p1q1−− 2 ⎡⎤kq 2 ⎡lp⎤ ⇔ . = ∑ ⎢⎥ + ∑ ⎢ ⎥ 22 k1= ⎣⎦p l1= ⎣ q ⎦ p1q1−− ⎛⎞⎛⎞qp . Do đó ta có: ⎜⎟⎜⎟.1=−()22 ⎝⎠⎝⎠pq p1q1−− ⎛⎞qp. ⎛⎞ ⇒ ⎜⎟=−()1.22 ⎜⎟ ⎝⎠pq ⎝⎠ 1.2. Ký hiệu Jacobi 1.2.1. Định nghĩa Cho p là một số lẻ lớn hơn 1 và p = p1.p2 pr là dạng phân tích của p thành thừa số nguyên tố (p1, p2 pr: có thể trùng nhau) và cho (a, p) = 1. Khi đó ký hiệu Jacobi được xác định bởi đẳng thức: ⎛⎞aaaa⎛⎞⎛⎞⎛⎞ ⎜⎟= ⎜⎟⎜⎟⎜⎟... ⎝⎠pppp⎝⎠⎝⎠⎝⎠12 r ⎛⎞a Trong đó ⎜⎟ là ký hiệu Legendre. ⎝⎠pi 1.2.2. Các tính chất ⎛⎞⎛a a1 ⎞ 1. Nếu a ≡ a1 (modp) thì ta có ⎜⎟⎜= ⎟ ⎝⎠⎝pp ⎠ ⎛⎞1 2. ⎜⎟= 1 ⎝⎠p ⎛⎞1 p1− 3. ⎜⎟−=−()1 2 ⎝⎠p ⎛⎞⎛⎞⎛⎞⎛⎞a12 a ...a n a 1 a 2 a n 4. ⎜⎟⎜⎟⎜⎟⎜⎟= ... ⎝⎠⎝⎠⎝⎠⎝⎠pppp ⎛⎞baba22 ⎛ ⎞⎛⎞ Hệ quả: ⎜⎟==1; ⎜ ⎟⎜⎟ ⎝⎠ppp ⎝ ⎠⎝⎠ ⎛⎞2 p12 − 5. ⎜⎟=−()1 8 ⎝⎠p 6. Nếu P, Q là hai số lẻ nguyên tố cùng nhau thì ta có: p1Q1−− ⎛⎞QP. ⎛⎞ ⎜⎟=−()1.22⎜⎟ ⎝⎠PQ⎝⎠