THÔNG TIN CHUNG VỀ SÁNG KIẾN
1. Tên sáng kiến: THẶNG DƯ BẬC CAO
2. Lĩnh vực áp dụng sáng kiến:Chương trình Toán lớp 10 và 11 chuyên.
3. Thời gian thực hiện sáng kiến:Từ 9- 2015 đến 5 – 2016.
4. Tác giả:
Họ và tên: Trần Văn Huyến.
Năm sinh: 1984.
Nơi thường trú: Số nhà 13/16 đường Trần Nhật Duật thành phố Nam Định.
Trình độ chuyên môn: Thạc sĩ.
Chức vụ công tác: Giáo viên.
Nơi làm việc: Trường THPT chuyên Lê Hồng Phong Nam Định.
Địa chỉ liên hệ: Trường THPT chuyên Lê Hồng Phong Nam Định.
Điện thoại: 0935086607.
5. Đồng tác giả: Không
6. Đơn vị áp dụng sáng kiến:
Tên đơn vị:Trường THPT chuyên Lê Hồng Phong.
Địa chỉ: 76 đường Vị Xuyên, TP Nam Định.
Điện thoại: 0350640297.
BÁO CÁO SÁNG KIẾN
I.
ĐIỀU KIỆN HOÀN CẢNH TẠO RA SÁNG KIẾN
Số học là một nhánh của toán học ra ra đời từ rất sớm, ngay từ khi xuất hiện các con
số. Tuy nhiên đến ngày nay số học vẫn là một nhánh của toán học chứa đựng nhiều kì
thú, bất ngờ và nhiều bí mật lớn chưa có lời giải đáp. Đối với học sinh, các em đã được
tiếp cận với các con số từ những bậc học tiểu học thậm chí sớm hơn. Đến bậc trung học
cơ sở các em thực sự đã biết và giải được một số bài toán về phép chia hết và phép chia
có dư và số học trở thành môn học bắt buộc không thể thiếu đối với tất cả các em học
sinh. Trong các kì thi HSG Quốc Gia, thi Olympic toán học quốc tế...thì các bài toán số
học thường xuất hiện như một chủ đề bắt buộc mặc dù đây là một trong những bài toán
khó nhất trong khi xuất hiện trong các đề thi ở VMO, TST, IMO... Tuy nhiên có thể nhận
thấy rằng phần nhiều bài toán là chứng minh hoặc giải quyết các vấn đề về chia hết hoặc
chia có dư. Chính vì vậy tác giả đã viết sáng kiến này để trình bày về một mảng quan
trọng trong số học đó là thặng dư bậc cao và từ đó học sinh có thể vận dụng những lý
thuyết và kĩ năng vào việc giải một số bài toán về chúng.
Chúng ta hãy quay lại vấn đề thặng dư với một câu hỏi sau đây: Cho trước hai số
nguyên a và n với n > 0. Có tồn tại hay không số nguyên x sao cho x có số dư là a khi
chia cho n?”
Câu hỏi trên còn diễn đạt khác là: Cho trước hai số nguyên a và n với n 0 . Có tồn tại
hay không số nguyên x thỏa mãn x a mod n ? Câu trả lời như chúng ta đã biết! số x như
vậy luôn tồn tại và bằng x a kn ,k Z . Thậm chí Qin Jiushao một nhà toán học
Trung Hoa còn chứng minh được một vấn đề tổng quát hơn đó là luôn tồn tại số nguyên x
thỏa mãn đồng thời nhiều đồng dư tuyến tính x ai mod mi , i 1, k miễn rằng các ni
nguyên tố cùng nhau đôi một, tức là ni , n j 1, i, j thỏa mãn 1 i j k . Tuy nhiên từ
câu hỏi ở trên chúng ta thử liên hệ và đặt ra hai câu hỏi sau đây.
a) Cho trước các số nguyên n và a với n > 0 và a,n = 1 . Có tồn tại hay không số
nguyên x thỏa mãn x 2 = a modn ?
Tổng quát hơn ta xét ví dụ sau đây.
b) Cho trước các số nguyên n và a với n > 0 và a,n = 1 . Và với m là một số
nguyên
sao cho m 2. Có tồn tại hay không số nguyên x thỏa mãn
x m a modn ?
Nội dung của sáng kiến kinh nghiệm này là đi tìm và trình bày lời giải đáp cho hai câu
hỏi ở trên và các ứng dụng của chúng trong việc giải một số bài toán liên quan thường
xuất hiện trong các đề thi học sinh giỏi như VMO, TST, IMO...và xuất hiện trên trang
web toán học thi olympic quốc tế. Chẳng hạn chúng ta xét một số bài toán sau đây:
http://imomath.com. Chứng minh rằng 4kxy 1 không thể là ước của xm y n với mọi
m,n,k , x, y nguyên dương.
http://imomath.com. Chứng minh rằng không tồn tại x, y, z N sao cho 4 xyz x y là số
chính phương.
http://imomath.com. Chứng minh rằng với mọi x, y, z nguyên dương thì
x2 y 2 z 2
3 xy yz zx
không thể là một số nguyên.
Việt nam TST 2005. Cho p là một số nguyên tố với p 1mod8 . Tính tổng
p 1
k2
S .
k 1 p
Bankan Mathematical Olympiad. Giải phương trình nghiệm nguyên
x5 4 y 2 . (2)
IMO Short list 1991. Cho a, b, c là các số nguyên và p là một số nguyên tố lẻ. chứng
minh rằng nếu f x ax 2 bx c là số chính phương tại 2 p 1 giá trị nguyên liên tiếp
của x thì p | b2 4ac .
Và còn nhiều bài toán khác nữa mà việc giải chúng đòi hỏi học sinh những kỹ năng tốt
và được trang bị tốt các kiến thức về đồng dư. Thặng dư bậc cao cung cấp cho học sinh
những kiến thức và kĩ năng tốt nhất để giải các bài toán dạng này thậm chí giúp cho các
em có cái nhìn hệ thống và tổng quát hơn về bài toán chia hết và bài toán giải phương
trình nghiệm nguyên.
II.
MÔ TẢ GIẢI PHÁP
1. Mô tả giải pháp trước khi tạo ra sáng kiến
Thặng dư bậc cao là một nội dung khó nhưng đầy lý thú trong số học, một mặt nó xuất
phát từ những bài toán đơn giản ngay cả đối với các học sinh bậc trung học cơ sở, một
mặt chúng lại chứa đựng những bí ẩn, những kiến thức toán học rất khó mới có thể tiếp
cận được chúng. Những kiến thức cơ bản liên quan đến thặng dư bậc cao đó là đồng dư
modulo, định lý Euler, định lý Fecma, cấp của một số, căn nguyên thủy, hệ thặng dư,
định lý số dư Trung Hoa...và đòi hỏi một số kiên thức nhất định về về đa thức.
Là một giáo viên dạy trường chuyên, chúng tôi nhận thấy rằng cần phải có một đề tài
nghiên cứu về dạng toán này để giúp các em học sinh lớp chuyên Toán bổ xung các kiến
thức cơ bản đồng thời phát triển tư duy và kĩ năng giải toán, giúp các em không còn lúng
túng khi gặp các bài toán dạng này. Hy vọng nội dung của sáng kiến này sẽ giúp các em
học sinh tìm ra được các phương pháp hợp lí để giải quyết những bài toán dạng này.
2. Mô tả giải pháp sau khi có sáng kiến
a. Phương pháp
Một bài toán sử dụng thặng dư bậc cao ban đầu phải có dấu hiệu của chia hết hoặc có
dấu hiệu của một binhg phương (đối với thặng dư bậc 2)...Từ đây chúng ta khái quát và
sử dụng các lý thuyết thặng dư bậc cao để xử lý chúng.
b. Nội dung
Nội dung của sáng kiến này được tác giả chia làm hai chương.
Chương 1. Thặng dư bình phương. Nội dung chương này chính là trình bày lời giải
đáp cho câu hỏi thứ nhất và các ứng dụng của thặng dư bình phương. Trong đó tác giả
trình bày vắn tắt các định lý và tính chất và các hệ quả quan trọng của thặng dư bậc 2 và
nhiều ứng dụng trong việc giải một số các liên quan như bài toán chia hết, bài toán
nghiệm nguyên thường xuất hiện trong các đề thi như VMO, TST, IMO...
Chương 2. Thặng dư bậc k. Chương này là một bước phát triển tiếp theo của chương
1 nhằm tìm kiếm lời giải đáp cho câu hỏi thứ 2, tuy nhiên việc làm này đòi hỏi một số
kiến thức về cấp của một số và căn nguyên thủy, định lý thặng dư Trung Hoa mà những
kết quả này được tác giả trình bày tóm tắt hoặc nhắc lại mà không chứng minh và một số
ứng dụng của thặng dư bậc k để giải phương trình thặng dư bậc cao và phần cuối là một
số các bài tập xây dựng ra để củng cố chắc nội dung của lý thuyết thặng dư bậc k.
MỤC LỤC
BẢNG KÍ HIỆU ...................................................................................................................................... 1
CHƯƠNG 1. THẶNG DƯ B ẬC 2 ...................................................................................................... 2
A. Lý thuyết........................................................................................................................................ 2
Định nghĩa 1.2. Giả sử p là một số nguyên tố và a là một số nguyên. Kí hiệu ........................ 2
Định lý 1.5 (Tiêu chuẩn Euler). Cho p là một số nguyên tố. Khi đó:....................................... 4
Định lý 1.10 (Luật tương hỗ Gauss). Nếu p và q là các số nguyên tố lẻ phân biệt thì........... 7
Định lý 1.14. Cho n là số nguyên dương có khai triển ra thừa số nguyên tố là
n p1 . p2 ... pk (ở đó pi là các số nguyên tố và i là các số nguyên không âm) và a là số
1
2
k
nguyên tố cùng nhau với n, khi đó a là số chính phương modulo n khi và chỉ khi a là số
chính phương modulo pi i 1, k . .............................................................................................. 12
i
B. Bài tập và ứng dụng .................................................................................................................. 13
CHƯƠNNG 2. THẶNG DƯ B ẬC k ................................................................................................. 31
A. Lý thuyết...................................................................................................................................... 31
Định nghĩa 2.1. Cho m, n là các số nguyên dương m 2 và a là một số nguyên sao cho
a, n 1 , khi đó nếu tồn tại số nguyên x sao cho
x m a modn thì số a được gọi là thặng dư
bậc m modulo n, ngược lại thì số a được gọi là không thặng dư bậc m modulo n................. 31
Định lý 2.13. Cho p là một số nguyên tố lẻ và gcd a, p 1 thì x m a mod p giải được nếu
và chỉ nếu a
p 1
d
1 mod p , ở đó d gcd m , p 1 . ..................................................................... 37
Định lý 2.14. Nếu p là một số nguyên tố lẻ, q là một căn nguyên thủy của p và
d gcd m, p 1 , thì tất cả các thặng dư cấp m của p theo modulo p được cho bởi
p 1
d.
d 2d
q , q ,..., q d ............................................................................................................................. 37
Định nghĩa 2.15 (Chỉ số số học của một số). Đặt n là một số nguyên dương và q là một căn
nguyên thủy của n. Nếu số nguyên a thỏa mãn a,n = 1 thì tồn tại duy nhất một số nguyên x
với 1 x n sao cho q x a modn . Số x được gọi là chỉ số của a cơ số q modulo n và
được kí hiệu ..................................................................................................................................... 39
Định lý 2.16. Cho n là một só nguyên dương với căn nguyên thủy q và hai số a, b nguyên tố
cùng nhau với n. Khi đó: ................................................................................................................ 39
Định lý 2.17. Cho n là k.indq x indq a mod n số nguyên dương và giả sử tồn tại căn
nguyên thủy của n. Nếu k là số nguyên dương và a nguyên tố cùng nhau với n thì phương
trình đồng dư x k a mod n (1) có nghiệm nếu và chỉ nếu....................................................... 41
B. Bài tập .......................................................................................................................................... 42
TÀI LIỆU THAM KHẢO .................................................................................................................. 45
BẢNG KÍ HIỆU
n : Các số nguyên tố với n trong tập 1, 2,...,n 1 .
x @a mod n : x không đồng dư với a theo modulo n.
a | b : a là ước của b.
a | b : a không là ước của b.
a
: Kí hiệu Legender.
n
a, n 1 :
a và n nguyên tố cùng nhau.
gcd a, b : Ước chung lớn nhất của a và b.
Trang 1
CHƯƠNG 1. THẶNG DƯ BẬC 2
A. Lý thuyết
Định nghĩa 1.1. Cho a và n là hai số nguyên tố cùng nhau và n 1 . Nếu tồn tại số
nguyên x sao cho x 2 a modn thì số a được gọi là thặng dư bình phương modulo n hay
a còn được gọi là số chính phương modn nếu ngược lại thì số a được gọi là không
thặng dư bình phương modn hay a còn được gọi là số không chính phương modn .
Ta xét một ví dụ đơn giản sau đây
Ví dụ 1. Với n 19 . Xét các số nguyên dương chính phương modulo 19 nhỏ hơn 19.
11 182 1 mod19 ,
22 17 2 4 mod19 ,
32 162 9 mod19 .
42 152 16 mod19 ,
52 142 6 mod19 ,
62 132 17 mod19 .
7 2 122 11 mod19 ,
82 112 7 mod19 ,
92 102 5 mod19 .
Như vậy có 9 số 1, 4,5,6,7,9,11,16,17 là các số chính phương mod19 và 9 số còn lại
2,3,8,10,12,13,14,15,18 không là các số chính phương mod19 .
Trong trường hợp n p ký hiệu sau đây lần đầu được Legendre giới thiệu vào năm
1798 trong nỗ lực tìm kiếm chứng minh cho định lý cuối cùng của Fecma
Định nghĩa 1.2. Giả sử p là một số nguyên tố và a là một số nguyên. Kí hiệu
1 nÕu a lµ sè chÝnh ph¬ng modp ,
a
p = 1 nÕu a kh«ng lµ sè chÝnh ph¬ng modp ,
0 nÕu p lµ mét íc cña a.
Trong ví dụ đã đưa ra ở trên khi xét các số nguyên dương chính phương mod19 ta
thấy rằng có 9 số là chính phương mod19 và 9 số còn lại không là số chính phương
mod19 trong tập các số nguyên 1, 2,...,18 . Từ đây gợi ý cho ta đưa ra phỏng đoán rằng
p 1
p 1
các số là chính phương mod p và
số không là số chính
2
2
phương mod p trong tập các số 1, 2,.., p 1 ? Định lý sau là câu trả lời cho phỏng đoán
phải chăng có
này.
Định lý 1.3. Cho p là một số nguyên tố.
a) Nếu p 2 thì 1 là số chính phương modulo p.
Trang 2
b) Nếu p lẻ thì có đúng
p 1
số chính phương modp trong tập các số nguyên
2
p 1
1, 2,..., p 1 được cho bởi: 1 , 2 , . . . ,
.
2
2
2
2
Chứng minh.
a) Hiển nhiên
b) Ta đặt S1 1,2,...,
p 1
và S 1, 2,..., p 1 .
2
Ta chứng minh rằng i, j S1 thì i 2 @ j 2 mod p . Thật vậy giả sử ngược lại
i 2 j 2 mod p i j i j Mp
1 i, j
tuy nhiên vì
i j i @ j mod p
mặt khác vì
p 1
2 i j p 1 suy ra i j không chia hết cho p suy ra mâu thuẫn. Vậy
2
i 2 @ j 2 mod p . Mặt khác i S1 p i S \ S1 và vì p i i 2 mod p từ đó suy ra tập
2
các số chính phương trong tập S bằng tập các số chính phương trong S1 . Bây giờ để hoàn
thiện chứng minh định lý ta chỉ cần chỉ ra rằng h S và h là số chính phương thì luôn
tồn tại i S1 sao cho i 2 h mod p . Thật vậy nếu h là số chính phương mod p suy ra
luôn tồn tại i S sao cho i 2 h mod S . Nếu i S1 thì suy ra điều phải chứng minh. Nếu
i S \ S1 p i S1 mặt khác i 2 p i mod p . Ta có điều phải chứng minh # .
2
Ví dụ 2. Với p 17 các số chính phương mod17 trong trong tập 1, 2,...,16 là
12 mod17 1 ,
22 mod17 4 ,
32 mod17 9 ,
42 mod17 16 ,
52 mod17 8 ,
62 mod17 2 , 7 2 mod17 15 và 82 mod17 13 .
Mặc dù định lý 1.3 chỉ ra rằng một nửa các số trong tập 1, 2,...,p 1 là các số chính
phương, tuy nhiên ta cần một công cụ hữu hiệu hơn để chỉ ra đâu là một số chính phương
mod p trong tập các số nguyên tố cùng nhau với p? Câu trả lời được Euler tìm ra vào
năm 1755.
p21
a 1 modp
Định lý 1.4. Nếu p là số nguyên tố lẻ và gcd a, p 1 thì: p 1
a 2 1 modp .
Chứng minh.
Trang 3
Theo định lý nhỏ Fecma thì nếu p là số nguyên tố lẻ và gcd a, p 1 thì a p 1 1 mod p .
Mặt khác a p1 1 a
a
p 1
2
p 1
2
p 1
p21
2
suy
ra
hoặc
a
1 mod p hoặc
1 a 1 0 mod p
1 mod p # .
Định lý 1.5 (Tiêu chuẩn Euler). Cho p là một số nguyên tố. Khi đó:
a) Nếu p 2 thì mọi số a lẻ đều là số chính phương modp .
a
b) Nếu p 2 và gcd a, p 1 thì a
p
Chứng minh.
a) Nếu p 2 .
p 1
2
modp .
vì a lẻ suy ra a có dạng a 2k 1. Đặt x 2m 1 ta có x 2 a 2m 1 2k 1
2
2 2m2 2m k 0 mod 2 suy ra a là số chính phương mod p .
b) Nếu p 2 .
Giả sử a là số chính phương mod p khi đó tồn tại x Z sao cho x 2 a mod p , do
a, p 1 x, p 1 . Theo định lý Fecma x p1 1 mod p , mặt khác x p1 a
từ đó suy ra a
p 1
2
p 1
2
mod p
1 mod p .
Bây giờ ta chứng minh rằng nếu a không là số chính phương
a
p 1
2
mod p thì
1 mod p . Với mỗi số 1 r p 1 tồn tại duy nhất một số x 1, 2,..., p 1 sao
cho rx a mod p . Vì a không là số chính phương mod p suy ra r x và các số
1, 2,..., p 1 được chia thành
p 1
cặp r , x mà rx a mod p . Theo định lý Wilson ta
2
có,
1 p 1! rx
p 1
2
a
p 1
2
mod p .
p 1
a
Vậy ta có khẳng định a 2 mod p # .
p
Ví dụ 3. Xét số nguyên tố p 47 ta có
47 1
5
5
2
5
523 54 .53 1 mod 47 .
47
Trang 4
Suy ra không tồn tại x để x 2 5 mod 47 .
47 1
11
7
2
7 23 7 2 .7 1 mod 47 .
7
47
Suy ra không tồn tại x để x 2 7 mod 47 có nghiệm.
Một số hệ quả sau đây được suy ra trực tiêp từ định lý 1.5
Hệ quả 1.6. Cho một số nguyên tố và số nguyên a sao cho a, p 1 . Khi đó nếu
a b modp thì
a b
.
p p
Hệ quả1.7. Nếu p là một số nguyên tố lẻ và p, ab 1 thì
ab a b
.
p p p
k
Hệ quả 1.8. Cho p là số nguyên tố và số nguyên có phân tích n pi sao cho
i
i 1
n, p 1 thì
i
n k pii k pi
.
p i 1 p i 1 p
Ví dụ 4. Kiểm tra số 77 có là số chính phương modulo 19 hay không?
77
7.11 7 11
Ta có
, mặt khác ta có
19 19 19 19
19 1
2
191
2
77
119 1 mod19 suy ra 1 . Như vậy số 77 là số
19
chính phương modulo 19, tức là phương trình x 2 77 mod19 có nghiệm.
7
79 1 mod19 và 11
200
Ví dụ 5. Tính
.
37
37 1
37 1
5
100 2 5 2
2
1 mod 37 và 5 2 1 mod 37 .
Ta có
, 37 2
37
37 37 37
3
2
200
Vậy
1 . 1 1.
37
3
2
Trang 5
Mặc dù tiêu chuẩn Euler là một cách hữu hiệu để xác định một số có là số chính
phương hay không. Tuy nhiên một kết quả rất quan trọng về số chính phương được
Gauss phát hiện ra vào năm 1808 đó là luật thuận nghịch hay còn gọi là luật tương hỗ
Gauss. Luật tương hỗ Gauss là một công cụ hữu hiệu để biến đổi kí hiệu Legender.
a
Định lý 1.9 (Bổ đề Gauss . Cho p là số nguyên tố lẻ với a, p 1 , khi đó 1 , ở
p
s
p
1
đó s là số phần tử trong tập a, 2a,..., p 1 a và lớn hơn .
2
2
Chứng minh.
1
Đặt S là tập thặng dư dương nhỏ nhất theo modulo p của các số a, 2a,..., p 1 a .
2
p
p 1
và đặt r
s . Ta gán nhãn cho các phần
2
2
p
p
tử của tập S như sau S a1 , a2 ,..., ar , b1 , b2 ,..., bs , ở đó ai , i 1, r và b j , j 1, s .
2
2
1
Vì tập các số ai , bj là thặng dư dương nhỏ nhất của các số a, 2a,..., p 1 a nên ta có
2
Đặt s là số phần tử của tập S mà lớn hơn
r
s
a . b
i 1
i
j 1
j
a
p 1
2
p 1
.
! mod p .
2
p
p
, j 1, s 0 p b j , j 1, s . Xét tập a1 , a2 ,...,ar , p b1 , p b 2 ,...,p bs .
2
2
p 1
Tập này gồm
số. Ta chứng minh tập này gồm các số phân biệt.
2
Vì b j
Thật vậy giả sử tồn tại i , j sao cho ai p b j mod p ai b j 0mod p hay
ia ja 0 mod p i j a 0 mod p vì a, p 1 suy ra i j M
a điều này mâu thuẫn
vì 0 i, j
p 1
0 i j p, i 1, r ; j 1, s . Mặt khác
2
p bj 1
s
j 1
s
s
b mod p
j 1
j
p 1
r
s
r
s
p 1
s
s
p 1
2
, từ đó suy ra
! ai . p b j 1 ai . b j 1 a .
! mod p . Rút
2
2
i 1
j 1
i 1
j 1
p 1
a
gọn hai vế cho
! suy ra 1 .
2
p
s
Ví dụ 6. Xét xem số 20 có là số chính phương modulo 41 hay không?
Ta có
Trang 6
20, 40,60,..., 400 20, 40,19,39,18,38,17,37,16,36,15,35,14,34,13,33,12,32,11,31 mod 41 .
Có 10 số lớn hơn
p 1
10
20
20 s 10 . Vậy 1 1 mod 41 . Tức là 20 là số
2
41
chính phương modulo 41.
Định lý 1.10 (Luật tương hỗ Gauss). Nếu p và q là các số nguyên tố lẻ phân biệt thì
p 1 q 1
p q
.
2 2 .
1
q p
Chứng minh.
Ta xét p và q là hai số nguyên tố lẻ phân biệt. Với mỗi số k 1, 2,...,
p 1
đặt q k và
2
kq
rk là các số xác định bởi qk pqk rk với 1 rk p 1 , khi đó qk và rk là các
p
p
thặng dư dương nhỏ nhất của qk. Ta gọi a1 , a2 ,..., ar là các giá trị của rk nhỏ hơn
và
2
p
b1 , b2 ,..., bs là các giá trị của rk lớn hơn
, khi đó theo bổ đề Gauss
2
a1 , a2 ,..., ar , p b1 , p b2 ,..., p bs là các số phân biệt và trùng với tập các số nguyên
1, 2,...,
q
p 1
s
và 1 . Đặt
2
p
r
s
p 1
2
i 1
j 1
k 1
a ai và b b j . Khi đó a b rk .
r
s
p 1
2
i 1
j 1
k 1
Từ đó ai p b j sp a b k
p 1
2
p2 1
.(*)
8
p 1
2
qk
p 1
lấy tống 2 vế kq pqk rk theo 1 k
ta được
2
k 1 p
Đặt u qk
k 1
p 1
p21
p21 q p 2 1
2
. (**)
pu a b p qk a b pqk rk q k
k 1
k 1
8
k 1
p2 1
. q 1 . (***)
Lấy ** * ta được pu 2b sp
8
Trang 7
q
Lấy modulo 2 vế của (***) vì p q 1 mod 2 u s mod 2 . Do đó 1 1 .
p
s
u
q 1
2
jp
p
v
ta đạt được 1 .
j 1 q
q
Lặp lại quá trình này với p và q với v
q p
p 1 q 1
Suy ra 1 . Bây giờ ta chứng minh u v
.
.
p
q
2
2
u v
Xét tất cả các điểm lưới i, j , i, j Z
trên mặt phẳng sao cho
1 i
p 1
và
2
p 1 q 1
q 1
. Rõ ràng có
điểm như vậy. Ta xét đường thẳng (d) có phương
.
2
2
2
trình pj qi không có điểm lưới đang xét nào thuộc đường thẳng (d) vì nếu có suy ra q là
1 j
ước của pj nhưng vì p, q 1 j Mq mâu thuẫn vì 1 j
q 1
. Do đó các điểm lưới đang
2
xét hoặc nằm trên hoặc nằm dưới đường thẳng (d). Mặt khác các điểm lưới nằm dưới
đường thẳng (d) là
p 1
2
qi
u .
i 1 p
Các điểm lưới nằm trên đường thẳng (d) là
q 1
2
jp
v .
j 1 q
Từ đó ta có u v
p 1 q 1
q p
p 1 q 1
.
.
. Vậy ta có 1 2 2 # .
2
2
p q
Luật tương hỗ Gauss thực chất khẳng định rằng nếu p và q là hai số nguyên tố lẻ thì p
là số chính phương mod q khi và chỉ khi q là số chính phương mod p và ngược lại
ngoại trừ trường hợp p và q cùng đồng dư với 3 modulo 4 . Thật vậy vì ta có
1
p 1 q 1
.
2 2
1 p q 3 mod 4 . Hay nói cách khác ta có hệ quả sau đây.
Hệ quả 1.11. Cho p và q là các số nguyên tố lẻ khi đó
Trang 8
p q
a) Nếu p @3 mod4 hoặc q @3 mod4 thì .
q p
p
q
b) Nếu p q 3 mod4 thì .
q
p
Ví dụ 7. Xét phương trình x 2 73 mod 419 có nghiệm hay không?
731 419 1
73 419
.
7524
2
2
Áp dụng luật tương hỗ Gauss ta có
.
1
1
1 . Mặt khác
419 73
3
731
3
7321
419 54 2.3 2 3
73
3
2
.
2
.
3 1.1 1
1.
419
73 73 73 73 73
3
Vậy phương trình x 2 73 mod 419 có nghiệm.
Ví dụ 8. Xét phương trình x 2 11 mod 293 (1) có nghiệm hay không?
Trước hết ta có 11 3 mod 4 và 293 1 mod 4 . Xét phương trình liên kết tương ứng
111
293 7
2
x 2 293 mod11 (2). Ta có
7
1 mod11 suy ra (2) vô nghiệm. Sử
11 11
dụng hệ quả 1.11 suy ra (1) có nghiệm.
Định lý 1.12. Cho p là một số nguyên tố lẻ và số nguyên a nguyên tố cùng nhau với p khi
đó a là số chính phương modulo p khi và chỉ khi a là số chính phương modulo
pk , k Z , k 1 .
Chứng minh.
“Phần thuận” Giả sử a là số chính phương mod p k với k 1 khi đó tồn tại số nguyên x
sao cho x2 a Mpk x2 a Mp hay x 2 a mod p , do đó a là số chính phương mod p .
“Phần đảo” Ngược lại giả sử a là số chính phương modulo p ta chứng minh a là số chính
phương mod p k với k 1 bằng quy nạp.
Thật vậy k 1 khẳng định hiển nhiên đúng.
2
- Giả sử khẳng định đã đúng đến k, tức là tồn tại xk sao cho xk a mod p
-
xk2 a tp k , t Z .
-
Đặt xk 1 xk sp k xk21 xk2 2sxk p k s2 p2 k a p k 2sxk t s2 k p2 k ,
Trang 9
trong đó số nguyên s thỏa mãn 2sxk t mod p . Số nguyên s là tồn tại vì 2 xk , p 1 . Ta
có Vì 2sxk t Mp suy ra xk21 a mod p k 1 . Vậy a là số chính phương mod p k 1 # .
Ví dụ 9. Tìm nghiệm của phương trình x 2 6 mod 25 (*).
Trước hết ta nhận thấy phương trình x 2 6 mod 5 1 mod 5 và 1 6 1 .5 t 1
và x1 1 mod5 . Bây giờ ta xác định số nguyên s sao cho 2s 1 0 mod5 . Phương trình
này tương đương 2s 1 mod5 s 3 mod5 và 1 nghiệm của (*) bé hơn 25 là
1 5.3 16 . Do vậy nghiệm của (*) là x 16 mod 25 hay x 9 mod 25 .
Bây giờ ta xét trong trường hợp p là số nguyên tố chẵn tức p 2 . Xét n 2k ,
k 1, k Z . Ta có định lý sau đây.
Định lý 1.13. Cho số nguyên a và số n 2k , k 2, k Z . Khi đó:
1) Nếu k 1 thì 1 a 1 mod 2 .
n 2
a
a
2) Nếu k 2 thì 2 2 1 a 1 mod 4 .
2 2
a
a
3) Nếu k 3 thì k 1 a 1 mod8 .
n 2
Chứng minh.
1) Hiển nhiên.
2) Giả sử a là số chính phương mod 4 suy ra tồn tại x sao cho x 2 a mod 4 . Vì a lẻ
a
a
suy ra x lẻ. Đặt x 2k 1 x 2 2k 1 1 mod 4 a 1 mod 4 . Đảo lại giả sử a lẻ và
2
a 1 mod 4 a 4h 1,
đặt
x 2k 1 x 2 2k 1 1 4h mod 4 ,
2
hay
x a mod 4 .
2
3) Giả sử a là số chính phương mod 2k , k 3 suy ra tồn tại x thỏa x2 a mod 2k .
8 và vì
Vì a lẻ suy ra x lẻ. Đặt x 2k 1 x 2 2k 1 4k k 1 1 . Vì k 3 2k M
2
k k 1M
2 4k k 1M
8 x2 4k k 1 1 1 mod 23 , do đó x 2 4k k 1 1 1 mod8
. Vậy a 1 mod8 # .
Trang 10
Đảo lại giả sử a 1 mod8 hay a 1 8h . Ta chứng minh a là số chính phương
mod 2 , k 3 .
k
Nếu k 3 hiển nhiên.
- Nếu k 3 . Đặt n 2k 3 ta xét tập A gồm n số nguyên sau
-
1.2 3.4
2i 1 2i ,..., 2n 1 2n .
A ,
,...,
2
2
2 2
Ta chứng minh rằng tập A gồm n số phân biệt theo modulo n. Thật vậy
- Rõ ràng tập A gồm n số.
- Giả sử trong A có hai số trùng nhau theo modulo n tức là:
2i 1 2i 2 j 1 2 j
mod n
2
suy ra i j 2i 2 j 1 0 mod n . Mặt khác 2i 2 j 1, n 1 i j Mn điều này mâu
2
thuẫn vì i , j phân biệt và 1 i, j n . Như vậy ta đã chứng minh được rằng tập A là n giá
trị phân biệt theo modulo n do đó mọi số nguyên đều đồng dư với một phần tử nào đó của
tập A theo modulo n. Từ chứng minh trên suy ra với a 1 8h , tồn tại một phần tử thuộc
A đồng dư với h theo mod n .
Giả sử
2i 1 2i h
2
mod n 8i 2i 1 8h mod8n 4i 1
2
1 8h mod8n hay
x 2 a mod 2k . Định lý được chứng minh.
Ví dụ 10. Tìm nghiệm của phương trình x 2 17 mod 25 .
Trước hết ta tìm số r sao cho r 2 17 mod 24 r 1 vì 12 1 17 24 1 . Ta đặt s là
số thỏa mãn s r 23.k s 2 r 2 k.24 mod 25 17 k 1.24 mod 25 . Từ đây ta
chọn k 1,3 suy ra s 9,25 9,7 mod 25 . Vậy tất cả x thỏa mãn theo modulo 2 5 là
9, 7 .
Trang 11
Định lý 1.14. Cho n là số nguyên dương có khai triển ra thừa số nguyên tố là
n p1 . p2 ... pk (ở đó pi là các số nguyên tố và i là các số nguyên không âm) và a là số
nguyên tố cùng nhau với n, khi đó a là số chính phương modulo n khi và chỉ khi a là số
chính phương modulo pi i 1, k .
Chứng minh.
1
2
k
i
“ ” Giả sử a là số chính phương mod n suy ra tồn tại số nguyên x sao cho x2 a Mn ,
n p11 . p22 ... pkk x 2 a Mpii , i 1, k a
mặt khác vì
là số chính phương
mod p , i 1, k .
i
i
“ ” Giả sử a là số chính phương modulo pi , i 1, k . Khi đó tồn tại xi N sao cho
i
xi2 a mod pii , i 1, k . Vì các pii nguyên tố cùng nhau, theo định lý thặng dư Trung
Hoa tồn tại số nguyên x thỏa x xi mod pi x2 xi2 mod pi , i 1, k x2 a mod n
i
i
do đó a là số chính phương modulo n. Định lý được chứng minh # .
Từ các kết quả ở trên ta rút ra kết luận khi nào a là một chính phương mod n với n là
một số nguyên dương bất kỳ và a, n 1 .
Hệ quả 1.15. Cho số nguyên a và n là số nguyên dương bất kỳ sao cho a, n 1 , khi đó a
là số chính phương mod n khi và chỉ khi:
1) a là số chính phương mod p với mọi số nguyên tố lẻ p là ước của n và
2) a 1 mod 2 nếu 2 là ước của n; a 1 mod 4 nếu 2 2 là ước của n, và a 1 mod8
nếu 2 k là ước của n với mọi k nguyên và k 3 ..
Ví dụ 11. Kiểm tra xem 17 có là số chính phương mod 2100 hay không?
Ta có phân tích ra thừa số nguyên tố 2100 22.3.52.7 . Bây giờ ta kiểm tra tính chính
phương mod p của 17 với lần lượt 2 2 , 3, 52 , 7. Ta có
17
2 1 vì 17 1 mod 4 .
2
17 2
1 .
3 3
51
7 1
17 17 2
17 3
2
2
2
mod
5
1
3
và
mod 7 1 .
2
5 5 5
7 7
Vậy 17 không là số chính phương mod 2100 .
Trong trường hợp n là một số nguyên dương bất kì, kí hiệu sau đây được Jacobi đưa
ra vào năm 1846 trong một bài báo của Crelle. Về thực chất đây là một mở rộng của kí
Trang 12
hiệu Legendre. Đặt n p1 . p2 ... pk và a là một số nguyên dương, kí hiệu Jacobi được
định nghĩa là
1
2
k
i
a k a
.
n i 1 pi
Cũng giống như kí hiệu Legendre, kí hiệu Jacobi cũng có đầy đủ các tính chất đã
được xét. Cụ thể là:
1) Nếu a b mod n thì ,
n n
a
b
a
a a
2)
,
mn
m n
ab
a b
3)
,
n n n
n 1
1
4) 1 2 nếu n lẻ,
n
n 1
2
5) 1 8 ,
n
n 1 m 1
n m
4
6)
với m, n lẻ và nguyên tố cùng nhau.
1
m n
2
Tuy nhiên có một điểm khác biệt giữa kí hiệu Jacobi và kí hiệu Legender là đối với kí
hiệu Jacobi thì nếu 1 thì phương trình x 2 a mod n chưa chắc có nghiệm tuy
n
a
nhiên nếu 1 thì phương trình x 2 a mod n vô nghiệm.
n
a
B. Bài tập và ứng dụng
Thặng dư bình phương được ứng dụng nhiều trong phương trình nghiệm nguyên hoặc
tính chất chia hết của số nguyên. Trước hết ta xét một số bài toán cơ sở sau đây.
Bài 1. Cho p là một số nguyên tố. Hãy xác định điều kiện p để 1 là số chính phương
mod p .
Lời giải.
a) Trường hợp p 2 .
Ta chỉ cần chọn x là số lẻ x 2k 1 khi đó x 2 2k 1 1 1 mod 2 . Suy ra định lý
2
đúng trong trường hợp p 2 .
Trang 13
- Xem thêm -
.PDF 
52 
330 
66 
