Luận văn Thặng dư chính phương, kí hiệu legendre, kí hiệu jacobi và ứng dụng

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRIỆU THỊ VY VY THẶNG DƯ CHÍNH PHƯƠNG, KÍ HIỆU LEGENDRE, KÍ HIỆU JACOBI VÀ ỨNG DỤNG Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60.46.40 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng - Năm 2011 2 Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: TS. NGUYỄN DUY THÁI SƠN Phản biện 1: TS. Nguyễn Ngọc Châu Phản biện 2: GS. TSKH. Nguyễn Văn Mậu Luận văn ñược bảo vệ trước hội ñồng chấm Luận văn tốt nghiệp thạc sĩ Khoa học họp tại Đại học Đà Nẵng vào ngày 23 tháng 10 năm 2011 Có thể tìm hiểu luận văn tại: - Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng - Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng 3 MỞ ĐẦU 1. Lý do chọn ñề tài Có thể nói: thặng dư chính phương, kí hiệu Legendre, kí hiệu Jacobi là những mảng kiến thức hay và khó liên quan ñến lý thuyết ñồng dư, ñồng thời có nhiều ứng dụng trong Số học. Vì thế, trong các kì thi chọn học sinh giỏi ở các nước (nhất là các kì thi chọn ñội tuyển Olympic Toán), những mảng kiến thức này thường ñược quan tâm ñáng kể. Ở nước ta, theo chỗ chúng tôi biết, mãi ñến năm 2008 mới có một tài liệu tiếng Việt [2] chính thức ñề cập ñến cả ba mảng thặng dư chính phương, kí hiệu Legendre và kí hiệu Jacobi; do ñó việc giảng dạy các kiến thức này một cách ñầy ñủ ở bậc trung học phổ thông gặp không ít khó khăn, nhất là khi mà giáo viên thường chưa ñược ñào tạo chuyên sâu về chúng. Vì những lý do trên, tôi chọn ñề tài “Thặng dư chính phương, kí hiệu Legendre, kí hiệu Jacobi và ứng dụng” ñể nghiên cứu. 2. Mục ñích và nhiệm vụ nghiên cứu Chương 1, chương 2 của luận văn sẽ trình bày một cách ñầy ñủ nhất – theo cách hiểu của chúng tôi – về lý thuyết thặng dư chính phương, thặng dư không chính phương, kí hiệu Legendre, kí hiệu Jacobi với nhiều ví dụ minh họa. Trong chương 3, chúng tôi tìm cách ñưa ra các ứng dụng và xây dựng một hệ thống các bài toán theo mức ñộ từ dễ ñến khó liên quan ñến các vấn ñề về thặng dư chính phương, kí hiệu Legendre, kí hiệu Jacobi. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu Đối tượng nghiên cứu là thặng dư chính phương, kí hiệu Legendre, kí hiệu Jacobi và ứng dụng. 4 3.2. Phạm vi nghiên cứu Nghiên cứu lý thuyết và ứng dụng của thặng dư chính phương, kí hiệu Legendre, kí hiệu Jacobi dựa trên lý thuyết về ñồng dư. 4. Phương pháp nghiên cứu Trong luận văn này, chúng tôi thu thập và ñọc các tài liệu tìm ñược từ nhiều nguồn khác nhau (ñặc biệt là các thư mục trên internet có liên quan ñến ñề tài) ñể phân tích, nghiên cứu lý thuyết về thặng dư chính phương, kí hiệu Legendre, kí hiệu Jacobi và viết lại một cách hệ thống theo cách chúng tôi hiểu. 5. Ý nghĩa khoa học và thực tiễn của ñề tài Xây dựng ñược một tài liệu tham khảo bổ ích cho giáo viên và học sinh trung học phổ thông về thặng dư chính phương, kí hiệu Legendre, kí hiệu Jacobi, trong ñó phần lý thuyết ñược chứng minh chặt chẽ và các bài toán ñược hệ thống tương ñối ñầy ñủ và cập nhật theo mức ñộ từ dễ ñến khó. 6. Cấu trúc của luận văn Ngoài phần mở ñầu và kết luận, luận văn gồm có 3 chương: Chương 1. Thặng dư chính phương, thặng dư không chính phương và kí hiệu Legendre. Chương 2. Kí hiệu Jacobi và số giả nguyên tố Euler. Chương 3. Một số ứng dụng và các bài toán. 5 Chương 1 THẶNG DƯ CHÍNH PHƯƠNG THẶNG DƯ KHÔNG CHÍNH PHƯƠNG KÍ HIỆU LEGENDRE 1.1. Thặng dư chính phương - thặng dư không chính phương Định nghĩa 1.1. Cho m là số nguyên dương và a là số nguyên nguyên tố cùng nhau với m . Nếu ñồng dư thức 2 (mod )x a m≡ có nghiệm thì ta nói rằng a là một thặng dư chính phương của m . Ngược lại, nếu ñồng dư thức 2 (mod )x a m≡ không có nghiệm, ta nói rằng a là một thặng dư không chính phương của m . Ví dụ 1.1. Để xác ñịnh các số nguyên là thặng dư chính phương của 13, chúng ta tính bình phương của các số nguyên 1, 2, , 12. Ta thấy rằng: ( )2 21 12 1 mod 13≡ ≡ ; ( )2 22 11 4 mod 13≡ ≡ ( )2 23 10 9 mod 13≡ ≡ ; ( )2 24 9 3 mod 13≡ ≡ ( )2 25 8 12 mod 13≡ ≡ ; ( )2 26 7 10 mod 13≡ ≡ . Như vậy, các thặng dư chính phương của 13 là 1, 3, 4, 9, 10, 12; các số nguyên 2, 5, 6, 7, 8, 11 là các thặng dư không chính phương của 13. Trong chương 1 này, chúng ta sẽ nghiên cứu thặng dư chính phương, thặng dư không chính phương của số nguyên tố lẻ p . Chúng ta sẽ chỉ ra rằng, nếu p là một số nguyên tố lẻ thì số các thặng dư chính phương của p bằng số các thặng dư không chính phương của p trong tập { }1, 2, ..., 1S p= − . 6 Bổ ñề 1.1. Cho p là một số nguyên tố lẻ và a là một số nguyên nguyên tố cùng nhau với p . Khi ñó, ñồng dư thức 2 (mod )x a m≡ hoặc là không có nghiệm, hoặc là có ñúng hai nghiệm không ñồng dư mod p . Bổ ñề trên dẫn dắt chúng ta ñến ñịnh lí sau: Định lí 1.1. Nếu p là một số nguyên tố lẻ thì có ñúng 1 2 p − thặng dư chính phương của p và 1 2 p − thặng dư không chính phương của p trong tập { }1, 2, ..., 1S p= − . Một kí hiệu liên kết ñặc biệt với thặng dư chính phương ñược mô tả trong ñịnh nghĩa sau: 1.2. Kí hiệu Legendre 1.2.1. Định nghĩa 1.2. Cho p là một số nguyên tố lẻ và a là một số nguyên nguyên tố cùng nhau với p . Kí hiệu Legendre a p       ñược ñịnh nghĩa như sau: 1 1 . a p nÕu a lµ thÆng d− chÝnh ph−¬ng cña p nÕu a lµ thÆng d− kh«ng chÝnh ph−¬ng cña p   =   −   Kí hiệu này ñược ñặt tên sau khi nhà Toán học người Pháp là Adrien-Marie Legendre giới thiệu việc sử dụng kí niệu này. Ví dụ 1.2. Theo ví dụ 1.1, kí hiệu Legendre 13 a      , với 1, 2 , ..., 12a = , có giá trị như sau: 1 3 4 9 10 12 1 13 13 13 13 13 13             = = = = = =                        ; 2 5 6 7 8 11 1 13 13 13 13 13 13             = = = = = = −                        . 7 1.2.2. Tiêu chuẩn Euler. Cho p là một số nguyên tố lẻ và a là một số nguyên nguyên tố cùng nhau với p . Khi ñó: ( ) 1 2 mod p a a p p −  ≡    . Ví dụ 1.3. Trường hợp 13p = , ta có: ( ) ( ) 13 1 26 223 3 27 1 1 mod13 − = = ≡ ≡ . Vì vậy, 3 1 13   =    , tức là 3 là một thặng dư chính phương của 13. 1.2.3. Các tính chất của kí hiệu Legendre Định lí 1.2. Cho p là một số nguyên tố lẻ và ,a b là các số nguyên nguyên tố cùng nhau với p . Khi ñó: (i) Nếu ( )moda b p≡ thì a b p p     =        . (1.1) (ii) a b ab p p p      =          (1.2) (iii) 2 1 a p   =    . (1.3) Ví dụ 1.4. Tính 317 13       . Vì ( )317 5 mod13≡ nên theo công thức (1.1), ta ñược: 317 5 1. 13 13     = = −        Sử dụng tiêu chuẩn Euler, chúng ta có thể phân lớp những số nguyên tố có 1− là một thặng dư chính phương hoặc 1− là một thặng dư không chính phương. Định lí 1.3. Nếu p là một số nguyên tố lẻ thì 8 ( ) ( ) 1 1 mod41 1 1 mod4 . nÕu p p nÕu p  ≡ −  =   − ≡ −   Một kết quả ñẹp sau ñây của nhà toán học Gauss cung cấp một tiêu chuẩn khác ñể xác ñịnh khi nào số nguyên a nguyên tố cùng nhau với số nguyên tố p là một thặng dư chính phương của p . Bổ ñề 1.2. (Bổ ñề Gauss). Cho p là một số nguyên tố lẻ và a là một số nguyên nguyên tố cùng nhau với p . Nếu s là số các thặng dư dương bé nhất modulo p của các số nguyên 1, 2 , 3 , ..., 2 p a a a a − mà lớn hơn 2 p thì ( )1 sa p   = −    . Ví dụ 1.5. Cho 5a = và 13p = . Sử dụng bổ ñề Gauss, tính 5 13       . Ta tính các thặng dư dương bé nhất modulo13 của 1.5, 2.5, 3.5, 4.5, 5.5 và 6.5 . Đó tương ứng là 5, 10, 2 , 7, 12 và 4 . Có 3 số trong các số này lớn hơn 13 2 . Vậy, ( )35 1 1. 13   = − = −    Sử dụng bổ ñề Gauss, ta có thể ñịnh rõ ñặc ñiểm của tất cả các số nguyên tố có 2 là một thặng dư chính phương. Định lí 1.4. Nếu p là một số nguyên tố lẻ thì ( ) 2 1 8 2 1 p p −  = −    (1.4) Như vậy, 2 là một thặng dư chính phương của các số nguyên tố p thỏa ( )1 mod8p ≡ ± và là một thặng dư không chính phương của các số nguyên tố p thỏa ( )3 mod8p ≡ ± . 9 2 1 p   =    nếu ( )1 mod8p ≡ ± ; 2 1 p   = −    nếu ( )3 mod8p ≡ ± . Ví dụ 1.6. Theo ñịnh lí 1.4, ta thấy rằng: 2 2 2 2 1 7 17 23 31         = = = =                ; 2 2 2 2 2 2 1 3 5 11 13 19 29             = = = = = = −                        . Ví dụ 1.7. Tính 89 . 13       Ta có ( )89 2 mod13≡ − nên 89 2 1 2 13 13 13 13 − −       = =              . Vì ( )13 1 mod4≡ nên theo ñịnh lí 1.3, ta có 1 1. 13 −  =    Từ ( )13 3 mod8≡ − , theo ñịnh lí 1.4, ta có 2 1. 13   = −    Vậy 89 1. 13   = −    Tiếp theo, chúng ta trình bày ñịnh luật về tính thuận nghịch chính phương, một nền tảng quan trọng cho sự ñánh giá kí hiệu Legendre. 1.3. Định luật về tính thuận nghịch chính phương Cho p và q là hai số nguyên tố khác nhau, q là một thặng dư chính phương của p . Khi ñó, ta có biết ñược rằng p là một thặng dư chính phương của q ? Định lí sau ñây giúp ta trả lời câu hỏi này. Định lí 1.5. (Định luật về tính thuận nghịch chính phương) Cho p và q là hai số nguyên tố lẻ khác nhau. Khi ñó 10 ( ) 1 12 2.1 p qp q q p − −   = −      . Ta chú ý rằng số 1 2 p − là số chẵn khi ( )1 mod4p ≡ và là số lẻ khi ( )3 mod4p ≡ . Do vậy: 1 1 . 2 2 p q− − là chẵn nếu ( )1 mod4p ≡ hoặc ( )1 mod4q ≡ ; 1 1 . 2 2 p q− − là lẻ nếu ( )3 mod4p ≡ và ( )3 mod4q ≡ . Từ ñó, ta có: ( ) ( ) ( ) ( ) 1 nÕu 1 mod4 hoÆc 1 mod4 1 nÕu 3 mod4 vµ 3 mod4 . p qp q q p p q  ≡ ≡    =    − ≡ ≡    Vì giá trị của p q       và q p       chỉ có thể là 1 hoặc −1 nên: ( ) ( ) ( ) ( ) nÕu 1 mod4 hoÆc 1 mod4 nÕu 3 mod4 vµ 3 mod4 . q p q pp q q p q p    ≡ ≡        =       − ≡ ≡    Ví dụ 1.8. Cho 13p = và 17q = . Tính 13 17       và 17 13       . Ta có ( )1 mod4p q≡ ≡ . Do vậy 13 17 17 13     =        . Vì ( )17 4 mod13≡ nên theo (1.1), ta có 17 4 13 13     =        . Theo (1.3), ta có 24 2 1 13 13    = =       . 11 Vậy 13 17 1 17 13     = =        . Ví dụ 1.9. Cho 7p = và 19q = . Tính 7 19       . Ta có ( )3 mod4p q≡ ≡ . Áp dụng ñịnh luật về tính thuận nghịch chính phương, ta ñược: 7 19 19 7     = −        . Vì ( )19 5 mod7≡ nên theo (1.1), ta có 19 5 7 7     =        . Lại có ( )5 1 mod4≡ , sử dụng ñịnh luật về tính thuận nghịch chính phương một lần nữa, ta ñược 5 7 7 5     =        . Vì ( )7 2 mod5≡ và ( )5 3 mod8≡ − nên theo (1.1) và (1.6), ta ñược: 7 2 1 5 5     = = −        . Vậy 7 1 19   =    . Ví dụ 1.10. Biết rằng 1009 là số nguyên tố. Tính 713 1009       . Ta phân tích 713 23.31= . Theo (1.2): 713 23.31 23 31 . 1009 1009 1009 1009         = =                . Từ ( )1009 1 mod4≡ , ta ñược: 23 1009 1009 23     =        ; 31 1009 1009 31     =        . 12 Vì ( )1009 20 mod23≡ , ( )1009 17 mod31≡ nên theo (1.1): 1009 20 23 23     =        ; 1009 17 31 31     =        . Theo (1.2) và (1.3), ta có: 2 220 2 .5 2 5 5 23 23 23 23 23          = = =                  . Do ( )5 1 mod4≡ nên theo ñịnh luật về tính thuận nghịch chính phương: 5 23 23 5     =        . Vì ( )23 3 mod5≡ nên theo (1.2): 23 3 5 5     =        . Áp dụng ñịnh luật về tính thuận nghịch chính phương một lần nữa, ta ñược 3 5 5 3     =        . Vì ( )5 2 mod3≡ nên theo (1.1) và (1.6), ta ñược 5 2 1 3 3     = = −        . Như vậy 23 1. 1009   = −    Tương tự, 17 31 14 2 7 7 17 31 17 17 17 17 17 7              = = = = =                          23 7 4 2 1 7 3 3 3        = = − = − = − = −               . Như vậy 31 1. 1009   = −    13 Vậy 713 1 1009   =    . Bổ ñề 1.3. Nếu p là một số nguyên tố lẻ và a là một số nguyên lẻ không chia hết cho p thì ( ) ( ),1 T a pa p   = −    trong ñó, ( ) 1 2 1 , p j ja T a p p − =   =     ∑ . Ví dụ 1.11. Tính 7 11       và 11 7       . Sử dụng bổ ñề 1.3, ta tính tổng: 5 1 7 7 14 21 28 35 0 1 1 2 3 7. 11 11 11 11 11 11j j =             = + + + + = + + + + =                        ∑ Vậy ( )77 1 1 11   = − = −    . Tương tự, ta có: 3 1 11 11 22 33 1 3 4 8. 7 7 7 7j j =         = + + = + + =                ∑ Vậy ( )811 1 1 7   = − =    . Hệ quả. Nếu p là số nguyên tố lẻ thì a) ( )( ) 1 nÕu 1 mod123 1 nÕu 5 mod12 p p p  ≡ ±   =   − ≡ ±   b) ( )( ) 1 nÕu 1 mod63 1 nÕu 1 mod6 . p p p  ≡ −  =   − ≡ −   14 Chương 2 KÍ HIỆU JACOBI VÀ SỐ GIẢ NGUYÊN TỐ EULER Trong phần này, chúng ta ñịnh nghĩa kí hiệu Jacobi. Kí hiệu này ñược giới thiệu bởi nhà Toán học người Đức tên là Carl Jacobi. Kí hiệu Jacobi là một sự mở rộng của kí hiệu Legendre. Nó ñược sử dụng ñể ñánh giá kí hiệu Legendre và ñịnh nghĩa số giả nguyên tố Euler. 2.1. Kí hiệu Jacobi Định nghĩa 2.1. Cho n là một số nguyên dương lẻ có phân tích tiêu chuẩn 1 2 1 2 ... m tt t mn p p p= ( ip ( )1,i m= là các số nguyên tố, it ( )1,i m= là các số nguyên dương) và a là một số nguyên nguyên tố cùng nhau với n . Khi ñó, kí hiệu Jacobi a n       ñược ñịnh nghĩa như sau: 1 2 1 2 1 21 2 ... ... m m tt t tt t mm a a a a a n p p pp p p         = =                 trong ñó 1 2 , , ..., m a a a p p p                 là các kí hiệu Legendre. Ví dụ 2.1. Từ ñịnh nghĩa kí hiệu Jacobi, ta thấy rằng: ( )( ) ( ) 2 2 2 2 2 2 2 1 1 1 75 3 53.5        = = = − − = −              ; 37 37 37 37 37 2 2 4 385 5.7.11 5 7 11 5 7 11             = = =                        ( ) ( ) ( ) 2 22 1 .1. 1 .1. 1 1 11   = − = − − = −    . Khi n là số nguyên tố, kí hiệu Jacobi chính là kí hiệu Legendre. 15 Ta thấy rằng, nếu ( )2 modx a n≡ có nghiệm và ip ( )1,i m= là ước nguyên tố của n thì ( )2 mod ix a p≡ cũng có nghiệm. Vì vậy, 1 i a p   =    . Do ñó: 1 2 1 2 1 21 2 ... 1 ... m m tt t tt t mm a a a a a n p p pp p p         = = =                 . Ngược lại, cho 15n = và 2a = . Ta có ( )( )2 2 2 1 1 1 15 3 5      = = − − =          . Tuy nhiên, ñồng dư thức ( )2 2 mod15x ≡ không có nghiệm do ( )2 2 mod3x ≡ và ( )2 2 mod5x ≡ không có nghiệm. Như vậy, nếu 1a n   =    , ta chưa thể kết luận ñược ( )2 modx a n≡ có nghiệm hay không. 2.2. Các tính chất của kí hiệu Jacobi Định lí 2.1. Cho n là số nguyên dương lẻ và ,a b là hai số nguyên nguyên tố cùng nhau với n . Khi ñó (i) Nếu ( )moda b n≡ thì a b n n     =        . (2.1) (ii) ab a b n n n      =          . (2.2) (iii) ( ) 121 1 n n − −  = −    . (2.3) (iv) ( ) 2 1 8 2 1 n n −  = −    . (2.4) 16 2.3. Định luật về tính thuận nghịch ñối với kí hiệu Jacobi Định lí 2.2. Cho ,n m là hai số nguyên dương lẻ nguyên tố cùng nhau. Khi ñó ( ) 1 1.2 21 m nn m m n − −   = −      . Bây giờ, chúng ta sẽ giới thiệu một thuật toán ñể ñánh giá kí hiệu Jacobi. Cho a và b là hai số nguyên dương với ( ), 1,a b a b= > . Gọi 0 1 ,R a R b= = . Sử dụng thuật toán chia, chia 0 R cho 1 R và phân tích số dư thành tích của lũy thừa cao nhất của 2 và một số nguyên dương lẻ, ta ñược: 1 0 1 1 2 2sR R q R= + , trong ñó, 1 s là một số nguyên không âm và 2 R là một số nguyên dương lẻ với 2 1 R R< . Ta lại lấy 1 R chia cho 2 R và phân tích số dư thành tích của lũy thừa cao nhất của 2 và một số nguyên dương lẻ, ta ñược: 2 1 2 2 3 2sR R q R= + , trong ñó, 2 s là một số nguyên không âm và 3 R là một số nguyên dương lẻ với 3 2 R R< . Tiếp tục như vậy cho ñến khi 1nR = , tức là: 3 2 3 3 4 2sR R q R= + 2 3 2 2 1 2 n s n n n nR R q R − − − − − = + 1 2 1 1 2 .1n s n n nR R q − − − − = + , trong ñó, js là một số nguyên không âm và 1jR + là một số nguyên dương lẻ với 1j jR R+ < , 2, 1j n= − . 17 Ta minh họa dãy các ñẳng thức này bởi ví dụ sau: Ví dụ 2.2. Cho 401, 111a b= = . Khi ñó: 2401 111.3 2 .17= + 0111 17.6 2 .9= + 317 9.1 2 .1= + . Định lí 2.3. Cho a và b là hai số nguyên dương với a b> . Khi ñó: ( ) 22 2 1 2 11 2 1 2 2 3 1 2 1 1 1 11 1 1 1 1 1 ... . . ... . 8 8 8 2 2 2 2 2 21 n n n n R R RR R R R R R s s sa b − − − − − − −− − − − − − + + + + + + +  = −    trong ñó, các số nguyên jR và js , 1, 1j n= − ñược mô tả như trên. Ví dụ 2.3. Tính 401 111       . Từ ví dụ 2.2, ta ñược: ( ) 2 2 2111 1 17 1 9 1 111 1 17 1 17 1 9 1 2. 0. 3. . . 8 8 8 2 2 2 2 401 1 1. 111 − − − − − − − + + + +  = − =    2.4. Số giả nguyên tố Euler Cho p là một số nguyên tố lẻ và b là một số nguyên nguyên tố cùng nhau với p . Khi ñó, theo tiêu chuẩn Euler: ( ) 1 2 mod p b b p p −   ≡     . Vì vậy, nếu ta kiểm tra ñược n là số nguyên tố, b là một số nguyên với ( ), 1b n = thì ta ñược: ( ) 1 2 mod n b b n n −   ≡     trong ñó, b n       là kí hiệu Jacobi. 18 Nếu chúng ta chỉ ra ñược rằng ñồng dư thức ( ) 1 2 mod n b b n n −   ≡     là sai, tức là ( ) 1 2 mod n b b n n −   ≡     thì n là hợp số. Ví dụ 2.4. Cho 341n = và 2b = . Ta tính ñược ( ) 341 1 17022 2 1 mod341 . − = ≡ Lại có, từ ( )341 3 mod8≡ − , theo ñịnh lí 2.1, ta ñược 2 1 341   = −    . Do ñó ( ) 341 1 2 2 2 mod341 341 −   ≡     . Vậy 341n = là hợp số. Định nghĩa 2.2. Cho b là một số nguyên dương. Nếu n là một hợp số nguyên dương lẻ thỏa mãn ñồng dư thức ( ) 1 2 mod n b b n n −   ≡     thì n ñược gọi là số giả nguyên tố Euler cơ sở b . Một số giả nguyên tố Euler cơ sở b là một hợp số, nó ñược trá hình như là một số nguyên tố bằng cách thỏa mãn ñồng dư thức ñược cho trong ñịnh nghĩa. Ví dụ 2.5. Cho 1105n = và 2b = . Ta có: 1105 5.13.17.= ( ) ( ) ( )1105 1 138 138552 422 2 2 16 1 mod5 .− = = = ≡ ( )( ) ( )( ) ( )1105 1 46 462 2552 622 2 2 64 1 mod13 .− = = = ≡ ( )( ) ( )( ) ( )1105 1 69 692 2552 422 2 2 16 1 mod17 .− = = = ≡ 19 Suy ra ( ) 1105 1 55222 2 1 mod 1105 − = ≡ . Từ ( )1105 1 mod8≡ nên 2 1 1105   =    . Do ñó ( ) 1105 1 2 2 2 mod 1105 1105 −   ≡     . Vì 1105 là hợp số nên 1105 là số giả nguyên tố Euler cơ sở 2. Định lí 2.4. Nếu n là số giả nguyên tố Euler cơ sở b thì n là số giả nguyên tố cơ sở b . Định lí 2.5. Nếu n là số giả nguyên tố mạnh cơ sở b thì n là số giả nguyên tố Euler cơ sở b . Như ta ñã biết một số giả nguyên tố Euler cơ sở b chưa hẳn là số giả nguyên tố mạnh cơ sở b . Tuy nhiên, khi gặp ñiều kiện ràng buột, một số giả nguyên tố Euler cơ sở b là số giả nguyên tố mạnh cơ sở b . Hai ñịnh lí sau ñây cho chúng ta biết ñiều ñó. Định lí 2.6. Nếu ( )3 mod4n ≡ và n là số giả nguyên tố Euler cơ sở b thì n là số giả nguyên tố mạnh cơ sở b . Định lí 2.7. Nếu n là số giả nguyên tố Euler cơ sở b và 1b n   = −    thì n là số giả nguyên tố mạnh cơ sở b . 20 Chương 3 MỘT SỐ ỨNG DỤNG VÀ CÁC BÀI TOÁN 3.1. Chứng minh ñồng dư thức bậc hai có dạng ( )2 0 modax bx c p+ + ≡ có nghiệm với p là số nguyên tố lẻ, ( ), 1a p = . Xét ñồng dư thức ( )2 0 modax bx c p+ + ≡ (3.1) với p là số nguyên tố lẻ và ( ), 1a p = . Vì ( ), 1a p = nên ta cũng có ( )4 , 1a p = . Đồng dư thức (3.1) tương ñương với ( ) ( )24 0 moda ax bx c p+ + ≡ . Sử dụng phân tích ( ) ( ) ( )22 24 2 4a ax bx c ax b b ac+ + = + − − , ta ñược: ( ) ( )( )2 22 4 modax b b ac p+ ≡ − . Đặt ( )2y ax b= + và ( )2 4d b ac= − , ta ñược: ( )2 mody d p≡ . (3.2) Nếu ( )0 modx x p≡ là nghiệm của (3.1) thì ( )( )02 mody ax b p≡ + thỏa mãn (3.2). Ngược lại, nếu ( )0 mody y p≡ là nghiệm của (3.2) thì từ ( )( )02 modax y b p≡ − ta có thể tìm ñược nghiệm của (3.1). Bài toán 1. Tìm tất cả các thặng dư chính phương của 29. Bài toán 2. Tìm giá trị của các kí hiệu Legendre sau: a) 2 29       b) 1 29 −      c) 5 29       21 d) 2 127       e) 1 127 −      f) 5 127       . Bài toán 3. Những ñồng dư thức nào sau ñây có nghiệm: a) ( )2 2 mod 29x ≡ b) ( )2 28 mod 29x ≡ c) ( )2 5 mod 29x ≡ d) ( )2 2 mod 127x ≡ e) ( )2 126 mod 127x ≡ f) ( )2 5 mod 127x ≡ . Bài toán 4. Chứng minh rằng ( )2 196 mod 1357x ≡ có nghiệm. Bài toán 5. Đồng dư thức nào sau ñây có nghiệm. Tìm nghiệm của chúng nếu có. a) ( )25 4 7 0 mod 19x x+ + ≡ ; b) ( )22 7 13 0 mod 61x x+ − ≡ . Bài toán 6. Chứng minh rằng nếu p là số nguyên tố có dạng 4 1k + thì !x p′= là nghiệm của ñồng dư thức ( )2 1 0 modx p+ ≡ với 1 2 p p − ′ = . 3.2. Tìm nghiệm của ñồng dư thức bậc hai có dạng ( )2 mod ,nx a p≡ *n∈
với p là số nguyên tố lẻ và ( ), 1a p = . Bài toán 7. Chứng minh rằng nếu p là một số nguyên tố lẻ thì ñồng dư thức ( )2 mod ,nx a p≡ *n∈
có nghiệm khi và chỉ khi 1a p   =    . 3.3. Một số bài toán khác Bài toán 8. Chứng minh rằng 19 không phải là ước của 24 4n + với bất kì số nguyên n nào. Bài toán 9. Khi các số nguyên dương a và b thay ñổi sao cho cả hai số 15 16a b+ và 16 15a b− ñều là các số chính phương dương, hãy tìm giá trị bé nhất có thể có của { }min 15 16 , 16 15a b a b+ − . 22 Bài toán 10. Cho 22 1nk = + với n∈
. Chứng minh rằng k là số nguyên tố khi và chỉ khi k là một ước của 1 23 1 k− + . Bài toán 11. Cho ,m n là các số nguyên dương thỏa mãn ( )3 1 3 n m A m + + = là một số nguyên. Chứng minh rằng A là số lẻ. Bài toán 12. Tính 2 20011 2 2 2 ... 2003 2003 2003 2003        + + + +               . Bài toán 13. Chứng minh rằng 2 1n + không có ước nguyên tố có dạng 8 7k + . Bài toán 14. Chứng minh rằng nếu a là một thặng dư chính phương của số nguyên tố p thì nghiệm của ( )2 modx a p≡ là a) ( )1 modnx a p+≡ ± nếu 4 3p n= + . b) ( )1 modnx a p+≡ ± hoặc ( )2 1 12 modn nx a p+ +≡ ± nếu 8 5p n= + . Bài toán 15. Chứng minh rằng phương trình 2 3 5x y= − không có nghiệm nguyên ( ),x y . Bài toán 16. a) Chứng minh rằng không tồn tại các số tự nhiên ,x y sao cho 4xy x y− − là một số chính phương. b) Chứng minh rằng không tồn tại các số tự nhiên , ,x y z sao cho 4xyz x y− − là một số chính phương. Bài toán 17. Chứng minh rằng nếu n là số giả nguyên tố Euler cơ sở a và b thì n cũng là số giả nguyên tố Euler cơ sở ab . Bài toán 18. Chứng minh rằng nếu n là số giả nguyên tố Euler cơ sở b thì n cũng là số giả nguyên tố Euler cơ sở n b− . 23 3.4. Bài tập tham khảo 1) Tính 7 43       . Tìm một số nguyên x thỏa mãn ( )2 7 mod43x ≡ . 2) Cho p là một số nguyên tố. Chứng minh rằng tồn tại x ∈
thỏa mãn 2 3p x x− + nếu và chỉ nếu tồn tại y Î ¢ thỏa mãn 2 25p y y− + . 3) Cho p là một số nguyên tố lẻ. Chứng minh rằng 1 1 0 p a a p − =   =    ∑ . 4) Chứng minh rằng với n Î ¥ , mọi ước nguyên tố p của 4 2 1n n− + ñều có dạng 12 1,k + k Î ¢ . 5) Chứng minh rằng một số nguyên a là thặng dư chính phương của mọi số nguyên tố p nếu và chỉ nếu a là số chính phương. 6) Chứng minh rằng 2 2 1 5 x y + − không phải là số nguyên với bất kì các số nguyên , 2x y > . 7) Tìm tất cả các số nguyên dương N là thặng dư chính phương của tất cả các số nguyên tố lớn hơn N . 24 KẾT LUẬN Luận văn ñã trình bày một cách ñầy ñủ nhất về lý thuyết thặng dư chính phương, thặng dư không chính phương, kí hiệu Legendre, kí hiệu Jacobi với nhiều ví dụ minh họa. Luận văn ñã xây dựng ñược một hệ thống các bài toán liên quan ñến các vấn ñề về thặng dư chính phương, kí hiệu Legendre, kí hiệu Jacobi và trình bày một số bài toán trong các kì thi quốc gia, quốc tế, một số bài toán trên các tạp chí Crux, . Luận văn là một tài liệu tham khảo cho giáo viên và học sinh chuyên Toán.