Thặng dư bậc hai modulo M

Bài viết trình bày các số k-phương .mod p/ trong đó p là số nguyên tố đóng vai trò cực kì quan trọng trọng trong lí thuyết số. Các số k phương đã được giới toán học quan tâm nghiên cứu từ xa xưa, đặc biệt là từ thế kỷ 17 cho đến nay đã có rất nhiều công trình lí thuyết số nghiên cứu về tính chất và ứng dụng của số k-phương.
Nội dung trích xuất từ tài liệu:
Thặng dư bậc hai modulo M THẶNG DƯ BẬC HAI MODULO M Nguyễn Hồng Lữ - Trường THPT Chuyên Lương Thế Vinh - Đồng Nai LỜI GIỚI THIỆU Các số k-phương .mod p/ trong đó p là số nguyên tố đóng vai trò cực kì quan trọng trọng trong lí thuyết số. Các số k phương đã được giới toán học quan tâm nghiên cứu từ xa xưa, đặc biệt là từ thế kỷ 17 cho đến nay đã có rất nhiều công trình lí thuyết số nghiên cứu về tính chất và ứng dụng của số k-phương.Định nghĩa 1. Số k-phương .mod m/: Cho số nguyên dương m; m 2 và số nguyên a sao cho .a; m/ D 1. Nếu tồn tại số tự nhiên x sao cho: x k a .mod m/ thì ta nói a là số k-phương module m hay nói: a là số lũy thừa bậc k theo module m, cũng có người nói: a là thặng dư bậc k của m. Số chính phương mod m: Cho số nguyên dương m 2 và số nguyên a sao cho .a; m/ D 1. Nếu tồn tại số tự nhiên x sao cho x 2 a .mod p/ thì ta nói a là số chính phương module m (cũng nói a là thặng dư bình phương của m)Số k–phương module nguyên tố đơn giản và hay gặp nhất chính là số 2-phương module nguyêntố mà trong ngôn ngữ lí thuyết số ta gọi là thặng dư bậc hai theo module nguyên tố hay số chínhphương mod p nguyên tố.1. Thặng dư bậc hai modulo p1.1. Khái niệmCho số nguyên m, cho số nguyên tố lẻ p: Nếu phương trình x 2 a .mod p/ có nghiệm nguyên thì ta nói a là số chính phương module m (cũng nói a là thặng dư bình phương của m). Nếu phương trình x 2 a .mod p/ không có nghiệm nguyên thì ta nói a là số phi chính phương module m (cũng nói a không phải là thặng dư bình phương của m). Nếu a 0 .mod m/ thì ta nói: a không phải là số chính phương module m, đồng thời a không phải là số phi chính phương module m.Kí hiệu: +) aQRp: a là số chính phương module p (viết tắt chữ quadratic residue) +) aNRp: a là số phi chính phương module p (viết tắt chữ quadratic nonresidue)Ví dụ 1.1. Vì 52 4 .mod 7/ nên: 4 là số chính phương module 7 hay 4QR7 131 Tạp chí Epsilon, Số 05, 10/2015 Vì 52 3 .mod 1/1 nên: 3 là số chính phương module 11 hay 3QR11 Vì a2 6 2 .mod 3/ với mọi số nguyên a nên: 2 là số phi chính phương module 3 hay 2NR3. Vì b 2 6 3 .mod 7/ với mọi số nguyên b nên: 3 là số phi chính phương module 7 hay 3NR7.Định lí sau đây cho ta mối quan hệ trong phép nhân của các thặng dư bậc hai .mod p/Định lý 1.1. Cho p là số nguyên tố lẻ. Ta có: Nếu: aQRp và bQRp thì abQRp Nếu: aQRp và bNRp thì abNRp Nếu: aNRp và bNRp thì abQRpMột cách tổng quát: Tích hai số cùng chính phương hoặc cùng phi chính phương module psẽ cho ta một số chính phương module p. Tích của một số chính phương và một số phi chínhphương module p sẽ cho ta một số phi chính phương module p.Chú ý: Bạn thấy định lí này giống với phép nhân dấu âm (-) với dấu dương(+) trong đại số: haisố cùng dấu thì tích là số dương; hai số trái dấu thì tích là số âm!Nhận xét: Ta có aQRm , .a C m/QRm: Điều này cho ta thấy: Nếu một phần tử của lớp thặngdư modulo m là số chình phương modulo m thì mọi phần tử của lớp đó cũng là thặng dư modulom.Ví dụ 1.2. Với modulo bằng 7: một số nguyên tố lẻ. Ta có: +) Tập hợp các số f1I 2I 4g là 3 số chính phương module 7 +) Tập hợp các số f3I 5I 6g là 3 số phi chính phương module 7. 7 1Nhận xét: có D 3 cho mỗi loại. 2Ví dụ 1.3. Với modulo bằng 13: một số nguyên tố lẻ. Ta có: +) Tập hợp các số 1I 3I 4I 9I 10I 12 là 6 số chính phương module 13 +) Tập hợp các số 2I 5I 6I 7I 8I 11 là 6 số phi chính phương module 13. 13 1Nhận xét: có D 6 số cho mỗi loại. 2Từ các ví dụ 2, ví dụ 3 ta đi đến định lí sau:Định lý 1.2. Nếu p là số nguyên tố lẻ thì trong tập 1; 2; :::; p 1 số các thặng dư bình phương p 1của p bằng số các số không phải là thặng dư bình phương của p và bằng 2 132Tạp chí Epsilon, Số 05, 10/2015Chứng minh. Để ý rằng: k 2 .p k/2 .mod p/, nên trong tập hợp 12 I 22 I :::I .p 1/2 có ˚ p 1 p 1 cặp đồng dư (6 0 ) với nhau theo mod p. Cho k chạy từ 1 đến ta đặt k 2 ak 2 2 p 1.mod p/ và ak thuộc tập hợp f1I 2I : : : I p 1g, như vậy là có số chính ...