Chuyên đề Thặng dư bình phương - Chuyên Toán 10
Chuyên đề Thặng dư bình phương - Chuyên Toán 10. Tài liệu được sưu tầm giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem.
Chủ đề: Chuyên đề Toán 10 225 tài liệu
Môn: Toán 10 3.2 K tài liệu
Tác giả:
Preview text:
THẶNG DƯ BÌNH PHƯƠNG
(Dành cho học sinh từ đội dự tuyển trở lên).
A. YÊU CẦU CẦN ĐẠT
- Nhận biết được định nghĩa và các tính chất của thặng dư bình phương.
- Hiểu và vận dụng được kí hiệu Legendre và các tính chất: tiêu chuẩn Euler, bổ đề Gauss,
luật thuận nghịch Gauss….
- Vận dụng được để giải các bài toán số học về chia hết, ước số, sự tồn tại, biểu diễn số
nguyên và phương trình nghiệm nguyên.
B. NỘI DUNG KIẾN THỨC 1. LÝ THUYẾT
Trước hết ta định nghĩa thặng dư bình phương của một số theo modulo n, trong đó n là số nguyên dương lớn hơn 1.
Định nghĩa 1. Cho số nguyên dương n số nguyên dương a nguyên tố cùng nhau với n được gọi
là một thặng dư bình phương mod n (hoặc số chính phương mod n) nếu phương trình 2
x a(mod n) có nghiệm, trường hợp trái lại ta nói a là bất thặng dư bình phương (không chính phương) modulo n. Nhận xét.
Rõ ràng một số chính phương sẽ là một số chính phương (mod n) với mọi số nguyên dương n.
Nếu a là một thặng dư bình phương modulo n và a b(mod n), thì b cũng là một thặng
dư bình phương modulo n.
Định nghĩa 2. (kí hiệu Legendre): Cho p là một số nguyên tố lẻ, số nguyên a nguyên tố cùng a
nhau với p. Kí hiệu Legendre xác định như sau: p a 1
nếu a là một thặng dư bình phương modulo p p a 1
nếu a là bất thặng dư bình phương modulo p. p a
Chú ý: Trong tài liệu còn định nghĩa cho trường hợp a p là 0 p
Định lí 1. Cho số nguyên tố lẻ p, số nguyên a nguyên tố cùng nhau với p, khi đó: Phương trình 2
x a (mod p) hoặc vô nghiệm, hoặc có đúng 2 nghiệm đồng dư modulo p.
Trong số các số 1, 2, ..., p 1 có chính xác số thặng dư bình phương và số bất thặng dư p 1
bình phương theo modulo p cùng là . 2
Chứng minh. Giả sử a là một thặng dư bình phương mod .
p Ta thấy rằng nếu b là một trong các
số thuộc 1, 2,..., p 1 thì 2 2
b ( p b) (mod p). Do đó phương trình 2
x a(mod p) có đúng 2
nghiệm mà bình phương có cùng thặng dư a theo modulo p (vì tập 1, 2,..., p 1 là một hệ thặng
dư thu gọn modulo p).
Đặt S 1, 2,..., p 1 , 1
S 1, 2,...,( p 1) / 2 . Với mỗi i 1
S , gọi ir là số (dương nhỏ nhất) mà 2
i r (mod p). i
Ta thấy rằng ir rj nếu i j. Thật vây, nếu 2 2
r r i j 0(mod p) (i j)(i j) 0(mod p). i j Nhưng điều này không
xảy ra vì i j, i j điều không chia hết cho p do 1 i j i j . p Vậy tập A 2
r S | r i (mod p), i S 1 , i i
có A ( p 1) / 2. Ta chứng minh A là tập tất các số
chính phương modulo p trong S. Thật vậy, mỗi số thuộc A đều là số chính phương (mod p).
Ngược lại, giả sử a S sao cho 2
a k (mod p) với k S. Nếu k 1
S thì a r . k A Nếu k 1 S
thì b p k 1 S và ta có 2
a b (mod p) (do 2 2
k ( p k ) (mod p) ) do đó a r . b A p 1 r
Hệ quả. Với mỗi số nguyên tố lẻ p , ta có 0. p r 1
Định lí 2. (Tiêu chuẩn Euler) Với p là số nguyên tố lẻ và số nguyên a thỏa mãn (a, p) 1, khi đó p 1 a 2 a (mod p). p a
Chứng minh. Xét trường hợp 1. Khi đó đồng dư 2
x a(mod p) có nghiệm x 0 x . Theo p
định lý Fermat bé, ta có p 1 p 1 2 2 2 p a ( 0 x ) 0
x 1 1(mod p). Do đó p 1 a 2 a (mod p). p a Trường hợp 1.
Khi đó phương trình đồng dư 2
x a(mod p) vô nghiệm. p 1
Với mỗi i 1, 2,..., p
1 tồn tại duy nhất j,1 j p 1 sao cho .
i j a(mod p), rõ ràng i j (vì phương trình 2
x a(mod p) vô nghiệm), nên các số thuộc tập 1, 2,..., p 1 phân thành
p 1 cặp, sao cho tích hai số trong mỗi cặp đều đồng dư với a theo modulo p. 2 p 1 Từ đó 2 ( p 1)! a
(mod p), mặt khác theo định lý Wilson thì ( p 1)! 1 (mod p). p 1 a Do đó 2 a (mod p). p
Định lý được chứng minh. p 1 1
Hệ quả. Với mỗi số nguyên tố p 2 , chúng ta 2 (1) . p
Như vây, phương trình đồng dư 2
x 1 (mod p) có nghiệm khi và chỉ khi p 2 hoặc p 1 (mod 4) . Phương trình đồng dư 2
x 1(mod p) vô nghiệm khi và chỉ khi p 1 (mod 4).
Định lí 3. (Kí hiệu của Legendre có tính chất nhân) Giả sử p là số nguyên tố lẻ, a và b là những số nguyên. Khi đó: a b
i) Nếu a b(mod p), thì p p ab
a b ii) . p p p 2 a
iii) Nếu (a, p) 1. thì 1. p Chứng minh.
i) Nếu a b(mod p), thì phương trình 2
x a(mod p) có nghiệm khi và chỉ khi phương trình 2 a b
x b(mod p) có nghiệm. Vậy . p p
ii) Nếu a hoặc b chia hết cho p thì khẳng định của định lý hiển nhiên đúng.
Bây giờ ta xét trường hợp cả a và b không chia hết cho p. p 1 p 1 p 1 ab
a b
Theo tiêu chuẩn Euler, ta có 2 2 2 (ab) a .b . (mod p). p p p 2 ab
a b Vì và ,
chỉ nhận các giá trị 1 hoặc -1, mà p 2 nên không thể xảy ra trường hợp p p p ab
a b
1 1(mod p), do đó . . p p p a 2
a a a iii) Vì 1, theo ii) ta có . 1. p p p p
Nhận xét: Tích của hai thặng dư bình phương hoặc hai thặng dư bất bình phương là một thặng
dư bình phương, tích của một thặng dư bình phương với một thặng dư bất bình phương là một
thặng dư bất bình phương.
Định lí 4. (Bổ đề Gauss) Giả sử p là số nguyên tố lẻ, a là số nguyên dương không chia hết cho p. p 1
Nếu trong các số thặng dư dương bé nhất của các số nguyên a, 2a, 3a,...,
a có s thặng dư lớn 2 p a hơn thì (1)s. 2 p p 1
Chứng minh. Trong số các thặng dư dương bé nhất của các số nguyên a, 2a, 3a,..., a, 2 p p giả sử 1
u , u2,...,us là các thặng dư lớn hơn và 1
v , v2,..., t
v là các thặng dư bé hơn . 2 2 p 1
Vì ja, p 1 với mọi 1 j , nên mọi u ,
i v j đều khác 0, tức là thuộc tập hợp 2 1, 2,..., p
1 . Ta sẽ chứng minh tập hợp p 1 p 1 u , p 2
u ,..., p u ; s 1 v , 2 v ,..., t v 1, 2,..., . 2
Thật vậy, rõ ràng không có hai số i
u nào, cũng như không có hai số t
v nào đồng dư với nhau p 1
theo modulo, (nếu trái lại ta sẽ hai số tự nhiên phân biệt m, n thuộc tập 1, 2,..., thỏa mãn 2
ma na(mod p) m ,
n mâu thuẫn) đồng thời các số p i
u cũng không đồng dư với số v j
nào theo modulo. Như vậy ta có p 1 ( p 1
u )( p u2)...( p u ). s 1 v v2....v !(mod p). t 2 Mặt khác, p 1
u , p u2,..., p u ; 1 v , 2 v ,..., s t
v là các thặng dư dương bé nhất của p 1 p 1 p 1
a, 2a, 3a,...,
a theo modulo p, nên 2 1
u , u2,...,u . s 1 v , 2
v ,..., v a . !(mod p). t 2 2 Như vậy ta có 3 p 1 p 1 p 1 s p 1 p 1 2 s 2 2 (1) ! a .
!(mod p) (1) a
1(modp) a
(1)s (modp). 2 2 a a
Áp dụng tiêu chuẩn Euler ta được
(1)s (mod p),
mà chỉ nhận giá trị 1 hay 1, nên p p
a (1)s. Đpcm. p 2 p 1 2
Định lí 5. Nếu p là số nguyên tố lẻ thì 8 (1) . p
Như vậy, là số 2 là một thặng dư bình phương modulo p khi và chỉ khi p 1(mod 8). p
Chứng minh. Áp dụng bổ đề Gauss, ta cần đếm số các thặng dư dương bé nhất lớn hơn của 2 dãy số p 1 1.2, 2.2,..., .2 2
vì các số này bé hơn p nên chúng trùng với các thặng dư dương bé nhất của chúng. Như vậy, ta p
chỉ cần đếm các số của dãy lớn hơn . 2 p 1 p p
Số chẵn 2 j, với 1 j , không vượt quá khi j . 2 2 4 p p 1 p
Vậy số các số trong dãy lớn hơn là s . 2 2 4 Như vậy, ta có p 1 p 2 2 4 (1) . p 2 p 1 p p 1
Bằng cách xét các trường hợp p 1(mod 4), ta được (mod 2). 2 4 8
Khi đó được lí được suy ra từ bổ đề Gauss.
Định lí 6. (Luật thuận nghịch Gauss) Với mỗi cặp các số nguyên tố lẻ khác nhau ( p, q) . Ta có: p 1 q 1 .
p q 2 2 (1) . q p 4
Chứng minh. Trước hết ta chứng minh bổ đề: Giả sử p là số nguyên tố lẻ và a là số nguyên p 1 a 2 ja
không chia hết cho p. Khi đó (1)k , trong đó k . p p j 1
(Ở đây kí hiệu x
là phần nguyên của số thực x ). p 1
Chứng minh bổ đề. Xét các thặng dư dương bé nhất của các số trong dãy a, 2a, 3a,..., a, 2 theo (mod p). p p Gọi 1
u , u2,...,us là các thặng dư lớn hơn và 1
v , v2,..., t
v là các thặng dư bé hơn . 2 2 ja ja
Theo thuật toán chia Euclide ta có ja ja (mod p), với 0 ja p 1. p p ja Nên ja
là số dư trong phép chia ja cho p. Do đó p ( p 1 )/2 ( p 1 )/2 s t ja ja p r s .
i j (1) p j 1 j 1 i 1 j 1
Mặt khác, từ chứng minh định lí 4, ta có p 1 p 1 u , p 2
u ,..., p u ; s 1 v , 2 v ,..., t v 1 , 2,..., . 2 Nên ( p 1 )/2 s t s t j ( p r ) i s
j sp ir s j (2) j 1 i 1 j 1 i 1 j 1
Trừ từng vế các đẳng thức (1) và (2) ta được ( p 1 )/2 ( p 1 )/2 s ja (a 1) j p s 2 r . i (3) p j 1 j 1 i 1 ( p 1 )2 2 p 1 2 ( p 1)/2 p 1 ja Do a, p lẻ và j ,
nên (3) suy ra 0 (a 1) s(mod 2). 8 8 p j 1 j 1 ( p 1 )/2 ja
( p 1)/2 ja Suy ra s (mod 2). Do đó s k (mod 2).
Nên từ định lí 4, ta có bổ đề p p j 1 j 1 được chứng minh. Trở lại bài toán.
Theo bổ đề định lí sẽ được chứng minh nếu ta chứng minh được 5 ( p 1 )/2 (q 1 )/2 jq jp p 1 q 1 . . p q 2 2 j 1 j 1 p 1 q 1
Đặt S (x, y) |1 x ,1 y . 2 2 p 1 q 1 Khi đó tập S có .
phần tử và không có phần tử (x, y) S thỏa mãn qx py, vì p, q là 2 2
hai số nguyên tố phân biệt. Xét các tập 1
S (x, y) S | qx
py , S2 (x, y) S | qx py. Ta có p 1 qx p 1 qx 1
S (x, y) |1 x ,1 y
(x, y) |1 x ,1 y , 2 p 2 p py q 1 py q 1
S2 (x, y) |1 x ,1 y
(x, y) |1 x ,1 y . q 2 q 2 Do đó ( p 1 )/2 (q 1 )/2 qx py 1 S , S 2 . p q x 1 y 1 Vì S 1
S S2 , nên ta có ( p 1 )/2 (q 1 )/2 p 1 q 1 qx py . S 1 S S2 . 2 2 p q x 1 y 1
Từ đó ta có điều phải chứng minh.
Định lí 7. Cho p 2 là một số nguyên tố. Khi đó: i.
2 là thặng dư bình phương mod p nếu và chỉ nếu p 1 (mod 8) . ii.
2 là thặng dư bình phương mod p nếu và chỉ nếu p 1 (mod 8) hoặc p 3 (mod 8) . iii.
3 là thặng dư bình phương mod p nếu và chỉ nếu p 1 (mod12), (với p 3 ) iv.
3 là thặng dư bình phương mod p nếu và chỉ nếu p 1 (mod 6) . v.
5 là thặng dư bình phương mod p nếu và chỉ nếu p 1
(mod 5), (với p 5) Chứng minh. 2 p 1 2 i. Theo định lí 5, ta có 8 (1) .
Do đó 2 là thặng dư bình phương modulo p khi và p 2 p 1 chỉ khi 2 8 (1)
1 p 16k 1 p 1(mod 8). ii.
2 là thặng dư bình phương mod p nếu và chỉ nếu 6 2 p 1 p 1 2 1 2 2 8 1 ( 1 ) .( 1 ) 1 (1) p p p
- Nếu p 8k 1, thì chỉ có p 8k 1 thỏa mãn (1).
- Nếu p 8k 3, thì chỉ thỏa mãn khi p 8k 3 thỏa mãn (1).
Vậy 2 là thặng dư bình phương mod p nếu và chỉ nếu p 1 (mod 8) hoặc p 3 (mod 8) .
iii. Giả sử số nguyên tố lẻ p thỏa mãn (3, p) 1. Gọi s là số các thặng dư dương nhỏ nhất p 1 p
theo modulo p của số 3, 2.3,..., .3 mà lớn hơn
. Khi đó theo bổ đề Gauss ta có 2 2 3 p (1)s.
Khi chia các số của dãy số trên cho p được số dư lớn hơn là các số 3 j p 2 p p thuộc khoảng , p .
Do đó ta cần đánh giá số cách chọn số j thỏa mãn 3 j . p Đặt 2 2 p r r
12k r, với r *
1,5, 7,11 , k . Ta có
3 j p 2k
j 4k . (1) 2 6 3
Tính chẵn lẻ của số các số j thỏa mãn (1) cùng tính chẵn lẻ của số các số j thỏa mãn r r j , (2) 6 3
Với r 1, có 0 số j thỏa mãn (2), suy ra s 0, nên theo bổ đề Gauss 3 là thặng dư bình phương modulo p.
Với r 5 có 1 số j thỏa mãn (2), suy ra s 1, nên theo bổ đề Gauss 3 không là thặng dư
bình phương modulo p.
Với r 7 có 1 số j thỏa mãn (2), suy ra s 1, nên theo bổ đề Gauss 3 không là thặng dư
bình phương modulo p.
Với r 11 có 2 số j thỏa mãn (2), suy ra s 2, nên theo bổ đề Gauss 3 là thặng dư bình phương modulo p.
Vậy 3 là thặng dư bình phương mod p nếu và chỉ nếu p 1 (mod12), (với p 3 )
iv. Theo luật thuận tương hỗ, ta có 3 là thặng dư bình phương mod p nếu và chỉ nếu p 1 p 1 3 1 p 1 . 3 1 3 3 p 2 2 2 2 1 1 (1) (1) .(1) p p p p 3 p p 1 (1) (2) 3
Đặt p 6k r, với r * 1, 5 , k . 7
Với p 6k 1 thì (2) thỏa mãn.
Với p 6k 5 thì (2) không thỏa mãn.
Vậy 3 là thặng dư bình phương mod p nếu và chỉ nếu p 1 (mod 6) .
v. Với p là số nguyên tố lẻ khác 5, theo luật tương hỗ ta có 5 1 p 1 . 5 p 5 p 5 p 2 2 ( 1 ) 1 . p 5 p 5 p 5
Do đó 5 là số chính phương modulo p khi và chỉ khi p là số chính phương mod 5 khi và p chỉ khi (5 1 )/2 2 1 p
(mod 5) 1 p (mod 5) p 5k 1. 5
Phần tiếp theo này chúng ta sẽ khảo sát một vài ứng dụng quen thuộc của thặng dư bình
phương trong bài toán các thi Olympic. Ứng dụng đầu tiên mà chúng ta nghĩ tới chắc chắn là về
các bài toán về đồng dư, chia hết. Dưới đây là tập hợp các bài toán đó.
3. BÀI TẬP ÁP DỤNG
a) Các bài toán chia hết, ước số.
Bài 1. (Polish Olympiad) Cho p 5 là một số nguyên tố. Chứng minh rằng tồn tại x sao cho 2
p | x x 3 khi và chỉ khi tồn tại y sao cho 2
p | y y 25 . Giải. Ta có 2
p | x x 3 tương đương với 2 2
p | 4(x x 3) (2x 1) 11, từ đó ta thấy rằng tồn
tại x khi và chỉ khi 11 là thặng dư bình phương mod p . Tương tự 2
p | y y 25 tương đương với 2 2
p | 4( y y 25) (2 y 1) 99, nên tồn tại y khi và chỉ khi 99 là thặng dư bình phương
mod p . Mặt khác ta thấy: 2 99 11 3 11 p p p p
Bài toán được chứng minh.
Bài 2. Chứng minh rằng tồn tại vô số số nguyên tố dạng: i) 4k 1; ii) 10k 9 .
Giải. i) Xét số 2 A (2 1 p 2 p ... p ) 1. n
Rõ ràng mỗi ước nguyên tố của A phải là số lẻ. Xét một
ước nguyên tố p của A. Suy ra 8 2 1 (2 1 p 2
p ... p ) 1 0(mod p) 1. n p p 1 p 1 Suy ra 2 (1) 1
2 p 1(mod 4) p 4k 1, nhưng nó lại không chia hết cho số 2 nào trong các số 1 p , 2
p ,..., pn . Vô lí.
Tổng quát: Cho a, b là các số nguyên khác không và (a, b) 1. Chứng minh mọi ước nguyên tố của 2 2
a b phải có dạng 4k 1.
Lời giải. Gọi p là một ước tố lẻ của 2 2
a b , suy ra 2 2 2 2 2 b
a b p a b (mod p)
1 (vì (a, b) 1 (a, p) ( . b p) 1 ). (1) p p 1 p 1 p 1 2 b
Mặt khác, theo định lý 2, thì 2 p 1 2 2 2 (b ) (1) .b (1) (mod p) p 2 b
Nếu p = 4k + 3
1 (mod p), mâu thuẫn với (1) p
Vậy p có dạng 4k 1.
ii) Tương tự, xét với số 2 B 5(2 1 p 2 p ... p ) 1 n .
Bài 4. (Bulgaria MO 1998) Cho m, n là các số tự nhiên sao cho: ( 3)n m 1 A 3m
là một số nguyên. Chứng minh rằng A là số lẻ.
Giải. Tất cả các biến xét dưới đây đều nhận giá trị nguyên.
Giả sử ngược lại A là số nguyên chẵn, khi đó ( 3)n m 1 6km (1)
Suy ra m là số nguyên chẵn (xét (1) theo mod 2). Từ (1) suy ra 0 ( 3)n 1 n m
m 1(mod 3) n là số lẻ (vì số chính phương chia cho 3 dư 0
hoặc 1), và m 3t 2. Đặt m 2 . n 1
m , với 1 và 1
m là số lẻ. Khi đó 2 chia hết 3 1, suy ra 2 (vì n lẻ, nên n 1 n 2 3 1 3.9 1 4(mod 8) ).
Nếu 2, thì 4. 1
m m 3t 2 1(mod 3) 1
m 1(mod 3). do vậy tồn tại số nguyên tố p là ước của 1
m sao cho p 1 (mod 3) . (2) 9
Đặt n 2k 1, do n n 2k 1 2k 1 A 0 (m 3) 1 3 1 3 1(mod m) 3 1 0(mod p) k 2 1 3
3(mod p), suy ra 3 là thặng dư bình phương (mod p) p 1(mod 6) , mâu thuẫn với (2). k
Nên 1 . Khi đó m 2 1
m và từ (1) suy ra 2m 32 1 1 1 12k 1 m 2 1 m 4 1 m chẵn. Mâu thuẫn. Vậy m lẻ thì ( 3)n m
1 và 3m lẻ, suy ra A là số lẻ. Đpcm.
Bài 5. (VMO, 2004) Cho p 3 là số nguyên tố và p có dạng p 3n 1. Chứng minh rằng ta p luôn có 2
(i i 1) 0(mod p). i 1
Giải. Trước hết ta chứng minh mệnh đề sau: Với số nguyên tố p 3n 1 thì 3 là số chính
phương mod p. Thật vây, vì p nguyên tố nên n phải chẵn n 2l suy ra p 6l 1. Nếu l 2t, thì
p 12t 1 ( p 1) / 2 6t là số chẵn nên (1) là số chính phương (modp) và 3 là số chính
phương (modp). Do đó ( 3 ) ( 1
).3 là số chính phương (mod p).
Nếu l 2t 1 p 12t 7 ( p 1) / 2 6t 3 là số lẻ nên (1) không là số chính phương
(mod p) và 3 cũng không là số chính phương (mod p) . Do đó (3) (1).3 là số chính phương (mod p).
Vậy luôn tốn tại x , x lẻ để 2 x 3
(mod p) (ta có thể giả sử x lẻ, bởi vì nếu x chẵn thì thay
x bởi x p ). Giả sử 2 2 2
x 2k 1 x 3 4(k k 1) 0(mod p) k k 1 0(mod p). p
Giả sử k i(mod p), với 1 i p ta có 2
i i 1 0(mod p) 2 i i 1 0(mod p). i 1
Nhận xét. Ta có thể chứng minh được
0(mod p), nêu p 3k 1 p 2 i i
1 3(mod p), nêu p 3k 2 i 1
0(mod p), p 3.
Bài 6. (VMO 2004) Với mỗi số nguyên dương n ta kí hiệu S(n) là tổng các chữ số của n trong
biểu diễn thập phân. Xét các số tự nhiên n là bội số của 2003, tìm min S (n) . 10
Giải. Đặt p 2003, thì p là số nguyên tố. Rõ ràng S (n) 1 vì 10k không chia hết cho p. Giả sử
tồn tại n là bội của p và S (n) 2. Suy ra tồn tại k để 10k 1(mod p). Chú ý rằng 2 7 10 7 2
1024 10 (mod p), nên 5k 10k 7 2 2
10 k 10k 1 (mod p).
Vậy 1 là số chính phương (mod p). Mâu thuẫn vì p không có dạng 4k 1.
Do đó S(n) 3. Tiếp theo ta sẽ chứng minh tồn tại n là bội của p sao cho S(n) 3. Ta có 7 10 700 1001 ( p 1 )/2 10 2 2.10 2 2 1
(mod p), vì p 2003 8k 1. Ta chọn 700 n 2.10
1 thì n là bội của p và S (n) 3.
Vậy giá trị nhỏ nhất của S (n) khi n chạy trên các bội của 2003 là 3.
Nhận xét. Tồn tại vô hạn số tự nhiên n là bội của 2003 sao cho S(n) 3. n
Bài 7. Chứng minh rằng với mọi số tự nhiên n 2, ước số nguyên tố của 2 2 1 n F (số Fecma) có dạng n2 .2 m
1, m là số nguyên dương. n n 1
Giải. Gọi p là một ước nguyên tố của . 2 2 n F Suy ra 2 1(mod p) 2 1(mod p). Gọi h n 1 h ord (2) 2 1(mod p) h | 2
h 2k , k , k n 1. p k n n Nếu 2 2 k n 2 1(mod p) 2
1(mod p), mâu thuẫn với 2 2 1 (mod p). Vậy n 1 k 2
. Mặt khác theo định lí Fecma ta có p 1
2 1(mod p), suy ra n 1 n 1 2 | p 1 p .2 m
1, m nguyên dương. 2 p 1 2 Do n 2, suy ra 8
p 8k 1 (1) 1 0 x , ( 0
x , p) 1 sao cho 2 0
x 2(mod p) p p 1 p 1 n 1 p 1 p 1 n 1 n2 2 2 x 1(mod p) 2 | . m 2 p . m 2 1. 0 2 2 n Bài 8. Cho 2 k 2
1 với n là số nguyên dương, giả sử k là số nguyên tố. Chứng minh rằng k là k 1 ước của 2 3 1. n Giải. Vì 2 k 2
1 là số nguyên tố, nên theo luật luật tương hỗ Gauss, ta có 3 1 k 1 n n 1 2 2 . 3 k 3 k 2 1 4 1 2 2 2 ( 1) 1 1 . k 3 k 3 3 3 3
Do đó theo bổ đề Gaus, ta có 11 k 1 k 1 k 1 k 1 3 2 2 2 2 3 (mod k) 1 3 (mod k) 3 1 0(mod k) 3 1k. Đpcm. k Bài 9. Cho đa thức 8
f (x) x 16. Chứng minh rằng với mọi số nguyên tố p , đều tìm được số
nguyên dương n sao cho f (n) . p Giải. Ta có 4 4 2 2 2 2
f (x) (x 4)(x 4) (x 2)(x 2)(x 2x 2)(x 2x 2). Suy ra 2 2 2 2
f (x) (x 2)(x 2)[(x -1) 1][(x 1) 1].
- Nếu 2 là số chính phương modulo p thì tồn tại *
n sao cho p(n) 0(mod p).
- Nếu 2 là số chính phương modulo p thì tồn tại *
n sao cho p(n) 0(mod p).
- Nếu 1 là số chính phương modulo p thì tồn tại *
n sao cho p(n) 0(mod p). - Nếu 2, 2 , 1
đều không là số chính phương modulo p thì p 1 p 1 p 1 2 2 2 2 1(mod p), (2) 1(mod p), ( 1 ) 1 (mod p). p 1 p 1 p 1 Nhưng ta lại có 2 2 2 2 (2) (1) ( 1
)(1) 1(mod p), suy ra mâu thuẫn.
Vậy bài toán được chứng minh.
Nhận xét. - Từ bài toán trên ta xây dựng được bài toán sau (với cách giải tương tự): Cho đa thức 2 2 2
f (x) (x a)(x b)(x ab), trong đó a, b là hai số nguyên tố phân biệt. Chứng minh rằng
với mọi số nguyên tố p đều tìm được số nguyên dương n sao cho f (n) . p
- Đa thức dạng trên “rất hữu ích” trong ứng dụng vào việc tìm ước số nguyên tố của số nguyên
(bằng thuật toán Rho-phương pháp)
Bài 10. (IMO Shortlist, 1998) Xác định tất cả các số nguyên dương n sao cho với n này tồn tại số
nguyên m thỏa mãn n 2 2 1| m 9.
Giải. Ta viết 2 . s n
t; s, t , t là số lẻ.
Nếu t 3, thì t n t 2
2 1| 2 1 2 1| m 9. Ta có 2t 1 1(mod 4), tức là 2t 1 có dạng
4k 3, do đó nó có ước nguyên tố p mà p 1(mod 4). Hiển nhiên p 3, vì 3 | 2t 1, t lẻ. Từ đó suy ra 2 2
p | m 9 m 9(mod p). Vậy 9 là thặng dư bậc hai theo modulo p, suy ra 2 p 1 p 1 9 1 3 2 1 (1) .1 1 2 . p p p p 1 Suy ra
là số chẵn, tức là p 1(mod 4). Mâu thuẫn. 2
Từ đây ta suy ra t 1 hay 2 . s n Ta sẽ chứng minh rằng 2s n
, (với s ) là tất cả các giá trị
của n cần tìm. Thật vậy, ta sẽ chỉ ra số nguyên m thỏa mãn n 2 2 1| m 9. 12 s s 1 Ta có n 2 2 2 2 1 2
1 (2 1)(2 1)(2 1)...(2 1). k Từ đó để n 2
2 1| m 9, ta cần có 2 2 2
1| m 9, k 0,1,..., s 1. m k
Mặt khác dễ chứng minh được các số Fecma có tính chất: 2 2 2 1, 2
1 1, m k.
Do đó theo định lí thặng dư Trung Hoa thì tồn tại số nguyên 0
x thỏa mãn hệ đồng dư 0 0 2 2 2 x 0(mod 2 1) 0 x 0 9(mod 2 1) 0 1 2 2 2 2 2 x 0 x 9.2 9 (mod 2 1) 3.2 (mod 2 1) 2 2 2 2 1 2 2 2 2
x 3.2 (mod 2 1) 0 x 9.2 9(mod 2 1) 2 3 3 3 2 2 2 2 2 x 3.2 (mod 2 1) 0 x 9.2 9(mod 2 1) . ........ . ........ s2 s 1 s 1 s 1 2 2 2 2 2 x 3.2 (mod 2 1). 0 x 9.2 9 (mod 2 1). i Từ đó suy ra 2 2 0 x 9 0(mod 2
1), i 0,1,..., s 1. Từ đây suy ra n 2 n 2 n 2 2 1| 3( 0 x 1) 2 1| 0
x 9 2 1| m 9, với m 0
x đây chính là giá trị m cầm tìm.
Vậy tất cả giá trị của số tư nhiên n cần tím là 2s n , với s .
Bài 11. (APMO, 1997) Tìm một số n nằm giữa 100 và 1997 sao cho | 2n n 2 .
Giải. Hiển nhiên n thỏa mãn điều kiện thì n là số chẵn. Không thể xảy ra n 2 p , với p là số
nguyên tố (từ Định lí Fermat). Bây giờ chúng ta tìm n 2 pq , với p, q là các số nguyên tố khác nhau. Chúng ta cần 2 pq 1 2 2 pq | 2 1 1
. Theo Định lí Fermat ta lại có p q 2q 1 2 p 1 p | 2 1, q | 2
1, dễ thấy q 3,5, 7 không thoã mãn, ta thử chọn q 11 xem sao. Trong
trường hợp này chúng ta tìm thấy p 43 . Chúng ta còn lại chỉ cần chứng minh với 2 2
p 43, q 11 . Thật vậy, chỉ cần chứng minh rằng 1 q p và 2 1 2 1 p | 2 1, q | 2 1. p q
Điều này là rất dễ dàng kiểm tra.
Vậy chúng ta chọn n 2.11.43 .
Bài 12. (IMO Longlist, 1992, ROM 2) Cho a, b là các số nguyên. Chứng minh rằng 2 2a 1 , 2 b 2
không phải là một số nguyên.
Giải. Ta xét hai trường hợp:
Trường hợp 1: b chẵn thì 2
2a 1 chia hết cho 2, vô lí. 13
Trường hợp 2: b lẻ thì 2
b 2 3(mod 8) , do đó 2
b 2 có ước số nguyên tố lẻ dạng 8k 3 ,
gọi một trong số đó là p , thì do 2
2a 1chia hết cho p nên (a, p) = 1 do đó tồn tại 1 a sao cho a 1
a 1(mod p) , khi đó ta có: 2
2a 1 0(mod p) 2 2a 1(mod p) 2 2 a 1(mod p)
Do đó 2 là thặng dư bình phương theo mod p , với p là số nguyên tố dạng 8k 3 vô lí. Kết luận được chứng minh.
b) Các bài toán về sự tồn tại và biểu diễn số nguyên
Sau đây chúng ta sẽ thấy vai trò của thặng dư bình phương về chứng minh tồn tại hay không
tồn tại trong các bài toán số học thi Olympic cũng như sự tồn tại biểu diễn của một số nguyên theo dạng nào đó.
Bài 13. Chứng minh rằng với mỗi số nguyên tố p , thì tồn tại các số nguyên a, b sao cho 2 2
a b 1 là bội số của p .
Giải. Ta thấy p | 2 2
a b 1 khi và chỉ khi 2 2
a b 1(mod p) .
Nếu p 2 thì chỉ cần chọn a chẵn b lẻ ta có điều phải chứng minh.
Xét trường hợp p lẻ. Xét hai tập hợp 2 p 1 2 p 1
A {r | r i (mod p), i 1,
}, B {s | s j 1(mod p), j 1, }, i i j j 2 2
trong đó các số ir đôi một không đồng dư với nhau theo mod p , cũng như các số s j đôi một
không đồng dư với nhau theo mod p và r , s 1, 2,..., p 1 . i j
Ta có A B p 1, A B p 1.
Nếu A B p 1, thì A B nên tồn tại 2 2 2 2
r s i 1
j (mod p) i j 1 0(mod p). i j
Nếu A B p 1, thì A B nên các số r ,
i s j đôi một phân biệt, suy ra 1 r 2
r ... r 1 1
s s2 ... s 1 1 2 ... p 1 0(mod p) p p (1) 2 2 Ta lại có 14 2 2 2 p 1 1 r 2
r ... rp 1 1
s s2 ... s p 1 1 2 ... 2 2 2 (2) 2 2 2 p 1 p 1
(1 1) (2 1) ... 1 (mod p) 2 2
Từ (1) và (2) suy ra mâu thuẫn.
Vậy các số nguyên a, b sao cho 2 2
a b 1 là bội số của p . n n
Bài 14. Chứng minh rằng có vô số hợp số dạng 2 2 1 hoặc 2 6 1 ( hoặc cả hai) x x
Giải. Giả sử tồn tại số nguyên dương N sao cho với mọi x N thì cả hai số 2 2 1 và 2 6 1
đều là số nguyên tố. Ta thấy, với m n N 2m 2m 2n 6 1 3 1(mod 2 1) n
Nếu 3 không phải là thặng dư bình phương 2 mod 2 1 , thì với 1 2n m thì 2m 2m 2n 6 1 3 1 0(mod 2 1) . Vô lí. n
Vậy 3 là thặng dư bình phương 2 mod 2 1, 3 1 2n 2 1 Mà 2n n 2 1 1 3 1 2 n . 3 2 1 2 2 1 2 2 ( 1 ) 1 và 1 . Vô lí. 2n 3 2 1 3
Bài 15. (Việt Nam TST 2004) Chứng minh rằng số 2n 1 không có ước số nguyên tố nào có dạng 8k 1.
Giải. Giả sử 2n 1 có ước số nguyên tố p dạng 8k 1 .
Nếu n là số chẵn thì n/2 2 1 (2
) (mod p), do đó 1 là số chính phương modulo p. p 1 1 Suy ra 2 1 (1) 1. Vô lí. p
Tương tự nếu là n số lẻ thì (n 1 )/2 2 2 (2
) (mod p), do đó 2 là số chính phương modulo p. (1) 15 p 1 2 p 1 2 1 2 Ta lại có 2 (1) . 1 8
1 , mâu thẫn với (1) p p p
Bài toán được chứng minh.
Bài 16. (Tạp chí Pi số tháng 8, năm 2017) Chứng minh rằng không tồn tại số nguyên n 5, sao cho 3n 5n chia hết cho 2 n 25.
Giải. Giả sử ngược lại, tồn tại số nguyên n 5, sao cho 3n 5n chia hết cho 2 n 25.
Nếu n chẵn, tức là n 2k, thì từ n 5, suy ra 2
n 25 1. Do đó 2
n 25 có ước nguyên tố 2 2 3k p
p 3(mod 4). Hơn nữa 3n 5n 3k 5k p p 1. Vô lí. 5k p
Vậy n lẻ. Bây giờ ta xét p là một ước nguyên tố bất kì của 2
n 25, thì ta có 3n 5n . p Do đó
3n 5n ,
p p suy ra
3n 5n 3 . n ( 5n ) 15 1 . 1, vì n lẻ.
p p p p
Suy ra theo luật tương hỗ Gauss, ta có 15 1 3 5
p p 1 . . . . p p p p 3 5
Suy ra p đồng dư với 1, 2, 4, hoặc 8 theo (mod15). Như vậy mọi ước nguyên tố của 2 n 25
đều có dạng 15k r, với r 1, 2, 4,
8 . Do đó mọi ước nguyên tố của n 5 và n 5 phải thuộc
dạng vừa nêu. Mà tích của hai số dạng 15k r, với r 1, 2, 4,
8 là số coa dạng như vậy, nên suy
ra n 5 và n 5 đồng dư với 1, 2, 4,8 theo (mod15). Tuy nhiên điều nàu không thể vì hiệu của
hai số tùy ý thuộc tập 1, 2, 4,
8 không chia hết cho 5. Mâu thuẫn nhận được, từ đó suy ra bài toán được chứng minh.
Bài 17. (Indonesia TST, 2009) Chứng minh rằng tồn tại vô hạn số nguyên dương n sao cho 2
n 1 không là ước của n!.
Giải. Ta có bổ đề quên thuộc sau: Tồn tại vô hạn số nguyên tố dạng 4k 1, với k là số nguyên
dương. (Bổ đề đã được chứng minh trong bài 2).
Trở lại bài toán. Ta xét p là một số nguyên tó có dạng p 4k 1. 16 1
Theo tiêu chuẩn Euler, ta có ( p 1 )/2 (1) 1. p
Hay 1 là số chính phương (mod p).
Từ đó tồn tại m 1, 2,..., p 1 sao cho 2
m 1 0(mod p).
Ví m p, nên m! không chia hết cho p nên 2
m 1 không là ước của m!.
Theo bổ đề tồn tại vô hạn số nguyên tố p 4k 1, nên tồn tại vô hạn số nguyên dương n sao cho 2
n 1 không là ước của n!.
Bình luận. Bài toán trên có lẻ xuất phát ý tưởng của từ bài 3 trong kỳ thi Olympic Toán Quốc tế
lần 49 năm 2008 (tác giả là Kestuis Cesnavicius, người Litva), đây là bài toán khó nhất của ngày
thi thứ nhất. Từ bài toán này những năm sau nhiều nước dựa trên ý tưởng đó để phát triển thành
đề thi Olympic, đề chọn đội tuyển của nước mình.
Bài 18. (IMO Shortlist, 2008) Chứng minh rằng tồn tại vô số số nguyên dương n sao cho 2 n 1
có ước nguyên tố lớn hơn 2n 10n.
Giải. Xét số nguyên tố p dạng *
p 8k 1, k . Theo tiêu chuẩn Euler, ta có p 1 1 4k 1 1 2 (1) (1) 1(mod p) 1, vì 1, 1 . p p p
Nghĩa là 1 là số chính phương modulo p, nên phương trình 2 x 1
(mod p), có hai nghiêm
thuộc 1, 2,..., p
1 và hai nghiệm đó có tổng bằng p (vì 2 2 ( p ) m
m (mod p) ). p 1
Gọi n là nghiệm nhỏ hơn trong hai nghiệm đó, ra tồn tại n 1, 2,..., sao cho 2 2
n 1 0(mod p). p 1
Chúng ta sẽ chứng minh rằng p 2n 10n. Thật vậy, đặt n
l, với l 0. Thì 2 2 p 1 2 l
1 0(mod p) (2l 1) 4 0(mod p). 2 Do đó 2 *
(2l 1) 4 rp, r . (1) Ta có 2
(2l 1) 1 p(mod 8), nên từ (1) suy ra r 5(mod 8) r 5. p u 1 Do đó 2 5 4 1
(2l 1) 4 5 p l
. Đặt u 5 p 4, thì ta được l . Do đó 2 2 p 1 p u 2 u 4 n l
. Kết hợp với p
, ta được bất phương trình 2 2 5 17 2 5 40n 9 p u
u 5u 10n 4 0, mà u 0, nên suy ra u
, kết hợp với n , 2 2 suy ra 5 40n 9
p 2n u 2n
p 2n 10n. 2
Vì có vô hạn số nguyên tố dạng 8k 1, nên có vô hạn số nguyên dương n thỏa mãn bài toán.
Bài 19. (Turkey TST 2006) Với mỗi số nguyên dương n chúng ta xác định dãy ( ) n x như sau 2 2 2 x 1 1 x 2
x ... x , n n với 1
x là một số nguyên dương. Tìm 1
x nhỏ nhất sao cho 2006 | 2 x 006.
Giải. Chúng ta thấy rằng 2
x 1 x x , n 1 n n n , do đó n
x là số chẵn với mọi n 2. Lại chú ý 2
x 0(mod1003) x 1 x 1 0(mod1003) n n n 1 0(mod1003) n x hoặc 1 1(mod1003) n x
Bây giờ ta sẽ chứng minh đồng dư 1(mod1003) n x
không thể xảy ra với mọi n 2 , giả sử tồn tại n 2 sao cho 1(mod1003) n x thì 2 n x 1 n x 1 1(mod1003) 2
(2xn 1 1) 3(mod1003).
Vậy 3 là thặng dư bình phương mod 1003 . Mâu thuẫn với Định lí 8. Do đó 2 x 0(mod1003) 1
x 0(mod1003) hoặc 1 x 1 (mod1003).
Vậy giá trị nhỏ nhất của 1 x là 1002.
Bài 20. (KHTN Hà Nội, 2018) Cho dãy số nguyen dương (a ) n thỏa mãn 3 a 1 a 4 n n n a với
mọi n 1. Tìm giá trị nhỏ nhất của 1 a để 2
a 018 2018 chia hết cho 57.
Giải. Vì 57 3.19, nên để a2018 2018 chia hết cho 57 thì hai điều kiện sau đông thời thỏa mãn: a) 2 a 018 2(mod 3).
b) a2018 4(mod19).
Trước hết, xét theo modulo 3 cho toàn bộ các số hạng của dãy ( ), n a ta được.
a 1 a a a (mod 3). n n n n Như vậy 2 a 1 a , 3 a 1 a ,..., 2 a 018 1
a (mod 3) . Do đó điều kiện
a) tương đương với 1 a 1(mod 3) 1 a 2(mod 3). 18 Mặt khác ta lại có 3 a a a a 2 1 4 4 4 4
(a 4) 7(a 4) 5 (mod19). n n n n n n Ta sẽ chứng minh rằng 2
x 7x 5 không chia hết cho 19 với mọi số nguyên . x Thật vậy, xét phương trình đồng dư: 2 2 2
x 7 x 5 0(mod19) 4x 28x 20 0(mod19) (2 x 7) 12(mod19). 12 4 3 3 19 1
Phương trình này vô nghiệm, vì . 1. 19 19 19 19 3 3 Như vậy 2
(a 4) 7(a 4) 5 0(mod19), n n do đó a 1 4 0(mod19) a 4 0(mod19). n n
Suy ra điều kiện b) tương đương với 1
a 4(mod19). Tóm lại để a2018 2018 chia hết cho 57 , thì 1
a phải thỏa mãn hệ điều kiện: 1 a 2(mod 3) 1 a 53(mod 57). Vì 1 a 0, nên 1
a 53 là số nhỏ nhất cần tìm. 1 a 4 (mod19)
Chúng ta bây giờ sẽ khảo sát tiếp một vài ứng dụng của thặng dư chính phương trong việc giải
các phương trình Diophant, đây là ứng dụng mang tính kĩ thuật của công cụ này. Một số bài toán
được giới thiệu sau là những bài toán hay và khó, được giải quyết mang tính sắc bén và sức
mạnh của khái niệm thặng dư bình phương.
c) Các bài toán về phương trình nghiệm nguyên
Bài 21. (Putnam, 1954) Chứng minh rằng không có số nguyên x, y nào sao cho 2 2
x 3xy 2 y 122.
Giải. Giả sử tồn tại các số nguyên x, y sao cho 2 2
x 3xy 2 y 122 , khi đó ta có: 2 2
(2x 3y) 17 y 488
Vì 488 12(mod17) , Suy ra 12 là thặng dư bình phương mod17 , lại có 12 3 4 3 17 2 1 . Vô lí. 17 17 17 17 3 3
Bài 22. Chứng minh rằng phương trình 2 3
x 5 y không có nghiệm nguyên.
Giải. Giả sử phương trình 2 3
x 5 y có nghiệm nguyên (x, y). Nếu y chẵn thì 2 2
x 5 0(mod 8) x 3(mod 8), điều này vô lí theo định lí 7. Do đó y phải lẻ. Ta có 2 3 2 3 2
x 5 y x 3 y 8 ( y 2)( y 2 y 4). Từ y lẻ, nên 2
y 2 y 4 lẻ, gọi p là một ước nguyên tố lẻ của 2
y 2 y 4, có dạng p 3(mod 4) (1) 19
Tài liệu liên quan:
-
Phương trình đường thẳng trong mặt phẳng - Lý thuyết và bài tập môn Toán 10 - Kết nối tri thức
21 11 -
Tổng hợp bài tập: Các bài toán bất đẳng thức môn Toán 10
26 13 -
Lý thuyết và bài tập thực hành Chuyên đề 1: Đại số tổ hợp môn Toán 10
35 18 -
Chuyên đề IV: Hệ thức lượng trong tam giác Vecto môn Toán 10
43 22