Số chính phương theo modul bậc tùy ý

Chia sẻ: AndromedaShun _AndromedaShun | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

5
lượt xem 1
download

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

Số chính phương là số nguyên dương bằng bình phương đúng của một số nguyên. Bài viết trình bày định nghĩa, định lí, hệ quả của các định lí về số chính phương; kí hiệu Legendre; luật thuận nghịch Gauss;... 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: Số chính phương theo modul bậc tùy ý

Hội thảo khoa học, Hưng Yên 25-26/02/2017 SỐ CHÍNH PHƯƠNG THEO MODUL BẬC TÙY Ý Vũ Thị Thuần - Nguyễn Thị Đan Quế THPT Chuyên Hưng Yên 1 Kiến thức cơ sở Định nghĩa 1. Cho số nguyên dương m. Nếu hai số a và b có cùng số dư khi chia cho m thì ta nói a dồng dư với b theo modul m. Kí hiệu a ≡ b (mod m). Định lý 1 (Fecmat bé). Giả sử p là số nguyên tố và mọi a ∈ Z : a p ≡ a (mod p). Hệ quả 1. i) Với p là số nguyên tố, a là số nguyên thỏa mãn ( a, p) = 1 thì a p−1 ≡ 1 (mod p). ii) Với p là số nguyên tố và a là số nguyên thỏa mãn ( a, p) = 1 thì a p( p−1) ≡ 1 (mod p2 ). Định lý 2 (Wilson). Cho p là số nguyên tố. Khi đó ( p − 1)! ≡ −1 (mod p). 2 Một số kết quả 2.1 Số chính phương theo mod p Định nghĩa 2. Cho số nguyên tố p. Số nguyên a được gọi là số chính phương theo mod p nếu tồn tại số tự nhiên x sao cho x2 ≡ a (mod p). Hiển nhiên nếu p là ước của a thì a là số chính phương theo mod p, do đó ta chỉ xem xét trong trường hợp ( a, p) = 1. Ví dụ 1. 8 là số chính phương theo mod 17 vì 52 ≡ 8 (mod 17). Nhưng 8 lại không phải là số chính phương theo mod 11, vì phương trình x2 ≡ 8 (mod 11) không có nghiệm. Ví dụ 2. Cho p là số nguyên tố lẻ, a là số chính phương theo mod p, a không chia hết cho p. Chứng minh rằng a là số chính phương theo mod pk với mọi số tự nhiên k. . Lời giải. Do a là số chính phương theo mod p nên tồn tại số tự nhiên x để ( x2 − a)..p. . Giả sử ( x2 − a)..pt , nhưng không chia hết cho pt+1 . Khi đó x2 − a = pt .k với (k, p) = 1. Khi đó ta chứng minh tồn tại x 0 sao cho x 02 − a chia hết cho pt+1 . Xem xét x 0 ở dạng x 0 = x + pt .r. Khi đó x 02 − a = x2 + 2xpt r + p2t r2 − a = pt k + 2xpt r 214
Hội thảo khoa học, Hưng Yên 25-26/02/2017 . Do đó, để x 02 − a chia hết cho pt+1 thì k + 2xr..p. (1) . Vì p lẻ, a không chia hết cho p, ( x2 − a)..p nên (2x, p) = 1. Do đó theo định lý Bezout, tồn tại r thỏa mãn (1). Từ đó, suy ra điều phải chứng minh. Bổ đề 1. Cho p là số nguyên tố lẻ. Phương trình x2 ≡ a (mod p) chỉ có 1 nghiệm x ≡ 0 (mod p) nếu a ≡ 0 (mod p) và vô nghiêm hoặc có 2 nghiệm (mod p) nếu p - a. Chứng minh. Nếu a ≡ 0 (mod p), ta có x2 ≡ 0 (mod p), nên p | x2 , suy ra p | x, hay x ≡ 0 (mod p). Nếu p - a, và phương trình x2 ≡ a (mod p) có ít nhất một nghiệm là x ≡ b (mod p). Khi đó b2 ≡ a (mod p) nên (−b)2 ≡ a (mod p). Vậy x ≡ −b (mod p) cũng là một nghiệm của phương trình. Ta sẽ chứng minh 2 nghiệm này phân biệt. Thật vậy, giả sử b ≡ −b (mod p), thì p | 2b, nhưng p lẻ nên p | b, hay p ≡ 0 (mod p), suy ra a ≡ 0 (mod p) (mâu thuẫn). Vậy b và −b là 2 nghiệm phân biệt của phương trình. Giả sử ngoài nghiệm b và −b, phương trình còn nghiệm x ≡ c (mod p). Khi đó b2 ≡ c2 (mod p), hay p | (b2 − c2 ), suy ra c ≡ b (mod p) hoặc c ≡ −b (mod p). Như vậy, nghiệm c này trùng với nghiệm b hoặc −b. Do đó, phương trình ban đầu hoặc vô nghiệm hoặc chỉ có 2 nghiệm. Ví dụ 3. x2 ≡ 8(mod 17) có 2 nghiệm là 5 và 12. Nhưng chú ý rằng, kết quả này là sai khi p = 2, vì x2 ≡ 1 (mod 2) chỉ có một nghiệm là x ≡ 1(mod 2) p−1 Hệ quả 2. Cho p là số nguyên tố lẻ. Khi đó trong tập 1; 2; . . . ; p − 1 có số chính phương 2 p−1 theo mod p và số không phải là chính phương mod p. 2 Chứng minh. p−1 p−1 Ta có k2 ≡ ( p − k)2 (mod p), với mọi k = 1, Như vậy, tập 1; 2; . . . ; p − 1 có giá 2 2 trị bình phương khác nhau theo mod p. Do tập 1; 2; . . . ; p − 1 là hệ thặng dư thu gọn mod p p−1 p−1 nên có số chính phương theo mod p và số không phải là chính phương mod p. 2 2 2.2 Kí hiệu Legendre a Định nghĩa 3. Cho p là số nguyên tố lẻ và ( a, p) = 1. Kí hiệu Legendre được định nghĩa bởi p ( a 1 a là số chính phương theo mod p = p −1 a không phải là số chính phương theo mod p 5 2 11 Ví dụ 4. (5, 11) = 1. = 1, vì 4 ≡ 5 (mod 11). Tương tự như vậy, = 1, vì 62 ≡ 11 11 5 (mod 5). 215
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Trong trường hợp p = 2, ta chỉ có 2 phương trình sau x2 ≡ 0 (mod 2) và x2 ≡ 1 (mod 2) và 2 nghiệm lần lượt của nó là x ≡ 0 (mod 2) và x ≡ 1 (mod 2), tức là cả 0 và 1 đều là thặng dư bậc hai mod 2. Trong trường hợp p là hợp số, ta xem xét ví dụ sau. Ví dụ 5. Giải phương trình x2 ≡ 79 (mod 91). Lời giải. Vì 91 = 7.13 nên ta xem xét 2 phương trình đồng dư sau x2 ≡ 79 (mod 7) và x2 ≡ 79 (mod 13) x ≡ 3 (mod 7) x2 ≡ 79 (mod 7) ⇔ x2 ≡ 2 (mod 7) ⇔ x ≡ 4 (mod 7) 2 2 x ≡ 1 (mod 13) x ≡ 79 (mod 13) ⇔ x ≡ 1 (mod 13) ⇔ x ≡ 12 (mod 13) Sử dụng định lý thặng dư Trung hoa,ta xem xét bài toán trong 4 trường hợp, tuy nhiên vì m2 = (−m)2 , nên ta chỉ xem xét 2 trường hợp sau TH1. ( x ≡ 3 (mod 7) x ≡ 1 (mod 13) m 7 13 p 13 7 − 1 s ≡ p (mod m) 6 2 a 3 1 Vậy x ≡ 13.6.3 + 7.2.1 ≡ 248 ≡ 66(mod 91). Và x ≡ −66 ≡ 25(mod 91) cũng là một nghiệm khác của phương trình. TH2. ( x ≡ 3 (mod 7) x ≡ 12 (mod 13) m 7 13 p 13 7 − 1 s ≡ p (mod m) 6 2 a 3 12 Vậy x ≡ 13.6.3 + 7.2.12 ≡ 402 ≡ 38(mod 91). Và x ≡ −38 ≡ 53(mod 91) cũng là một nghiệm khác của phương trình. Dưới đây là một số công cụ để tính toán ký hiệu Legendre. a p −1 Định lý 3 (Euler). Cho p là một số nguyên tố lẻ, a > 0, (a, p) = 1. Khi đó = a 2 (mod p). p Ta xét hai trường hợp sau Chứngminh. a TH1. = 1. p 216
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Khi đó, tồn tại một số tự nhiên b sao cho sao cho b2 ≡ a (mod p). p −1 p −1 p −1 Bởi vậy, b2 2 ≡ a 2 (mod p) ⇔ b p−1 ≡ a 2 (mod p) Nếu p | b thì p | b2 = a (mâu thuẫn). p −1 p−1 ≡ 1 (mod p ). Do đó a 2 ≡ 1 (mod p ) và Nếu p - a, theo định lý Fermat ta có b a p −1 ≡ a 2 (mod p). p a TH2. = - 1. p Xét tập 1; 2; . . . ; p − 1. Ta chỉ ra rằng tập này sẽ được chia thành những cặp (s, t) sao cho st ≡ a (mod p). Giả sử s ∈ 1, 2, . . . , p − 1 thì (s, p) = 1 nên tồn tại nghịch đảo mod p của s, kí hiệu là s−1 . Khi đó, ta chọn t ∈ 1, 2, . . . , p − 1 sao cho t ≡ s−1 a (mod p). −1 2 Ta chứng minh rằng, s và t là phân Thật vậy, giả sử s ≡ s a (mod p), khi đó s ≡ a biệt. a (mod p), mâu thuẫn với gải thiết = - 1. p p−1 Như vậy tập 1, 2, . . . , p − 1 được chia thành cặp (s, t) như thế. p −1 2 Do đó 1.2 . . . ( p − 1) ≡ a 2 (mod p). Theo định lý Wilson, thì ( p − 1)! ≡ −1 (mod p). p −1 Vậy a 2 ≡ −1 (mod p). Từ đó, suy ra điều phải chứng minh. p −1 Ví dụ 6.Giảsử với p = 13 và a = 10, thì a 2 = 106 ≡ 1(mod 13). 10 Do đó, = 1 và x2 ≡ 10(mod 13) có nghiệm. Thật vậy 72 = 49 ≡ 10(mod 13). 13 a b Bổ đề 2. Nếu a ≡ b (mod p) thì = . p p Chứng minh. Nếu a ≡ b (mod p) thì x2 ≡ a (mod p) ⇔ x2 ≡ b (mod p). Do đóa là sốchính phương a b theo mod p khi và chỉ khi b là số chính phương theo mod p. Vậy = . p p a Chú ý rằng, ta có thể sử dụng kết quả này để áp dụng công thức Euler tính trong p trường hợp a < 0 bằng việc thay a bởi b > 0 sao cho a ≡ b (mod p). Bổ đề 3. Cho p là số nguyên tố lẻ, a, b > 0, ( a, p) = (b, p) = 1. Khi đó a b ab = p p p . Chứng minh. Theo định lý Euler, thì a b p −1 p −1 ≡ a 2 b 2 (modp) p p 217
Hội thảo khoa học, Hưng Yên 25-26/02/2017 ab p −1 ≡ ( ab) 2 (modp) p a b ab Do vậy ≡ (mod p). p p p Vì 2 vế của đẳng thức trên chỉ nhận giá trị bằng 1 hoặc - 1 và p là số nguyên tố lẻ nên a b ab = p p p . 2 a Hệ quả 3. Cho p là số nguyên tố lẻ, a > 0, ( a, p) = 1. Khi đó = 1. p a Chúng ta có thể sử dụng kết quả trên để tính cho trường hợp a là số chính phương. p Bổ đề 4. ( −1 1 nếu p = 4k + 1 = p −1 nếu p = 4k +3 Chứng minh. Theo công thức Euler, ta có −1 p−1 p −1 p −1 = ≡ ( p − 1) 2 ≡ (−1) 2 (mod p) p p ( ( (−1)2k nếu p = 4k + 1 1 nếu p = 4k + 1 = = (−1)2k+1 nếu p = 4k + 3 −1 nếu p = 4k + 3 Sử dụng bổ đề Gauss, ta cũng có thể chứng minh được rằng −1 p2 −1 = (−1) 8 p p2 − 1 (Chú ý rằng với p là số nguyên tố lẻ thì p = 2k + 1, p2 − 1 = 4k (k + 1) nên là số tự 8 nhiên) −1 Ví dụ 7. = 1, vì 13 = 4.3 + 1. Do đó, phương trình x2 ≡ 1(mod 13) có nghiệm. Thật 13 vậy 52 = 25 ≡ 12 ≡ −1 (mod 13) −1 Tương tự, = −1, vì 23 = 4.5 + 3. Do đó, phương trình x2 ≡ 1(mod 23) vô nghiệm. 23 2 72 − 1 = (−1) 8 = 1 7 Do đó, phương trình x2 ≡ 2(mod 7) có nghiệm. Thật vậy x ≡ 3 (mod 7) là một nghiệm của phương trình. 218
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Ví dụ 8. Cho x, y là các số nguyên. Chứng minh rằng x2 − 2 không chia hết cho 2y2 + 3. Lời giải. Giả sử 2y2 + 3 | x2 − 2 vì 2y2 + 3 là số lẻ, nên mọi ước nguyên tố của nó đều lẻ, giả sử một ước nguyên tố lẻ đó là p. Suy ra p cũng là ước của x2 − 2, hay phương trình x2 ≡ 2 (mod p) có nghiệm. Vậy p2 −1 2 . (−1) 8 = = 1 ⇔ p2 − 1..16 p p ≡ 1(mod 8) ⇔ p ≡ −1(mod 8) Như vậy, mọi ước nguyên tố của 2y2 + 3 chia 8 dư 1 hoặc -1 nên 2y2 + 3 ≡ ±1(mod 8). Điều này mâu thuẫn vì y2 ≡ 0, 1, 4(mod 8) nên 2y2 + 3 ≡ 3, 5(mod 8). Vậy điều giả sử là sai, suy ra điều phải chứng minh. Ví dụ 9 (VN TST 2004). Cho số nguyên dương n. Chứng minh rằng 2n + 1 không có ước nguyên tố dạng 8k + 7. Lời giải. Gọi p là ước nguyên tố của 2n + 1 và p ≡ 7(mod 8). Nếu n chẵn ta có −1 p−1 p −1 n 2 ≡ −1 (mod p) ⇒ = 1 ⇒ (−1) 2 = 1 ⇒ 2 | ⇒ p ≡ 1(mod 4) p 2 Điều này mâu thuẫn với p ≡ 7(mod 8) Nếu n lẻ ta có − − 2 1 1 p −1 p2 −1 2n+1 ≡ −2 (mod p) ⇒ =1⇒ ⇒ = 1 ⇒ (−1) 2 (−1) 2 = 1 ⇒ 2 | p p p p−1 ⇒ p ≡ 1(mod p)(1) 2 p −1 p2 −1 p −1 p2 −1 Vì p ≡ 7(mod 8) nên (−1) 2 = −1 và (−1) 8 = 1 kéo theo (−1) 2 (−1) 8 = −1 (mâu thuẫn với (1)) Như vậy, giả thiết phản chứng sai, suy ra điều phải chứng minh. Ví dụ 10. Cho n là số nguyên dương lẻ và u là một ước nguyên dương lẻ của 3n + 1. Chứng minh rằng u − 1 chia hết cho 3 . Lời giải. Gọi p là một ước nguyên tố lẻ của u, khi đó p cũng là ước nguyên tố lẻ của 3n + 1. Khi đó 3n + 1 ≡ 0 (mod p) ⇒ 3n+1 ≡ −3 (mod p ) Vì n lẻ nên n + 1 là chẵn, −3 do đó -3 là số chính phương theo mod p, hay = 1(*) Theo định lí Eu- p −3 −1 3 p −1 3 ler, ta có = = (−1) 2 . (1) Theo luật tương hỗ Gauss p p p p 3 p (3−1)( p−1) p −1 3 p −1 p = (−1) 4 = (−1) 2 ⇒ = (−1) . 2 (2) Từ (1) và (2) suy p 3 p 3 −3 p p 2 3−1 ra = (−1) p−1 . Nếu p ≡ 2(mod 3)⇒ = ≡ 2 2 ≡ −1(mod 3). p 3 3 3 −3 Kéo theo = −1,mâu thuẫn với (*) Hiển nhiên p 6= 3, do đó p ≡ 1(mod 3). p 219
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Vì u là số lẻ nên mọi ước nguyên tố của u đều là lẻ và thỏa mãn chia 3 dư 1, do đó u chia 3 dư 1, hay u − 1 chia hết cho 3. Ví dụ 11. Cho p là số nguyên tố, p > 3, p có dạng 3k + 1. Chứng minh rằng p . ∏i=1 i2 + i + 1 ..p. Lời giải. . . Ta sẽ chứng minh tồn tại i sao cho (i2 + i + 1)..p ⇔ (2i + 1)2 + 3..p ⇔ −3 là số chính phương p −1 theo mod p ⇔ (−3) 2 ≡ 1 (mod p). √ Ví dụ 12. Cho p là số nguyên tố lẻ. Chứng minh rằng tồn tại số tự nhiên a sao cho a < p + 1 và a là số chính phương theo mod p h pi Lời giải. Giả sử a là số chính phương theo mod p dương bé nhất. Đặt b = + 1. a Khi đó 0 < ab − p < a nên ab − p không phải là số chính phương theo mod p. Do đó ab − p a b b −1 = = = p p p p p Vậy b là một số chính phương theo mod p. Suy ra a ≤ b, mặt khác b < + 1 nên ta có a p a < + 1 (1). a √ √ Nếu a ≤ p thì hiển nhiên a < p + 1. √ p p √ Nếu a > p thì < √ , kết hợp với (1) suy ra a < p + 1. a p p−1 Ví dụ 13. Chứng minh rằng nếu p là số nguyên tố dạng 4k + 1 thì x = ! là một 2 nghiệm của phương trình x2 + 1 ≡ 0 (mod p). p−1 Lời giải. Ta có i ≡ −( p − i ) (mod p), với mọi i = 1, 2, . . . , 2 Nhân vế với vế của các đẳng thức này ta được p−1 p−1 p −1 ! ≡ (−1) 2 .( p − 1)( p − 2) . . . p − (mod p) 2 2 p−1 Với x = ! thì 2 p−1 p−1 p−1 2 p −1 p+1 x = ! ! ≡ !.(−1) 2 ( p − 1).( p − 2) . . . ≡ 2 2 2 2 p −1 p +1 (−1) 2 .( p − 1)! ≡ (−1) 2 ≡ −1 (mod p)(theo định lý Wilson) Định lý 4. Cho x, y là 2 số tự nhiên nguyên tố cùng nhau, a, b, c là các số tự nhiên tùy ý. Nếu p là ước nguyên tố lẻ của ax2 + bxy + cy2 mà không là ước của tích abc thì D = b2 − 4ac là số chính phương theo mod p. Trường hợp đặc biệt nếu p | x2 − Dy2 và ( x, y) = 1 thì D là số chính phương theo mod p. 220
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Chứng minh. Đặt N = ax2 + bxy + cy2 . Khi đó 4aN = (2ax + b)2 − Dy2 . Vì N ≡ 0 (mod p) nên (2ax + b)2 ≡ Dy2 (mod p)(1). . . . Nếu y..p thì ax2 ..p, mà a không chia hết cho p nên x..p. Mâu thuẫn với giả thiết ( x, y) = 1. Như vậy, tồn tại y1 sao cho yy1 ≡ 1 (mod p). Nhân cả 2 vế của (1) với y21 ta được (2axy1 + byy1 )2 ≡ D (yy1 )2 ≡ D (mod p) Như vậy D là số chính phương theo mod p. p−1 Với mỗi số tự nhiên a mà p không là ước của a,và k = 1, 2,. . . , tồn tại duy nhất số 2 p−1 p−1 rk ∈ − , . . . , −2, −1, 1, 2, . . . , sao cho ka ≡ rk (mod p). Hơn nữa không có hai 2 2 
 

giá trị nào của rk có giá trị tuyệt đối bằng nhau. Do đó tập |r1 | , |r2 | , . . . ,
r p − 1
thực

 2 p−1 chất là một hoán vị của tập (1, 2, . . . , p0 ) (p0 = ). 2 Bởi vậy 0 a.2a.3a . . . p0 a r1 .r2 .r3 . . . r p0 ap = = 1.2.3 . . . p0 1.2.3 . . . p0 Đặt rk = ε k . |rk | với k = 1, 2,. . . ,p’, ε k = ±1 và áp dụng công thức Euler ta được a Định lý 5. = ε 1 ε 2 . . . ε p0 p ka 2ka Nếu ε k ≡ −1 (mod p)thì ka = tp − |rk |, khi đó = t − 1, = 2t − 1, hay p p 2ka " # 2ka ka = + 1 Vì vậy ε k = (−1) p . p p 2.3 Luật thuận nghịch Gauss Từ kết quả của 5 ta chứng minh được bổ đề sau a p 0 2ka Bổ đề 5 (Bổ đề Gauss). = (−1)S , với S = ∑k=1 . p p a Bổ đề Gauss giúp ta dễ dàng tính được giá trị của kí hiệu Legendre trong trường p hợp a và p nhỏ. 2 p 0 4k Ví dụ với a = 2 thì = (−1)S , với S = ∑k=1 . p p 221