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

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

Thêm vào BST

Báo xấu

46
lượt xem 3
download

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

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ên củ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.

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: Biểu diễn số nguyên tố bởi các dạng toàn phương bậc hai nguyên

-1- BOÄ GIAÙO DUÏC VAØ ÑAØO TAÏO TRÖÔØNG ÑAÏI HOÏC SÖ PHAÏM THAØNH PHOÁ HOÀ CHÍ MINH NGUYEÃN HUYØNH NGOÏC XUAÂN BIEÅU DIEÃN SOÁ NGUYEÂN TOÁ BÔÛI CAÙC DAÏNG TOAØN PHÖÔNG BAÄC HAI NGUYEÂN Chuyeân ngaønh: Ñaïi soá vaø lyù thuyeát soá Maõ soá: 604605 LUAÄN VAÊN THAÏC SYÕ TOAÙN HOÏC Ngöôøi höôùng daãn khoa hoïc: PGS.TS. Mî Vinh Quang Thaønh phoá Hoà Chí Minh, naêm 2006
-2- MUÏC LUÏC Trang Trang phuï bìa .............................................................................................................1 Muïc luïc .......................................................................................................................2 Môû ñaàu .......................................................................................................................3 Chöông 1: Kieán thöùc cô baûn ....................................................................................4 1.1. Kyù hieäu Legrendre ...........................................................................4 1.2 Kyù hieäu Jacobi ...................................................................................10 1.3 vaønh caùc soá nguyeân ñaïi soá .................................................................11 Chöông 2: Tình Euclide cuûa vaønh caùc soá nguyeân ñaïi soá baäc hai..............................14 2.1 Mieàn Euclide .....................................................................................14 2.2 Ví duï veà mieàn Euclide .......................................................................15 2.3 Ví duï veà mieàn khoâng Euclide ............................................................27 Chöông 3: Bieåu dieãn soá nguyeân toá döôùi daïng toaøn phöông baäc hai nguyeân ............33 3.1 Boå ñeà .................................................................................................33 3.2 Boå ñeà..................................................................................................34 3.3 Ñònh lyù ...............................................................................................36 3.4 Ñònh lyù ..............................................................................................37 3.5 Ñònh lyù ..............................................................................................39 3.6 Moät soá haøm soá hoïc.............................................................................41 Taøi lieäu tham khaûo .....................................................................................................47
-3- MÔÛ ÑAÀU Moät soá nguyeân n ñöôïc goïi laø bieåu dieãn ñöôïc döôùi daïng toaøn phöông baäc hai nguyeân: ax2 + bxy + cy2 (a, b, c ∈ Z) neáu coù soá nguyeân x, y sao cho n = ax2 + bxy + cy2. Baøi toaùn bieåu dieãn caùc soá nguyeân toá döôùi daïng toaøn phöông baäc hai nguyeân laø moät trong nhöõng baøi toaùn quan troïng vaø coù nhieàu öùng duïng cuûa lyù thuyeát soá. Trong luaän vaên naøy chuùng toâi nghieân cöùu tính Euclide cuûa caùc vaønh soá nguyeâncuûa tröôøng môû roäng baäc 2, cuûa tröôøng caùc soá höõu tæ Q vaø sau ñoù öùng duïng noù ñeå nghieân cöùu moät soá caùch bieåu dieãn cuûa soá nguyeân toá p bôûi caùc daïng toaøn phöông baäc hai nguyeân. Luaän vaên goàm coù 3 chöông: Chöông 1: Kieán thöùc cô baûn. Neâu ñònh nghóa vaø tính chaát cuûa kyù hieäu Legendre vaø Jacobi. Ñònh nghóa vaø moâ taû vaønh soá nguyeân ñaïi soá cuûa tröôøng Q ( m ) Chöông 2: Tính Euclide cuûa vaønh caùc soá nguyeân ñaïi soá baäc hai. Chuùng toâi nghieân cöùu khi naøo vaønh soá nguyeân ñaïi soá baäc hai laø mieàn Euclide vaø khoâng laø mieàn Euclide. Chöông 3: Bieåu dieãn soá nguyeân toá döôùi daïng toaøn phöông baäc hai nguyeân. AÙp duïng chöông 1 vaø chöông 2 ñeå xeùt xem khi naøo soá nguyeân toá p bieåu dieãn ñöôïc döôùi daïng toaøn phöông baäc hai nguyeân vaø cho tröôùc moät soá n ta coù theå tính ñöôïc bao nhieâu öôùc d cuûa n coù theå bieåu dieãn ñöôïc vaø toång caùc öôùc ñoù. Toâi xin gôûi lôøi caûm ôn ñeán caùc thaày, coâ khoa toaùn tröôøng ÑH Sö phaïm TP.HCM vaø caùc thaày coâ ñaõ tham gia giaûng daïy toâi trong suoát quaù trình hoïc taäp. Ñaëc bieät laø PGS.TS. Mî Vinh Quang ñaõ nhieät tình vaø daønh nhieàu thôøi gian ñeå höôùng daãn, giuùp ñôõ toâi trong vieäc choïn ñeà taøi vaø thöïc hieän luaän vaên.
-4- CHÖÔNG 1: KIEÁN THÖÙC CÔ BAÛN 1.1. Kyù hieäu Legendre 1.1.1. Ñònh nghóa Ñoái vôùi moät phöông trình ñoàng dö baäc 2 thì chuùng ta hoaøn toaøn bieát ñöôïc phöông trình ñoù coù nghieäm hay khoâng vaø khi coù thì coù bao nhieâu nghieäm. Ta cuõng coù raèng phöông trình daïng Ax2 + Bx + C = 0 (mod P) (p laø soá nguyeân toá leû) ñeàu coù theå ñöa veà daïng x2 = a (modp) (1). Do ñoù chuùng ta chæ xeùt ñeán daïng (1). Neáu phöông trình (1) coù nghieäm thì ta noù a laø thaëng dö baäc hai theo modun p coøn neáu phöông trình (1) voâ nghieäm thì ta noùi a laø baát thaëng dö baäc hai theo modun p. p −1 Trong moät heä thaëng dö thu goïn theo modun p coù thaëng dö baäc hai töông öùng 2 2 ⎛ p −1 ⎞ p −1 ñoàng dö vôùi caùc soá 1, 22… ⎜ ⎟ vaø baát thaëng dö baäc 2. ⎝ 2 ⎠ 2 Ví duï: Tìm thaëng dö baäc hai theo modun 5. ⎧⎪ 2 2 ⎛ p − 1 ⎞2 ⎫⎪ Ñaët s’ = ⎨1 ,2 ... ⎜ ⎪⎩ 2 ⎟ ⎬ = 1 ,2 ⎝ 2 ⎠ ⎪⎭ 2 { } ⇒ 1, 4 laø thaëng dö vaø 2, 3 laø baát thaëng dö baäc 2 theo modun 5. Tìm thaëng dö vaø baát thaëng dö baäc 2 theo modun 7. { 2 s’ = 1 ,2 ,3 2 2 } ⇒ Thaëng dö baäc 2 theo modun 7 laø 1, 4, 2 vaø 3, 5, 6 laø baát thaëng dö 2 theo modun 7. Ñeå xeùt xem phöông trình x2 = a (modp), (a;p) = 1 coù nghieäm hay khoâng, ⎛a⎞ Legendre ñaõ ñöa vaøo kyù hieäu ⎜ ⎟ (kyù hieäu Legendre) ñöôïc xaùc ñònh nhö sau: ⎝p⎠ ⎛a⎞ ⎜ ⎟ = 1 neáu a laø thaëng dö baäc 2 theo modun p. ⎝p⎠ ⎛a⎞ ⎜ ⎟ = -1 neáu a laø baát thaëng dö baäc hai theo modun p. ⎝p⎠ 1.1.2. Tính chaát cuûa kyù hieäu Legendre p −1 ⎛a⎞ 1. ⎜ ⎟ ≡ a 2 (modp) ⎝p⎠
-5- ⎛a⎞ * Neáu a laø thaëng dö baäc 2 theo modun p thì ta coù ⎜ ⎟ = 1 hay coù x0 sao cho a ≡ ⎝p⎠ p −1 x (modp) ⇒ a 2 0 2 ≡ x 0p−1 (modp), maët khaùc (xo, p) =1 neân theo ñònh lyù Fecma ta coù x 0p−1 ≡ p −1 p −1 ⎛a⎞ ⎛a⎞ 1 (modp) ⇒ a 2 ≡ x 0p−1 ≡ 1 (modp) maø ⎜ ⎟ = 1 neân a 2 ≡ ⎜ ⎟ (modp) ⎝p⎠ p ⎝ ⎠ p −1 ⎛a⎞ Vaäy ⎜ ⎟ ≡ a 2 (modp) ⎝p⎠ ⎛a⎞ * Neáu a laø baát thaëng dö baäc 2 theo modun p thì ta coù: ⎜ ⎟ = -1 ⎝p⎠ (a, p) = 1 ⇒ ap-1 ≡ 1 (modp) ⎛ p2−1 ⎞ ⎛ p2−1 ⎞ ⇔ ⎜ a − 1⎟ ⎜ a + 1⎟ ≡ 0 (modp) ⎝ ⎠⎝ ⎠ p −1 Ta laïi coù moïi thaëng dö ñeàu thoûa Z 2 ≡ 1 (modp) baát thaëng dö ñeàu khoâng thoûa p −1 Neân a 2 ≡ -1 (modp) (Vì a laø baát thaëng dö theo modun p) p −1 ⎛a⎞ Vaäy ⎜ ⎟ ≡ a 2 (modp) ⎝p⎠ ⎛a⎞ ⎛b⎞ 2. Neáu a ≡ b (modp) thì ta coù ⎜ ⎟ = ⎜ ⎟ ⎝p⎠ ⎝p⎠ ⎛1⎞ 3. ⎜ ⎟ = 1 vôùi moïi p nguyeân toá leû. ⎝p⎠ Chöùng minh: Thaät vaäy, phöông trình x2 ≡ 1 (modp) bao giôø cuõng coù ngheäim. ⎛ 1⎞ p −1 4. ⎜ − ⎟ = ( −1) 2 ⎝ p ⎠ Chöùng minh: AÙp duïng tính chaát (1) vôùi a = -1. Ta coù: ⎛ 1⎞ p −1 ⎜ − ⎟ ≡ ( − 1) 2 (modp) ⎝ p⎠ Hai veá cuûa ñoàng dö thöùc naøy chæ laáy giaù trò laø 1 hoaëc -1 vaø vì p laø soá nguyeân toá leû neân 1 vaø -1 laø khaùc lôùp nhau theo modun p do ñoù ta coù ⎛ 1⎞ p −1 ⎜ − ⎟ = ( −1) 2 ⎝ p⎠ ⎛ a1a2 ...ak ⎞ ⎛ a1 ⎞⎛ a2 ⎞ ⎛ a3 ⎞ ⎛ ak ⎞ 5. ⎜ ⎟ = ⎜ ⎟⎜ ⎟ ⎜ ⎟ ... ⎜ ⎟ ⎝ p ⎠ ⎝ p ⎠⎝ p ⎠ ⎝ p ⎠ ⎝ p ⎠
-6- Chöùng minh: ⎛ a1a2 ...ak ⎞ p −1 Ta coù: ⎜ ⎟ ( 1 2 k ) 2 (modp) (tính chaát 1) ≡ a a ...a ⎝ p ⎠ p −1 p −1 p −1 p −1 ⎛ a1a2 ...ak ⎞ ⎛ ai ⎞ ⇔ ⎟ ≡ a1 .a2 ...ak (modp) maø ⎜ ⎟ ≡ ai (mod p) 2 2 2 2 ⎜ ⎝ p ⎠ p ⎝ ⎠ ⎛ a1a2 ...ak ⎞ ⎛ a1 ⎞ ⎛ a2 ⎞ ⎛ ak ⎞ neân ⎜ ⎟ ≡ ⎜ ⎟ ⎜ ⎟ ... ⎜ ⎟ (modp) ⎝ p ⎠ ⎝ p ⎠⎝ p ⎠ ⎝ p ⎠ ⎛ a1a2 ...ak ⎞ ⎛ a1 ⎞ ⎛ a2 ⎞ ⎛ ak ⎞ ⇒ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ... ⎜ ⎟ ⎝ p ⎠ ⎝ p ⎠⎝ p ⎠ ⎝ p ⎠ ⎛ b2 ⎞ ⎛ b2 ⎞ ⎛ b ⎞ ⎛ b ⎞ ⎡1.1 = 1 Heä quaû: ⎜ ⎟ = 1 vì ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ = ⎢ ⎝ p ⎠ ⎝ p ⎠ ⎝ p ⎠ ⎝ p ⎠ ⎣(−1)(−1) = 1 ⎛ ab2 ⎞ a ⎛ ab2 ⎞ ⎛ a ⎞ ⎛ b2 ⎞ ⎛ a ⎞ ⎛a⎞ ⎜ ⎟ = vì ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ .1 = ⎜ ⎟ ⎝ p ⎠ p ⎝ p ⎠ ⎝ p ⎠⎝ p ⎠ ⎝ p ⎠ ⎝p⎠ p −1 6. Boå ñeà Gao-xô: Goïi μ laø caùc soá trong daõy a, 2a… .a maø coù thaëng dö giaù trò 2 tuyeät ñoái nhoû nhaát theo modp laø aâm. ⎛a⎞ Theá thì ta coù: ⎜ ⎟ = (-1)μ ⎝p⎠ Chöùng minh: p −1 Ñaët p1 = 2 – Ta xeùt caùc ñoàng dö thöùc: 1.a ≡ ε1r1 (modp) 2.a ≡ ε2r2 (modp) … (2) p1a ≡ εp1rp1 (modp) Trong ñoù: εi = ±1 vaø 1 ≤ ri ≤ p1. Trong p1 soá ε1 coù μ soá aâm, coøn laïi p1 – μ soá döông. Ñeå chöùng minh meänh ñeà treân ta seõ ⎛a⎞ chöùng minh raèng ⎜ ⎟ = ε1.ε2… εp1 ⎝p⎠
-7- – Ta haõy xeùt daõy: a, -a, 2a, -2a… p1a, -p1a Ñoù laø moät heä thaëng dö thu goïn theo modp, caùc thaëng dö giaù trò tuyeät ñoái nhoû nhaát theo mod p töông öùng laø ε1r1, -ε1r1, ε2r2, -ε2r2… εp1rp1, -εp1rp1 Trong ñoù caùc thaëng dö naøy phaûi truøng vôùi caùc soá 1, 2… p1 sai khaùc moät thöù töï, nhö vaäy ta coù: r1.r2… rp = 1.2… p1 = p1! Nhaân caùc ñoàng dö thöùc (2) töøng veá vôùi nhau ta ñöôïc: p1 !a ≡ ε1ε 2 ...ε p .p1 ! (mod p) p1 1 ⇒ ap1 ≡ ε1 ε2…εp1 (modp) p −1 ⎛a⎞ ⎛a⎞ Maø ⎜ ⎟ ≡ a 2 = ap1 (modp) ⇒ ⎜ ⎟ ≡ ε1 ε2…εp1 (modp) vì hai veá cuûa ñoáng dö thöùc ⎝p⎠ ⎝p⎠ chæ laø 1 hoaëc -1 vaø p laø soá nguyeân toá leû neân 1 vaø -1 laø hai lôùp khaùc nhau theo modun p ⎛a⎞ do ñoù ta coù: ⎜ ⎟ = ε1 ε2…εp1 ⎝p⎠ p1 ⎛a⎞ 2 p −1 ⎡ ka ⎤ (a −1)+ ∑ ⎢ ⎥ 7. ⎜ ⎟ = ( −1) 8 k =1 ⎣ p⎦ ⎝p⎠ Chöùng minh: ñeå chöùng minh coâng thöùc naøy ta chöùng minh: p2 − 1 p1 ⎡ ka ⎤ μ≡ (a − 1) + ∑ ⎢ ⎥ (mod 2) 8 k =1 ⎣ p ⎦ – Ta xeùt daõy caùc ñaúng thöùc: a = q1p + γ1 2a = q2p + γ2 (3) … P1a = qp1p + γp1, 0 ≤ γi < p p −1 Nhö vaäy trong p1 soá γi coù μ soá lôùn hôn . Ta coøn coù γi hoaëc baèng ri hoaëc baèng 2 p – ri vaø vì theá ta coù: p1 p1 ∑ γ i = ∑ εi ri + μp i =1 i =1 Neáu εi >0 => γi = ri εi γi = p - γi – Nhö vaäy coäng ñaúng thöùc (3) töøng veá ta ñöôïc:
-8- ( p1 + 1) p1 a = p p1 ⎡ ka ⎤ + p1 p −1 ( p1 + 1) p1 p 2 − 1 2 ∑ ⎢ ⎥ ∑ ε1ri + μp (*) vì p 1 = 2 neân k =1 ⎣ p ⎦ i =1 2 = 8 do ñoù p2 − 1 p1 ⎡ ka ⎤ p1 (*) ⇔ a. = p∑ ⎢ ⎥ + ∑ ε1ri + μp (4) 8 k =1 ⎣ p ⎦ i =1 Ñaët A= ∑ r ; -B = ∑ r εi > 0 i εi < 0 i (A, B > 0) p1 p1 ( p1 + 1) p2 − 1 A + B = ∑ ri = 1 + 2 + ... + p1 = = i =1 2 8 p1 p2 − 1 ∑ ε r = A − B = A + B − 2B = i =1 i i 8 − 2B Thay keát quaû naøy vaøo ñaúng thöùc (4), ta ñöôïc: p2 − 1 p1 ⎡ ka ⎤ p2 − 1 a. = p∑ ⎢ ⎥ + − 2B + μp 8 k =1 ⎣ p ⎦ 8 p2 − 1 p1 ⎡ ka ⎤ p1 ⎡ ka ⎤ ⇔ ( a − 1) + p∑ ⎢ ⎥ = 2p∑ ⎢ ⎥ - B + μp 8 k =1 ⎣ p ⎦ k =1 ⎣ p ⎦ Ta laïi coù p laø soá nguyeân toá leû neân p ≡ 1 (mod2). Laáy ñoàng dö thöùc theo modun 2 hai veá cuûa (4) ta ñöôïc : ⎛ p2 − 1 ⎞ p1 ⎡ ka ⎤ μ ≡ (a – 1). ⎜ ⎟+∑⎢ ⎥ (mod2) ⎝ 8 ⎠ k =1 ⎣ p ⎦ AÙp duïng coâng thöùc 6 ta ñöôïc: p1 ⎛a⎞ 2 p −1 ⎡ ka ⎤ .( a −1) + ∑ ⎢ ⎥ ( ) ( ) μ ⎜ ⎟ = − 1 = −1 8 k =1 ⎣p⎦ p ⎝ ⎠ ⎛2⎞ p2 −1 8. ⎜ ⎟ = ( −1) 8 ⎝p⎠ Chöùng minh: AÙp duïng coâng thöùc 7 vôùi a = 2 p −1 Vì k = 1, 2… neân 2 p −1 k< ⇒ ak = 2k ≤ (p – 1) < p 2 ⎡ ka ⎤ p −1 ⇒ ⎢ p ⎥ = 0, ∀k = 1, 2… 2 ⎣ ⎦ p1 ⎛2⎞ 2 2 p −1 ⎡ ka ⎤ p −1 .( 2 −1) + ∑ ⎢ ⎥ ⎜ ⎟ = ( − 1) 8 k =1 ⎣ p ⎦ = ( −1) 8 ⎝p⎠
-9- 9. Neáu p, q laø hai soá nguyeân toá leû phaân bieät thì ta coù ⎛q⎞ p −1 q −1 ⎛p⎞ ⎜ ⎟ = ( −1) 2 2 . ⎜ ⎟ . ⎝p⎠ ⎝q⎠ Chöùng minh: ⎛q⎞ ⎛p⎞ p −1 q −1 Ta seõ chöùng minh raèng ⎜ ⎟ . ⎜ ⎟ = ( −1) . 2 2 ⎝p⎠ ⎝q⎠ Theo coâng thöùc 7, ta coù: p−1 p−1 ⎛q⎞ p2 −1 2 2 ⎡ kq ⎤ ⎡ kq ⎤ ∑ ( q −1) + ⎢ ⎥ = ( −1)∑ ⎜ ⎟ = ( −1) p ⎦ (vì (q – 1) laø soá chaün) ⎢ ⎥ 8 k =1 ⎣ p⎦ k =1 ⎣ ⎝p⎠ p−1 q −1 q−1 2 ⎡ kq ⎤ 2 ⎡ lp ⎤ ⎛p⎞ ⎛q⎞ ⎛p⎞ 2 ∑ ⎢ ⎥+ ∑ ⎢ ⎥ ⎡ lp ⎤ Töông töï: ⎜ ⎟ = ( −1)∑ ⎢⎣ q ⎥⎦ neân ⎜ ⎟ . ⎜ ⎟ = ( −1) k =1 ⎣ p ⎦ l=1 ⎣ q ⎦ l=1 ⎝q⎠ ⎝p⎠ ⎝q⎠ Ta chöùng minh: p −1 q −1 p − 1 q − 1 2 ⎡ kq ⎤ 2 ⎡ lp ⎤ . = ∑⎢ ⎥+∑⎢ ⎥ 2 2 k =1 ⎣ p ⎦ l =1 ⎣ q ⎦ p −1 q −1 p −1 q −1 Ta xeùt . soá coù daïng kq.lp vôùi k = 1, 2… ; l = 1, 2… 2 2 2 2 Trong ñoù caùc soá kq - lp ñoù hieån nhieân khoâng coù soá naøo baèng 0. Goïi soá caùc soá döông trong ñoù laø s1 vaø soá caùc soá aâm laø s2, ta coù: p −1 q −1 s1 + s 2 = . 2 2 p −1 Maët khaùc ta coù s1 laø soá caùc soá l sao cho kq – lp > 0 vôùi k = 1, 2… nghóa laø soá 2 p −1 kq p −1 2 ⎡ kq ⎤ caùc soá l sao cho l < p , k = 1, 2… 2 ⇒ s1 = ∑⎢ p ⎥ k =1 ⎣ ⎦ q −1 Vaø töông töï s2 laø soá caùc soá k sao cho kq – lp < 0 vôùi l = 1, 2… nghóa laø soá 2 q −1 lp q −1 2 ⎡ lp ⎤ caùc soá k sao cho k < q vôùi l = 1, 2… 2 ⇒ s2 = ∑⎢ q ⎥ l =1 ⎣ ⎦ p −1 q −1 2⎡ kq ⎤ 2 ⎡ lp ⎤ Vaäy s1 + s2 = ∑ ⎢ ⎥ + ∑⎢ q ⎥ k =1 ⎣ p ⎦ l =1 ⎣ ⎦
- 10 - p −1 q −1 p −1 q −1 2 ⎡ kq ⎤ 2 ⎡ lp ⎤ ⇔ 2 . 2 = ∑⎢ p ⎥ + ∑⎢ q ⎥ k =1 ⎣ ⎦ l =1 ⎣ ⎦ ⎛q⎞ ⎛p⎞ p −1 q −1 Do ñoù ta coù: ⎜ ⎟ . ⎜ ⎟ = ( −1) . 2 2 ⎝p⎠ ⎝q⎠ ⎛q⎞ p −1 q −1 ⎛p⎞ ⎜ ⎟ = ( −1) 2 2 . ⎜ ⎟ . ⇒ ⎝p⎠ ⎝q⎠ 1.2. Kyù hieäu Jacobi 1.2.1. Ñònh nghóa Cho p laø moät soá leû lôùn hôn 1 vaø p = p1.p2… pr laø daïng phaân tích cuûa p thaønh thöøa soá nguyeân toá (p1, p2… pr: coù theå truøng nhau) vaø cho (a, p) = 1. Khi ñoù kyù hieäu Jacobi ñöôïc xaùc ñònh bôûi ñaúng thöùc: ⎛ a ⎞ ⎛ a ⎞⎛ a ⎞ ⎛ a ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ... ⎜ ⎟ ⎝ p ⎠ ⎝ p1 ⎠ ⎝ p2 ⎠ ⎝ p r ⎠ ⎛a⎞ Trong ñoù ⎜ ⎟ laø kyù hieäu Legendre. ⎝ pi ⎠ 1.2.2. Caùc tính chaát ⎛a⎞ ⎛a ⎞ 1. Neáu a ≡ a1 (modp) thì ta coù ⎜ ⎟ = ⎜ 1 ⎟ ⎝p⎠ ⎝ p ⎠ ⎛1⎞ 2. ⎜ ⎟ = 1 ⎝p⎠ ⎛ 1⎞ p −1 3. ⎜ − ⎟ = ( −1) 2 ⎝ p ⎠ ⎛ a1a2 ...an ⎞ ⎛ a1 ⎞⎛ a2 ⎞ ⎛ an ⎞ 4. ⎜ ⎟ = ⎜ ⎟⎜ ⎟ ... ⎜ ⎟ ⎝ p ⎠ ⎝ p ⎠⎝ p ⎠ ⎝ p ⎠ ⎛ b2 ⎞ ⎛ ab2 ⎞ ⎛ a ⎞ Heä quaû: ⎜ ⎟ = 1; ⎜ ⎟=⎜ ⎟ ⎝ p⎠ ⎝ p ⎠ ⎝p⎠ ⎛2⎞ 2 p −1 5. ⎜ ⎟ = ( −1) 8 ⎝p⎠ 6. Neáu P, Q laø hai soá leû nguyeân toá cuøng nhau thì ta coù: ⎛Q⎞ p −1 Q −1 ⎛P⎞ ( ) . ⎜ ⎟ = −1 2 2 . ⎜Q⎟ ⎝P⎠ ⎝ ⎠
- 11 - 1.3. Vaønh cuûa caùc soá nguyeân ñaïi soá 1.3.1. Ñònh nghóa soá nguyeân ñaïi soá Moät soá laø moät soá nguyeân ñaïi soá neáu vaø chæ neáu noù thoûa maõn treân Q moät phöông trình ña thöùc ñôn heä vôùi heä soá nguyeân. 1.3.2. Ñònh lyù Neáu d ≠ 1 laø moät soá nguyeân khoâng coù nhaân töû bình phöông thì trong tröôøng hôïp d ( ) ≡ 2 hoaëc d ≡ 3 (mod 4) caùc soá nguyeân ñaïi soá trong Q d laø caùc soá a + b d vôùi caùc heä soá laø caùc soá nguyeân (höõu tæ). Nhöng neáu d ≡ 1 (mod 4) thì caùc soá nguyeân cuûa Q ( d ) laø ⎛ 1+ d ⎞ caùc soá a + b ⎜⎜ ⎟⎟ vôùi a, b laø soá nguyeân höõu tæ. ⎝ 2 ⎠ Chöùng minh: – Nhaän xeùt: Neáu a ≡ 1 (mod 2) => a = 2r + 1 ⇒ a2 = 4r2 + 4r + 1 ≡ 1 (mod 4) Vaäy a ≡ 1 (mod 2) => a2 ≡ 1 (mod 4) a ≡ 0 (mod 2) ⇒ a2 = 0 (mod 4) theo modun 4. Chöùng minh: a+ b d ∀u∈Q ( d ) ⇒ u ñeàu coù theå vieát döôùi daïng c trong ñoù a, b, c ∈ Z vaø khoâng coù nhaân töû chung naøo caû. Ta giaû söû b ≠ 0 ñeå loaïi tröø tröôøng hôïp taàm thöôøng cuûa moät soá höõu tæ. Khi ñoù phöông trình baäc hai ñôn heä baát khaû quy cho u laø: ⎛ a + b d ⎞⎛ a−b d ⎞ 2a a2 − db2 ⎜⎜ x − ⎟⎟ ⎜⎜ x − ⎟⎟ = x − x + 2 =0 ⎝ c ⎠⎝ c ⎠ c c2 2a a2 − db2 Neáu u laø soá nguyeân ñaïi soá thì caùc heä soá , cuõng phaûi laø soá nguyeân ⇒ 2 c2 4a2 4a2 − 4db2 4db2 , , 2 ∈ Z. c2 c2 c Giaû söû c ñöôïc phaân tích ra thöøa soá nguyeân toá laø: c = p1α p2α ...pαr , αi ≥ 0 1 2 r ⇒ c2 = p12 α p22 α ...p2r α 1 2 r Neáu trong söï phaân tích treân coù pi ≠ 2 thì: pi|c,c|2a => pi|2a => pi ⏐a (vì pi ≠2)
- 12 - pi|c => p2i c2 ; c2 4db2 => p2i 4db2 => pi b2 => pi b (vì d khoâng coù nhaân töû bình phöông). ⇒ a, b, c coù nhaân töû chung laø pi (voâ lyù vôùi caùch choïn a, b, c). Vaäy c = 2α, α ≥ 0 Ta chöùng minh α = 0 ∨ α = 1 Neáu α ≥ 2 thì 4|c, c|2a ⇒ 4|2a ⇒ 2|a 4|c ⇒ 16|c2, c2|4db2 ⇒ 16|4db2 ⇒ 4|db2 ⇒ 2|b2 ⇒ 2|b Vaäy a, b, c coù nhaân töû chung laø 2 (voâ lyù) Vaäy α chæ coù theå laø 0 hoaëc 1 hay c = 1 ∨ c = 2 Tröôøng hôïp d ≡ 2 hoaëc d ≡ 3 (mod 4) a2 − db2 a2 − db2 Neáu c = 2 thì = ∈ Z ⇔ a2 – db2 ≡ 0 (mod 4) ⇔ a2 ≡ db2 (mod 4) c 2 4 Neáu b ≡ 1 (mod 2) ⇒ b2 ≡ 1 (mod 4) ta laïi coù d ≡ 2 hoaëc d ≡ 3 (mod 4) neân db2 ≡ 2 hoaëc db2 ≡ 3 (mod 4) Do ñoù a2 ≡ 2 (mod 4) hoaëc a2 ≡ 3 (mod 4) (traùi vôùi nhaän xeùt) Neáu b ≡ 0 (mod 2) ⇒ b2 ≡ 0 (mod 4) ⇒ db2 ≡ 0 (mod 4) maø a2 ≡ db2 (mod 4) ⇒ a2 ≡ 0 (mod 4) ⇒ a ≡ 0 (mod 2) Tröôøng hôïp naøy a, b, c coù nhaân töû chung laø 2 (voâ lyù vôùi caùch choïn a, b, c) Vaäy c khoâng theå baèng 2 neân c chæ coù theå baèng 1. Khi ñoù u ñöôïc vieát döôùi daïng u = a + b d Caùc soá nguyeân ñaïi soá trong Q ( d ) laø caùc soá a + b d ; a, b ∈ Z Ngöôïc laïi moïi soá daïng a + b d ; a, b ∈ Z ñeàu laø soá nguyeân ñaïi soá trong Q ( d ) vì noù thoûa phöông trình coù heä soá nguyeân: x2 – 2ax + a2 – db2 = 0 Tröôøng hôïp d ≡ 1 (mod 4) 1+ d Neáu c = 1 thì u = a + b d ∈ Z + Z d ⊂ Z + Z 2 Neáu c = 2: a2 − db2 a2 − db2 Ta coù: = ∈Z ⇔ a2 – db2 ≡ 0 (mod 4) ⇔ a2 ≡ db2 ≡ b2 (mod 4) c2 4 (vì d ≡ 1 (mod 4))
- 13 - Neáu a ≡ 0 (mod 2) ⇒ a2 ≡ 0 (mod 4) ⇒ b2 ≡ 0 (mod 4) ⇒ b ≡ 0 (mod 2) ⇒ a, b, c coù nhaân töû chung laø 2 (voâ lyù) Neáu a ≡ 1 (mod 2) ⇒ a2 ≡ 1 (mod 4) ⇒ b2 ≡ 1 (mod 4) ⇒ b ≡ 1 (mod 2) Vaäy a ≡ b ≡ 1 (mod 2), khi ñoù caùc soá nguyeân ñaïi soá trong Q d laø caùc soá a+ b d a−b ⎛ 1+ d ⎞ 1+ d = + b ⎜⎜ ⎟⎟ = a’ + b’. 2 2 ⎝ 2 ⎠ 2 a−b (a’ = ∈ Z vì a ≡ b ≡ 1 (mod 2); b = b’) 2 a+ b d Ngöôïc laïi caùc soá , (a, b ∈ Z, a ≡ b ≡ 1 (mod 2), d ≡ 1 (mod 4)) 2 a2 − db2 Vì noù thoûa phöông trình heä soá nguyeân: x2 – ax + =0 4 (a ≡ b ≡ 1 (mod 2) ⇒ a2 ≡ b2 ≡ 1 (mod 4) ⇒ a2 – db2 ≡ 1 – d (mod 4) a2 − db2 a2 – db2 ≡ 0 (mod 4) ⇒ ∈ Z) 4
- 14 - CHÖÔNG 2: TÍNH EUCLIDE CUÛA VAØNH CAÙC SOÁ NGUYEÂN ÑAÏI SOÁ BAÄC HAI 2.1. Mieàn Euclide 2.1.1. Ñònh nghóa haøm Euclide Cho D laø moät mieàn nguyeân. AÙnh xaï φ: D → Z ñöôïc goïi laø haøm Euclide treân D neáu noù thoûa 2 tính chaát sau: i. φ (ab) ≥ φ (a), ∀ a, b ∈ D, b ≠ 0 ii. Neáu a, b ∈ D, b ≠ 0 thì toàn taïi q, r ∈ D sao cho: a = qb + r vaø φ (r) φ (0), neáu a ≠ 0 Chöùng minh: i. a ~ b ⇒ ∃ u ∈ U(D): a = bu ⇒φ a) = φ (bu) > φ (b) (u ≠ 0) (1) b = au-1 ⇒ φ (b) = φ (au-1) > φ (a) (2) Töø (1) vaø (2) => φ (a) = φ (b) ii. φ laø haøm Euclide ⎯⎯ ii → ∃ q, r: a = bq + r, φ (r) < φ (b) =φ(a) Maët khaùc a|b neân a|r Neáu r ≠ 0 thì φ (a) ≤ φ (r) (voâ lyù) vaäy r = 0 ⇒ a = bq maø b = ac = bqc ⇒ b(1 – qc) = 0 ⇒ qc =1
- 15 - ⇒ c ∈ U(D) hay a ~ b {U(D) = caùc phaàn töû khaû nghòch trong D} iii. Chöùng minh: a ∈ U(D) ⇔ φ (a) = φ (1) a ∈ U(D) ⇔ a ~ 1 ⎯⎯ i → φ (a) = φ(1) (⇐) 1/a, φ (a) = φ(1) ⇒ a ~ 1 ⇒ a ∈ U(D) iv. Ta coù q, r ∈ D: 0 = aq + r, φ (r) < φ (a) Neáu r ≠ 0 thì q ≠ 0, r = -aq ⇒ φ (r) = φ (-aq) ≥ φ (a) (voâ lyù) Vaäy r = 0 ⇒ φ (a) > φ (0) 2.1.3. Ñònh nghóa mieàn Euclide Cho D laø moät mieàn nguyeân. Neáu D coù haøm Euclide φ(a) thì D ñöôïc goïi laø mieàn Euclide vôùi haøm φ . Nhaän xeùt: Mieàn Euclide laø mieàn Iñeâan chính. Chöùng minh: Giaû söû D laø mieàn Euclide vôùi haøm φ , I ∇ D. Neáu I = {0} thì I = I ≠ {0} Ñaët s = {φ (a), a ≠ 0, a ∈ I} Vì I ≠ {0} neân s ≠ φ vaø ta coù φ (a) > φ (0), ∀ a ≠ 0 ⇒ s bò chaën döôùi ⇒ toàn taïi phaàn töû nhoû nhaát. Giaû söû φ (a) = min S 0 ≠ a∈I ∀b ∈ I ⇒ ∃ q, r ∈ D: b = aq + r, φ (r) < φ (a) Neáu r ≠ 0 ⇒ φ (r) ∈ S maø φ (r) < φ (a) maâu thuaãn vôùi vieäc choïn a. Vaäy r = 0 ⇒ b = aq hay I = Vaäy I laø Iñeâan chính. 2.2. Ví duï veà mieàn Euclide 2.2.1. Ñònh lyù a. Z laø mieàn Euclide b. Cho F laø moät tröôøng, F[x] laø moät mieàn Euclide. 2.2.2. Haøm φ m Cho m laø soá nguyeân khoâng chính phöông. Haøm φm: Q ( m ) → Q ñöôïc ñònh nghóa bôûi:
- 16 - ( ) φm r + s m = |r2 - ms2| ∀ r, s ∈ Q 2.2.3. Tính chaát cô baûn cuûa φm a. φm: Z + Z m → N ∪ {0} ⎛ 1+ m ⎞ b. Neáu m ≡ 1 (mod 4) thì φm: ⎜⎜ Z + Z ⎟ → N ∪ {0} ⎝ 2 ⎟⎠ c. α ∈ Q ( m), φ m(α) =0⇔α=0 d. φm(αβ) = φm(α). φ m(β), ∀ α, β ∈ Q ( m) e. φm(αβ) ≥ φm(α), ∀ α, β ∈ Z + Z m , β ≠ 0 ⎛l+ m ⎞ f. Neáu m ≡ 1 (mod 4) thì φm(αβ) ≥ φm(α), ∀ α, β ∈ Z + Z. ⎜⎜ ⎟⎟ ,β ≠ 0 ⎝ 2 ⎠ Chöùng minh: a. α = r + s m ; r, s ∈ Z φm(α) = |r2 – ms2| ∈ N ∪ {0} 1+ m s s b. α=r+s = r+ + m ; r, s ∈ Z 2 2 2 2 ⎛ s⎞ s2 s2 φm(α) = ⎜ r + ⎟ − m = r 2 + rs + (1 − m ) ⎝ 2⎠ 4 4 s2 m ≡ 1 (mod 4) ⇒ (m – 1) # 4 ⇒ r 2 + rs + (1 − m ) ∈ N ∪ {0} 4 c. α=r+r m ∈Q ( m) φm(α) = |r2 – ms2| = 0 ⇔ r2 = ms2 ⇔ r = ±s m ; r, s ∈ Q Vì m laø soá nguyeân khoâng chính phöông neân r = s = 0 ⇒ α = 0 d. α = r + s m ; r, s ∈ Q β = a + b m ; a, b ∈ Q ( )( α.β = r + s m a + b m ) = ra + bsm + ( rb + sa ) m φm(αβ) = |(ra + bsm)2 – m(rb + sa)2| φm (α). φm(β) = |r2 – ms2| |a2 – mb2| = |r2a2 – r2b2m – ms2a2 + m2b2s2|
- 17 - = |r2a2 + m2b2s2 + 2rsabm – m(r2b2 + 2rsba + ? = |(ra + bs)2 – m(rb + sa)2| Vaäy φm(αβ) = φm (α).φm (β) e. φm(αβ) ≥ φm (α), ∀ α, β ∈ Z + Z m , β ≠ 0 Ta coù: φm: Z + Z m → N ∪ {0} β ≠ 0 ⇒ φm(β) ≠ 0 ⇔ φm(β) ≥ 1, φm (α) ≥ 0 φm(αβ) = φm(α). φm(β) ≥ 1. φm (α) ⇔ φm (αβ) ≥ φm (α) 1+ m f. Neáu m ≡ 1 (mod 4) thì φm: Z + Z → N ∪ {0} 2 φm (αβ) = φm (α).φm (β) φm (α) ≥ 0 ⇒ φm (αβ) ≥ φm (α), ∀ β ≠ 0 β ≠ 0 ⇒ φm (β) ≥ 1 2.2.4. Boå ñeà Cho m laø soá nguyeân khoâng chính phöông. Z + Z m laø mieàn Euclide vôùi haøm φm neáu vaø chæ neáu moïi x, y ∈ Q thì toàn taïi a, b ∈ Z sao cho: (( ) ( φm x + y m − a + b m )) < 1 Chöùng minh: (⇒) Giaû söû Z + Z m laø mieàn Euclide vôùi φm, ta chöùng minh vôùi moïi x, y ∈ Q (( toàn taïi a,b ∈ Z sao cho φm x + y m − a + b m ) ( )) < 1 r+s m ∀ x, y ∈ Q, x + y m = ; r, s, t ∈ Z t Vì Z + Z m laø mieàn Euclide vôùi φm → ∃ a, b, c, d ∈ Z ( ) ( ) r + s m = a + b m t + c + d m sao cho: φ m c + d m < φm(t) ( ) ⎛ r+s m ⎞ ( Xeùt φm( x + y m − a + b m = φm ⎜⎜ ) t ( − a + b m ⎟⎟ ) ⎝ ⎠ = φm ⎜⎜ ⎛ c+d m ⎞ φm c + d m ( ) ⎟⎟ =
- 18 - (⇐) Ngöôïc laïi neáu moïi x,y∈Q thì toàn taïi a,b∈Z: φm (x + y m - (a + b m )) 0) m m m 2.2.5. Boå ñeà Cho m laø soá nguyeân khoâng chính phöong m ≡ 1 (mod 4). Mieàn nguyeân ⎛ 1+ m ⎞ Z + Z ⎜⎜ ⎟⎟ laø mieàn Euclide vôùi haøm φm neáu vaø chæ neáu moïi x, y ∈ Q toàn taïi a, b ∈ Z ⎝ 2 ⎠ ⎛ ⎛ 1+ m ⎞ ⎞ sao cho: φm ⎜ x + y m − ⎜⎜ a + b ⎟⎟ < 1 ⎜ ⎝ ⎝ 2 ⎟⎠ ⎟⎠
- 19 - Chöùng minh: ⎛ 1+ m ⎞ (⇒) Giaû söû: Z + Z ⎜⎜ ⎟⎟ laø mieàn Euclide. Ta chöùng minh moïi x,y∈Q. toàn taïi ⎝ 2 ⎠ ⎛ ⎛ 1+ m ⎞ ⎞ a,b ∈Z sao cho: φm ⎜ x+y m - ⎜⎜ a+b ⎟⎟ < 1: ⎜ ⎝ ⎝ 2 ⎟⎠ ⎟⎠ Thaät vaäy r+s m ∀ x, y ∈ Q, giaû söû x + y m = ; r, s, t ∈ Z t 1+ m ⎛ 1+ m ⎞ Ta coù: Z + Z m ⊂ Z + Z vì Z + Z ⎜⎜ ⎟⎟ laø mieàn Euclide vôùi haøm φm 2 ⎝ 2 ⎠ 1+ m 1+ m neân coù a + b , c+d sao cho: 2 2 ⎛ 1+ m ⎞ ⎛ 1+ m ⎞ ⎛ 1+ m ⎞ r + s m = ⎜⎜ a + b ⎟⎟ t + ⎜⎜ c + d ⎟⎟ , φm ⎜⎜ c + d ⎟ < φm(t) ⎝ 2 ⎠ ⎝ 2 ⎠ ⎝ 2 ⎟⎠ 1+ m 1+ m ⇒ c+d = r + s m - a+b t 2 2 ⎛ 1+ m ⎞ ⎜ c+d ⎟ r+s m 1+ m 1+ m ⇒⎜ 2 ⎟= - ( a+b )= x + y m − (a + b ) ⎜ t ⎟ t 2 2 ⎜ ⎟ ⎝ ⎠ ⎛ 1+ m ⎞ φ ⎛ c + d 1+ m ⎞ m⎜ ⎟ ⎛ ⎛ 1+ m ⎞⎞ ⎜ c+d ⎟ 2 ⎠ φm ⎜ x + y m − ⎜⎜ a + b = φm ⎜ 2 ⎟= ⎝
- 20 - 1+ m r+s 2 2r + s + s m = = x + y m ; trong ñoù: 1 + m 2t + u + u m t+u 2 x= ( 2r + s )( 2t + u ) − sum ∈ Q ( 2t + u ) − mu2 2 2 ( st − ru ) y= ∈Q ( 2t + u ) 2 − mu2 ⎛ ⎛ 1+ m ⎞⎞ Theo giaû thieát toàn taïi a, b ∈ Z sao cho: φm ⎜ x + y m − ⎜⎜ a + b ⎟⎟ < 1 ⎜ ⎝ ⎝ 2 ⎟⎠ ⎟⎠ m −1 Ñaët c = r – ta - bu ∈ Z (vì m ≡ 1 (mod 4)) 4 d = s – bt – au – bu ∈ Z 1+ m ⎛ 1+ m ⎞⎛ 1+ m ⎞ 1+ m Ta coù nhaän xeùt: r + s = ⎜⎜ a + b ⎟⎟ ⎜⎜ t + u ⎟⎟ + c + d 2 ⎝ 2 ⎠⎝ 2 ⎠ 2 Thaät vaäy, ta coù: ⎛ 1+ m ⎞⎛ 1+ m ⎞ m −1 1+ m VP = ⎜⎜ a + b ⎟⎟ ⎜⎜ t + u ⎟⎟ + r − ta − bu + (s – bt – au – bu) ⎝ 2 ⎠⎝ 2 ⎠ 4 2 1+ m + 2 m 1+ m 1+ m m −1 = at + bu + au + bt + r – ta – bu 4 2 2 4 1+ m 1+ m 1+ m 1+ m 1+ m +s - bt - au - bu =r+s = VT 2 2 2 2 2 1+ m 1+ m c+d r+s ⎛ 2 2 1+ m ⎞ ⎛ 1+ m ⎞ Ta coù: = − ⎜⎜ a + b ⎟⎟ = x + y m - ⎜⎜ a + b ⎟ 1+ m 1+ m ⎝ 2 ⎠ ⎝ 2 ⎟⎠ t+u t+u 2 2 ⎛ 1+ m ⎞ ⎛ ⎞ φm ⎜ c + d ⎟ 1+ m 2 ⎜ c+d ⎟ ⎛ ⎛ 1+ m ⎞⎞ ⎝ ⎠ =φ ⎜ 2 ⎟ = φm ⎜ x + y m − ⎜ a − b m ⎜ ⎟⎟ < 1 ⎛ 1+ m ⎞ ⎜ 1 + m ⎟ ⎜ ⎝ ⎝ 2 ⎟⎠ ⎟⎠ φm ⎜ t + u ⎟ ⎜ t+u ⎟ ⎝ 2 ⎠ ⎝ 2 ⎠ ⎛ 1+ m ⎞ ⎛ 1+ m ⎞ ⇒ φm ⎜⎜ c + d ⎟⎟ < φm ⎜⎜ t + u ⎟ ⎝ 2 ⎠ ⎝ 2 ⎟⎠ 2.2.6. Ñònh lyù