Mục đích nghiên cứu
Kí hiệu toán học giống như các chương trình con trong thuật toán, giúp diễn đạt vấn đề một cách ngắn gọn và dễ hiểu hơn Lịch sử phát triển của toán học đã chứng minh điều này Kí hiệu Legendre, liên quan đến khái niệm đồng dư thức trong số học, giúp trình bày các vấn đề về quan hệ đồng dư một cách mạch lạc và dễ tiếp cận hơn.
Rèn luyện kỹ năng áp dụng khái niệm thặng dư bình phương theo modulo n là rất quan trọng trong việc giải toán, đặc biệt qua các bài thi học sinh giỏi và các kỳ thi Olympic Việc thực hành thường xuyên sẽ giúp học sinh nắm vững kiến thức và cải thiện khả năng giải quyết vấn đề một cách hiệu quả.
Phương pháp nghiên cứu…
Tham khảo tài liệu trong và ngoài nước về số học giúp biên soạn cơ sở lý thuyết thặng dư bình phương và phân loại một số dạng đề thi Olympic toán liên quan Việc học chuyên sâu theo chuyên đề sẽ phát triển năng lực tư duy toán học của học sinh, đồng thời trang bị cho các em phương pháp giải quyết hiệu quả các bài toán số học có liên quan đến quan hệ đồng dư, một phần thường gặp khó khăn đối với học sinh các lớp chuyên toán.
Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm
Nhiều bài toán số học liên quan đến đồng dư thức x² ≡ a (mod n) yêu cầu học sinh áp dụng kiến thức nâng cao và đổi mới cách tiếp cận để tìm ra lời giải, đặc biệt là trong các bài toán dành cho học sinh giỏi.
Học sinh thường gặp khó khăn do thiếu cơ sở lý thuyết vững chắc Bài viết này nhằm cung cấp cho các em kiến thức lý thuyết cần thiết và hệ thống bài tập để áp dụng hiệu quả phương pháp học.
2 NỘI DUNG SÁNG KIẾN KINH NGHIỆM
2.1 Cơ sở lí luận của sáng kiến kinh nghiệm
Thặng dư bình phương của một số theo modulo n được định nghĩa khi n là một số nguyên dương lớn hơn 1 Cụ thể, một số nguyên dương a được gọi là thặng dư bình phương modulo n nếu nó là nguyên tố cùng nhau với n và thỏa mãn phương trình cụ thể.
2 (mod ) x ≡a 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.
Trong trường hợp modulo p, với p là một số nguyên tố lẻ, định nghĩa Legendre được sử dụng để ký hiệu mối quan hệ giữa số nguyên a và p Nếu a là một số nguyên nguyên tố cùng nhau với p, thì ký hiệu Legendre được biểu diễn là a p.
÷ nếu a là một thặng dư bình phương modunlo p a 1 p
÷ nếu a là bất thặng dư bình phương modunlo p.
Chú ý: Trong tài liệu còn định nghĩa cho trường hợp a pM là a 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 x² ≡ a (mod p) có thể không có nghiệm hoặc chỉ có đúng 2 nghiệm đồng dư theo modulo p Trong tập hợp các số từ 1 đến p−1, số lượng số có thặng dư bình phương và số không có thặng dư bình phương theo modulo p đều là 1.
Giả sử a là một thặng dư bình phương modulo p Nếu b thuộc tập {1, 2, , p − 1}, thì b² ≡ (p - b)² (mod p) Do đó, phương trình x² ≡ a (mod p) có đúng 2 nghiệm với 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} và S₁ = {1, 2, , (p − 1)/2} Với mỗi i thuộc S₁, gọi rᵢ là số dương nhỏ nhất.
2 i (mod ). i ≡r p Ta thấy rằng r i ≠r j nếu i≠ j Thật vây, nếu
2 2 0(mod ) ( )( ) 0(mod ). i j r = ⇒ −r i j ≡ p ⇒ −i j i+ ≡j p 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≤ − < + 2, chúng ta
Như vây, phương trình đồng dư x 2 ≡ −1(mod )p có nghiệm khi và chỉ khi p=2 hoặc
Phương trình đồng dư x^2 ≡ −1 (mod p) không có nghiệm nếu và chỉ nếu p ≡ −1 (mod 4) Theo định lý 3 về ký hiệu Lagrange có tính chất nhân, với p là số nguyên tố lẻ và a, b là các số nguyên, thì nếu a b ≡ (mod p) thì a b p p.
Chứng minh i) Nếu a b≡ (mod ),p thì phương trình x 2 ≡a(mod )p có nghiệm khi và chỉ khi phương trình x 2 ≡b(mod )p có nghiệm Vậy a b p p
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.
Theo tiêu chuẩn Euler, ta có
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
Tích của hai thặng dư bình phương hoặc hai thặng dư bất bình phương sẽ tạo thành một thặng dư bình phương, trong khi 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 sẽ là một thặng dư bất bình phương Theo Định lý 4 (Bổ đề Gauss), nếu p là số nguyên tố lẻ và a là số nguyên dương không chia hết cho p, thì trong các số thặng dư dương bé nhất của các số nguyên, có những tính chất quan trọng liên quan đến thặng dư.
2 a a a p− a có s thặng dư lớn hơn
Chứng minh Trong số các thặng dư dương bé nhất của các số nguyên 1
2 a a a p− a giả sử u u 1 2 , , ,u s là các thặng dư lớn hơn
2 p và v v 1 2 , , ,v t là các thặng dư bé hơn
≤ ≤ nên mọi ,u v i j đều khác 0, tức là thuộc tập hợp
{ 1, 2, , p − 1 } Ta sẽ chứng minh tập hợp
Không tồn tại hai số u i hay hai số v t nào đồng dư với nhau theo modulo Nếu điều này không đúng, sẽ dẫn đến sự tồn tại của hai số tự nhiên phân biệt m và n thuộc tập 1.
(mod ) , ma na≡ p ⇒ =m n mâu thuẫn) đồng thời các số p u− i cũng không đồng dư với số v j nào theo modulo Như vậy ta có
Mặt khác, p u p u− 1 , − 2 , ,p u v v− s ; , , , 1 2 v t là các thặng dư dương bé nhất của
− ÷ ≡ ÷ ⇒ − ≡ ⇒ ≡ − Áp dụng tiêu chuẩn Euler ta được a ( 1) (mod ), s p p
chỉ nhận giá trị 1 hay 1− , nên
÷ Đpcm. Định lí 5 Nếu p là số nguyên tố lẻ thì
÷ Như vậy, là số 2 là một thặng dư bình phương modulo p khi và chỉ khi p≡ ±1(mod8).
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ác số p− nhỏ hơn p sẽ trùng với các thặng dư dương nhỏ nhất của chúng Do đó, chúng ta chỉ cần đếm số lượng các số trong dãy lớn hơn p.
Vậy số các số trong dãy lớn hơn
÷ Bằng cách xét các trường hợp p≡ ±1(mod 4), ta được 1 2 1
2 4 8 p− − p ≡ p − 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ó:
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 không chia hết cho p Khi đó a ( 1) , k p
= ∑ (Ở đây kí hiệu x là phần nguyên của só thực x).
Chứng minh bổ đề Xét các thặng dư dương bé nhất của các số trong dãy 1
Gọi u u 1 2 , , ,u s là các thặng dư lớn hơn
2 p và v v 1 2 , , ,v t là các thặng dư bé hơn
Theo thuật toán chia Euclide ta có ja (mod ), ja ja p p
− là số dư trong phép chia ja cho p Do đó
Mặt khác, từ chứng minh định lí 4, ta có
Trừ từng vế các đẳng thức (1) và (2) ta được
≡ ∑ = Nên từ định lí 4, ta có bổ đề được chứng minh.
Theo bổ đề định lí sẽ được chứng minh nếu ta chứng minh được
2 2 p− q− phần tử và không có phần tử ( , )x y ⊂S thỏa mãn qx= py, vì p, q là hai số nguyên tố phân biệt.
Xét các tập S 1={( , )x y ∈S qx| > py S }, 2 ={( , )x y ∈S qx| < py } Ta có
Từ đó ta có điều phải chứng minh. Định lí 7 Cho p>2 là một số nguyên tố Khi đó
2 là thặng dư bình phương modp nếu và chỉ nếup≡ ±1 (mod8).
−2 là thặng dư bình phương mod p nếu và chỉ nếup≡1 (mod8) hoặc p≡3 (mod8).
3 là thặng dư bình phương modp nếu và chỉ nếu p≡ ±1 (mod12), (với p≠3)
−3 là thặng dư bình phương mod p nếu và chỉ nếu p≡1 (mod 6).
5 là thặng dư bình phương modp nếu và chỉ nếup≡ ±1 (mod 5), (với p≠5)
7 là thặng dư bình phương modp nếu và chỉ nếup≡ ± ± ±1, 3, 9 (mod 28), (với p≠7) vi)
Chứng minh Theo định lí 5, ta có
Do đó 2 là thặng dư bình phương modulo2 khi và chỉ khi 2 8 1 2
−2 là thặng dư bình phương modp nếu và chỉ nếu
- 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).
Số 2− được coi là thặng dư bình phương modulo p nếu và chỉ nếu p thỏa mãn điều kiện p≡1 (mod 8) hoặc p≡3 (mod 8) Giả sử p là một số nguyên tố lẻ thỏa mãn (3, 1) Gọi s là số các thặng dư dương nhỏ nhất theo modulo p của số 1.
2 p Khi đó theo bổ dề Gauss ta có
÷ Khi chia các số của dãy số trên cho p được số dư lớn hơn
2 p là các số 3j thuộc khoảng ,
Do đó ta cần đánh giá số cách chọn số j thỏa mãn 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
Với r=1, có 0 số j thỏa mãn (2), suy ra s=0, nên theo bổ đề Gaus 3 là thặng dư bình phương modulo p
Với Với r=5 có 1 số j thỏa mãn (2), suy ra s=1, nên theo bổ đề Gaus 3 không là thặng dư bình phương modulo p
Với Với r=7 có 1 số j thỏa mãn (2), suy ra s=1, nên theo bổ đề Gaus 3 không là thặng dư bình phương modulo p
Với Với r có 2 số j thỏa mãn (2), suy ra s=2, nên theo bổ đề Gaus 3 là thặng dư bình phương modulo p
Ba là thặng dư bình phương modulo p khi và chỉ khi p ≡ ±1 (mod 12), với điều kiện p khác 3 Theo luật thuận tương hỗ, -3 cũng là thặng dư bình phương modulo p khi và chỉ khi điều kiện tương tự được thỏa mãn.
Với p=6k+5 thì (1) 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ó
Do đó 5 là số chính phương modulo p khi và chỉ khi p là số chính phương modulo5, khi và chỉ khi 1 (5 1)/2 (mod 5) 1 2 (mod 5) 5 1.
Theo luật tương hỗ, ta có 7 là số chính phương (mod )p khi và chỉ khi p là số chính phương
1(mod 4), 4(mod 7) 25 3(mod 28) p≡ o p≡ ⇔ ≡p ≡ − vii) Nếu p≡ −1(mod 4).
Theo luật tương hỗ, ta có 7 là số chính phương (mod )p khi và chỉ khi p không là số chính phương (mod 7) 1 (7 1)/2 3 (mod ) 3,5,6(mod 7).
Tóm lại 7 là số chính phương (mod )p khi và chỉ khi p≡ ± ± ±1, 3, 9(mod 28). viii) Ta có 1 2 1
Một số chính phương sẽ luôn là số chính phương (mod) p với mọi số nguyên tố p Ngược lại, một số không chính phương có thể trở thành số chính phương theo một (mod) p nào đó Ví dụ, số 6 được coi là số chính phương (mod 19) vì 5^2 ≡ 6 (mod 19).
Có tồn tại số không chính phương nhưng lại là số chính phương (mod) p với mọi số nguyên tố p hay không? Định lý 8 chứng minh rằng không tồn tại số như vậy Cụ thể, nếu a là số không chính phương, thì sẽ luôn tồn tại một số nguyên tố lẻ p sao cho a không phải là số chính phương (mod) p.
Chứng minh Giả sử a b c= 2 ,ở đó c q q= 1 2 q m với q 1 <
Giải Giả sử gcd( , ) 1m n = Viết 5 m − =1 2 α p 1 α 1 p k α k (1) là phân tích ra thừa số nguyên tố của 5 m −1, ở đây p i >2với i=1, 2, ,k Từ điều kiện bài ra
Suy ra 2 α − 1 p 1 α 1 − 1 p k α k − 1 | 5 n −1, mà gcd(5 m −1,5 n − =1) 5 gcd( , ) m n − =1 4 nên α = i 1 với mỗi
1, 2, , i= k, và α =2 Do 2 | 5 3 x −1 với mỗi x chẵn, nên m là số lẻ, m=2 ' 1m+ Do
| 5.(5 ) m ' 2 1 p i − với mỗi i=1, 2, ,k, nên 5 là thặng dư bình phương modulop i , suy ra 1(mod 5) p i ≡ ± Ngoài ra, từ (2) suy ra không tồn tại p i sao cho p i ≡1(mod 5), vậy
Trong bài toán này, ta có biểu thức (1) với điều kiện (mod 5) p i ≡ − với mọi i = 1, 2, , k Khi lấy hai vế của (1) theo mod 5, ta suy ra (1) − k ≡ 1 (mod 5), từ đó kết luận rằng k là số chẵn Tiếp theo, xét (2) theo mod 5, ta có (2) − k + 1 ≡ 1 (mod 5), dẫn đến k ≡ 3 (mod 4), tạo ra mâu thuẫn với kết quả chứng minh trước đó.
Bài 4 (Bulgaria MO 1998) Cho m, n là các số tự nhiên sao cho:
+ + 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 đó
(m+3) n + =1 6km (1). Suy ra m là số nguyên chẵn ( xét (1) theo mod 2).
Từ mối quan hệ giữa n và m, ta có m + 3n ≡ 1 (mod 3), dẫn đến n là số lẻ vì số chính phương chỉ có thể chia cho 3 với số dư 0 hoặc 1 Do đó, m được xác định là 3t + 2 Khi đặt m = 2αm1, với α ≥ 1 và m1 là số lẻ, ta suy ra rằng 2α phải chia hết cho 3n + 1, từ đó kết luận rằng α ≤ 2 do n là số lẻ.
Nếu α =2,thì 4.m 1 = = + ≡ −m 3t 2 1(mod 3)⇒m 1 ≡ −1(mod 3) do vậy tồn tại số nguyên tố p là ước của m 1 sao cho p≡ −1(mod 3) (2) Đặt n=2k+1,do A∈ ⇒ ≡¢ 0 (m+3) n + ≡1 3 n + ≡1 3 2 1 k + +1(mod )m ⇒3 2 1 k + + ≡1 0(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).
Nên α =1 Khi đó m=2m 1 và từ (1) suy ra (2m 1+3) 2 1 k + + =1 12km 1⇒2m 1M4⇒m 1 chẵn. Mâu thuẫn.
Vậy m lẻ thì (m+3) n +1 và 3m lẻ, suy ra A là số lẻ Đpcm.
Bài 5 (AMM, Romania TST 2008) Với các số nguyên dương lẻ ,m n lớn hơn 1, thì 2 m −1 không chia hết 3 n −1.
Giải Giả sử ngược lại, tồn tại các số tự nhiên lẻ ,m n lớn hơn 1, sao cho
Suy ra 3 là thặng dư bình phương modM
(ở đây ta sử dụng kí hiệu Jacobi).
Do đó theo luật thuận nghịch Gauss ta có
(doM ≡2(mod 4) ) Điều này là mâu thuẫn Vậy giả sử là sai, bài toán được chứng minh
Nhận xét Từ Bài Toán 5, ta có kết quả tổng quát sau cho Bài Toán 5:
Bài toán tổng tuát: Chứng minh rằng nếu m>1 và n>0 có cùng tính chẵn lẻ, thì 2 m −1 không chia hết 3 n −1.
Giải: Nếu ,m n cùng lẻ, thì ta có Bài Toán 5, mà chúng ta vừa mới giải quyết.
Nếu ,m n cùng chẵn, thì 2 m −1chia hết cho 3, trong khi đó 3 n −1không chia hết cho 3, do đó bài toán được chứng minh
Bài 6 (Shortlist 2011) Cho ( ), ( )P x Q x là hai đa thức hệ số nguyên, nguyên tố cùng nhau trên [ ].x ¤ Giả sử rằng với mọi n∈¢ thì ( ), ( )P n Q n nguyên dương và 2 Q n ( ) −1 chia hết 3 P n ( ) −1. Chứng minh rằng ( )Q x là đa thức hằng.
Giải Do ( ), ( )P x Q x ∈Z x[ ] và nguyên tố cùng nhau trên [ ],¤ x nên tồn tại các đa thức ( ), ( ) [ ] u x v x ∈Z x và số nguyên dương d sao cho
Giả sử ( )Q x không là đa thức hằng số Khi đó dãy số ( Q n ( ) ) n ∈¢ không bị chặn, mà ta lại có ( ) *,
Q n ∈¥ ∀ ∈n ¢ nên deg( )Q chẵn và hệ số của số hạng bậc cao nhất của ( )Q x dương Từ đó ta có thể chọn m∈¢ sao cho M =2 Q m ( )− ≥1 3 max { P (1), (2), , ( ) P P d }.
Theo giả thiết, ta lại có M =2 Q m ( ) 1 − | 3 P m ( ) 1 − , (1) nên ( , 2) ( ,3) 1.M = M = Gọi ,a b lần lượt là cấp của 2,3 theo (modM).
Từ (1) ta có a Q m b P m| ( ), | ( )⇒( , )a b ≤( Q m P m( ), ( ))≤d. Đặt s=( , )a b ⇒ ∃x y 0 , 0 ∈¢ sao cho s ax= 0 +by 0 Do 1≤ ≤ ⇒ ∃ ∈s d k ¥,0≤ 3 là số nguyên tố và p có dạng p=3n+1 Chứng minh rằng ta luôn có 2
Để chứng minh rằng với số nguyên tố \( p = 3n + 1 \), thì \( -3 \) là số chính phương modulo \( p \), ta bắt đầu với việc nhận thấy rằng \( n \) phải là số chẵn, tức là \( n = 2l \), do đó \( p = 6l + 1 \) Nếu \( l = 2 \), thì \( p \) sẽ là số nguyên tố và \( (p - 1)/2 \) sẽ là số chẵn Như vậy, \( (1)^{-1} \) là số chính phương modulo \( p \) và \( 3 \) cũng là số chính phương modulo \( p \) Cuối cùng, ta có thể kết luận rằng \( (3)(1)^{-1} = -3 \) là số chính phương modulo \( p \).
Nếu l = + ⇒ =2 1t p 12t+ ⇒7 (p−1) / 2 6= +t 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ẻ để x 2 ≡ −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ử k i≡ (mod ),p với 1≤ ≤i p ta có i 2 + + ≡i 1 0(mod )p ( 2 )
Nhận xét Ta có thể chứng minh được
Bài toán 8 (VMO 2004) yêu cầu tìm giá trị tối thiểu của tổng các chữ số S(n) của một số nguyên dương n, trong đó n là bội số của 2003 Cần xác định S(n) cho các số tự nhiên n và tìm min(S(n)).
Đặt p là số nguyên tố, ta có 1S n > vì 10 k không chia hết cho p Giả sử tồn tại n là bội của p, từ đó suy ra tồn tại k sao cho 10 k ≡ −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 đó ( ) 3.S n ≥ Tiếp theo ta sẽ chứng minh tồn tại n là bội của p sao cho ( ) 3.S n Ta có 10 7 ≡2 10 ⇒2.10 700 ≡2 1001 =2 ( p − 1)/2 ≡ −1(mod ),p vì p 03 8≠ k±1.
Ta chọn n=2.10 700 +1 thì n là bội của p và ( ) 3.S n 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.
Trong bài viết này, chúng ta sẽ chứng minh rằng với mọi số tự nhiên n ≥ 2, ước số nguyên tố của số Fecma F_n = 2^{2^n} + 1 có dạng m·2^n + 2 + 1, trong đó m là số nguyên dương Đồng thời, chúng ta cũng nhận xét rằng tồn tại vô hạn số tự nhiên n là bội của 2003 sao cho điều kiện trên được thỏa mãn.
Giải Gọi p là một ước nguyên tố của F n Suy ra 2 2 n ≡ −1(mod )p ⇒2 2 n + 1 ≡1(mod ).p Gọi
Nếu k n≤ ⇒2 2 k ≡1(mod )p ⇒2 2 n ≡1(mod ),p mâu thuẫn với 2 2 n ≡ −1(mod ).p
Vậy k=2 n + 1 Mặt khác theo định lí Fecma ta có 2 p − 1 ≡1(mod ),p suy ra
Bài 10 Cho k=2 2 n +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à ước của 2 1
Giải Vì k=2 2 n +1 là số nguyên tố, nên theo luật luật tương hỗ Gauss, ta có
Do đó theo bổ đề Gaus, ta có
Bài 11 Cho đa thức f x( )=x 8 −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 pM
- Nếu 2 là số chính phương modulo p thì tồn tại n∈¥ * sao cho ( ) 0(mod ).p n ≡ p
- Nếu 2− là số chính phương modulo p thì tồn tại n∈¥ * sao cho ( ) 0(mod ).p n ≡ p
- Nếu 1− là số chính phương modulo p thì tồn tại n∈¥ * sao cho ( ) 0(mod ).p n ≡ p
- Nếu 2, 2, 1− − đều không là số chính phương modulo p thì
Nhưng ta lại có 2 2 1 ( 2) 2 1 ( 1) 2 1 ( 1)( 1) 1(mod ), p p p p
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
( ) ( )( )( ), 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 pM
- Đ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 12 (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 2 n −1|m 2 +9.
Giải Ta viết n−2 ; , s t s t∈¥,t là số lẻ.
Nếu t≥3, thì 2 t −1| 2 n − ⇒ −1 2 t 1|m 2 +9 Ta có 2 1 t − ≡ −1(mod 4), tức là 2 1 t − 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 | 2 1,/ t − ∀t lẻ.
Từ đó suy ra p m| 2 + ⇒9 m 2 ≡ −9(mod ).p Vậy −9 là thặng dư bậc hai theo modulo p, suy ra
2 p− là số chẵn, tức là p≡1(mod 4) Mâu thuẫn.
Từ kết quả trên, ta có thể kết luận rằng t=1 hoặc n=2 Chúng ta sẽ chứng minh rằng n=2 và s (với s thuộc tập hợp các số tự nhiên) là tất cả các giá trị cần tìm Cụ thể, chúng ta sẽ chỉ ra rằng số nguyên m thỏa mãn điều kiện 2^n - 1 chia hết cho m^2 + 9.
Từ đó để 2 n −1|m 2 +9, ta cần có 2 2 k +1|m 2 + ∀ =9, k 0,1, ,s−1.
Mặt khác dễ chứng minh được các số Fecma có tính chất: 2 2 m +1, 2 2 k + = ∀ ≠1÷ 1, m k.
Do đó theo định lí thặng dư Trung Hoa thì tồn tại số nguyên x 0 thỏa mãn hệ đồng dư
Từ đó suy ra x 0 2 + ≡9 0(mod 2 2 i + ∀ =1), i 0,1, ,s−1.
Từ đây suy ra 2 n −1| 3(x 0 2 + ⇒1) 2 n −1|x 0 2 + ⇒9 2 n −1|m 2 +9, với m x= 0 đâ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à n=2 , s với s∈¥.
Bài 13 ( APMO, 1997) Tìm một số n nằm giữa 100 và 1997 sao cho | 2n n +2.
Để chứng minh rằng n là số chẵn, ta thấy rằng n thỏa mãn điều kiện nhất định Theo Định lý Fermat, không thể có n = 2p, với p là số nguyên tố Do đó, chúng ta xem xét trường hợp n = 2pq, trong đó p và q là các số nguyên tố khác nhau Chúng ta cần phân tích thêm để làm rõ vấn đề này.
− + ⇒− ÷ = − ÷ Theo Định lí Fermat ta lại có
| 2 q 1, | 2 p 1 p − + q − + , dễ thấy q=3,5,7 không thoã mãn, ta thử chọn q xem sao Trong trường hợp này chúng ta tìm thấy pC Chúng ta còn lại chỉ cần chứng minh với
43, 11 p= q= Thật vậy, chỉ cần chứng minh rằng 2 2 p q 1
và p| 2 2 1 q − +1, | 2q 2 p − 1 +1. Điều này là rất dễ dàng kiểm tra
Bài 14 ( IMO Longlits, 1992, ROM 2) Cho ,a b là các số nguyên Chứng minh rằng
− + 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ì 2a 2 −1chia hết cho 2, vô lí.
Trong trường hợp b lẻ, ta có b^2 + 2 ≡ 3 (mod 8), từ đó suy ra rằng b^2 + 2 có ước số nguyên tố lẻ dạng 8k + 3 Gọi một trong những ước số đó là p, vì 2a^2 - 1 chia hết cho p nên (a, p) = 1 Do đó, tồn tại a1 sao cho
1 1(mod ) aa ≡ p , khi đó ta có:
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
2.2.2 Các bài toán về tồn hay không tồn tại Biểu diễn số nguyên
Thặng dư bình phương đóng vai trò quan trọng trong việc chứng minh sự tồn tại hay không tồn tại trong các bài toán số học thi Olympic Nó cũng liên quan đến việc biểu diễn một số nguyên theo các dạng nhất định.
Bài 15 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
Giải Ta thấy p| a 2 +b 2 +1 khi và chỉ khi a 2 ≡ − −b 2 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.
A= r r ≡i p i= − B= s s ≡ − −j p j= − trong đó các số r i đôi một không đồng dư với nhau theo modp, cũng như các số s j đôi một không đồng dư với nhau theo modp và r s i , j ∈{ 1, 2, , p−1 }
Nếu A B∪ < −p 1, thì A B∩ ≠ ∅ nên tồn tại
Nếu A B∪ = −p 1, thì A B∩ = ∅ nên các số ,r s i j đôi một phân biệt, suy ra
Từ (1) và (2) suy ra mâu thuẫn
Vậy các số nguyên ,a b sao cho a 2 +b 2 +1 là bội số của p
Bài 16 Chứng minh rằng có vô số hợp số dạng 2 2 n +1 hoặc 6 2 n +1 ( hoặc cả hai)
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 x +1 và 6 2 x +1 đều là số nguyên tố Ta thấy, với m n N> >
6 m + ≡1 3 m +1(mod 2 n +1) Nếu 3 không phải là thặng dư bình phương mod 2 2 n +1, thì với m=2 n − 1 thì
Vậy 3 là thặng dư bình phương mod 2 2 n +1,
Bài 17 ( Việt Nam TST 2004) Chứng minh rằng số 2 n +1 không có ước số nguyên tố nào có dạng 8k−1.
Giải Giả sử 2 n +1 có ước số nguyên tố p dạng 8k−1
Nếu n là số chẵn thì
− ≡ do đó 1− là số chính phương modulo p.
Tương tự nếu là n số lẻ thì
− ≡ do đó 2− là số chính phương modulo p (1)
Bài toán được chứng minh
Bài 18 (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 3 n +5 n chia hết cho n 2 −25.
Giải Giả sử ngược lại, tồn tại số nguyên n>5, sao cho 3 n +5 n chia hết cho n 2 −25.
Nếu n chẵn, tức là n=2 ,k thì từ n>5,suy ra n 2 −25 1.> Do đó n 2 −25 có ước nguyên tố
Vậy n lẻ Bây giờ ta xét p là một ước nguyên tố bất kì của n 2 −25, thì ta có 3 n +5 n Mp.
Suy ra theo luật tương hỗ Gauss, ta có
Suy ra rằng n đồng dư với 1, 2, 4, hoặc 8 theo (mod 15) Tất cả ước nguyên tố của n² - 25 đều có dạng 15k + r, với r thuộc {1, 2, 4, 8} Do đó, mọi ước nguyên tố của n - 5 và n + 5 cũng phải thuộc dạng này Tích của hai số dạng 15k + r, với r ∈ {1, 2, 4, 8}, sẽ là số cũng có dạng như vậy, dẫn đến n - 5 và n + 5 đồng dư với 1, 2, 4, 8 theo (mod 15) Tuy nhiên, điều này không thể xảy ra vì hiệu của hai số thuộc tập {1, 2, 4, 8} không chia hết cho 5 Mâu thuẫn này chứng tỏ bài toán đã được chứng minh.
Bài 19 (Indonesia TST, 2009) Chứng minh rằng tồn tại vô hạn số nguyên dương n sao cho
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.
Theo tiêu chuẩn Euler, ta có 1 ( 1)/2
Hay 1− là số chính phương (modop).
Từ đó tồn tại m ∈ { 1, 2, , p − 1 } sao cho m 2 + ≡1 0(mod ) p
Ví m< p, nên m! không chia hết cho p nên m 2 +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
Bài toán này có thể bắt nguồn từ ý tưởng của bài 3 trong kỳ thi Olympic Toán Quốc tế lần thứ 49 năm 2008, do Kestuis Cesnavicius từ Lithuania sáng tác Đây là bài toán khó nhất trong ngày thi đầu tiên Từ bài toán này, nhiều quốc gia đã phát triển thành các đề thi Olympic và đề chọn đội tuyển cho các năm sau.
Bài 20 (IMO shortlist, 2008) Chứng minh rằng tồn tại vô số số nguyên dương n sao cho n 2 +1 có ước nguyên tố lớn hơn 2n+ 10 n
Giải Xét số nguyên tố p dạng p=8k+1,k∈¥ * Theo tiêu chuản Euler, ta có
Nghĩa là 1− là số chính phương modulo p, nên phương trình x 2 ≡ −1(mod ),p có hai nghiêm thuộc { 1, 2, , p − 1 } và hai nghiệm đó có tổng bằng p (vì (p m− ) 2 ≡m 2 (mod )p ).
Gọi n là nghiệm nhỏ hơn trong hai nghiệm đó, ra tồn tại 1
Chúng ta sẽ chứng minh rằng p>2n+ 10 n Thật vậy, đặt 1
Ta có (2l+1) 2 ≡ ≡1 p(mod8), nên từ (1) suy ra r≡5(mod8)⇒ ≥r 5.
5 , p=u + ta được bất phương trình
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 21 ( Turkey TST 2006) Với mỗi số nguyên dương n chúng ta xác định dãy ( )x n như sau
1 1 2 , n n x + =x +x + +x với x 1 là một số nguyên dương Tìm x 1 nhỏ nhất sao cho 2006 | x 2006
Giải Chúng ta thấy rằng x n + 1 =x n +x n n 2 , ≥1 , do đóx n là số chẵn với mọi n≥2.
⇔ ≡ hoặc x n − 1 ≡ −1(mod1003) Bây giờ ta sẽ chứng minh đồng dư x n ≡ −1(mod1003)không thể xảy ra với mọi n≥2, giả sử tồn tại n≥2 sao cho x n ≡ −1(mod1003) thì
Vậy 3− là thặng dư bình phương mod1003 Mâu thuẫn với Định lí 8.
Do đó x 2 ≡0(mod1003) ⇔x 1 ≡0(mod1003) hoặc x 1 ≡ −1(mod1003).
Vậy giá trị nhỏ nhất của x 1 là 1002.
Bài 22 (KHTN Hà Nội, 2018) Cho dãy số nguyen dương ( )a n thỏa mãn a n + 1 =a 3 n +4a n với mọi n≥1 Tìm giá trị nhỏ nhất của a 1 để a 2018 +2018 chia hết cho 57.
Giải Vì 57 3.19,= nên để a 2018 +2018 chia hết cho 57 thì hai điều kiện sau đông thời thỏa mãn: a) a 2018 ≡2(mod 3). b) a 2018 ≡ −4(mod19).
Trước hết, xét theo modulo 3 cho toàn bộ các số hạng của dãy ( ),a n ta được.
1 (mod 3). n n n n a + ≡a +a ≡ −a Như vậy a 2 ≡ −a a 1 3 , ≡a 1 , ,a 2018 ≡ −a 1 (mod 3) Do đó điều kiện a) tương đương với − ≡a 1 1(mod 3)⇔a 1 ≡2(mod 3).
Mặt khác ta lại có a n + 1+ =4 a n 3 +4a n + ≡4 ( a n +4 () a n +4) 2 +7(a n + −4) 5 (mod19).
Ta sẽ chứng minh rằng x 2 +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ư:
Phương trình này vô nghiệm, vì 12 4 3 3 19 1
Như vậy (a n +4) 2 +7(a n + − ≡4) 5 0(mod19), do đó a n + 1 + ≡4 0(mod19)⇒a n + ≡4 0(mod19). Suy ra điều kiện b) tương đương với a 1 ≡ −4(mod19) Tóm lại để a 2018 +2018 chia hết cho 57 , thì a 1 phải thỏa mãn hệ điều kiện:
Vì a 1 >0, nên a 1 S là số nhỏ nhất cần tìm.
Chúng ta sẽ tiếp tục khám phá ứng dụng của thặng dư chính phương trong việc giải các phương trình Diophant, một ứng dụng kỹ thuật của công cụ này Các bài toán được giới thiệu sau đây không chỉ thú vị mà còn đầy thách thức, thể hiện sức mạnh và sự sắc bén của khái niệm thặng dư bình phương.
2.2.3 Các bài toán về phương trình nghiệm nguyên
Bài 23 ( Putnam, 1954) Chứng minh rằng không có số nguyên ,x y nào sao cho
2 3 2 2 122. x − xy− y Giải Giả sử tồn tại các số nguyên ,x y sao cho x 2 −3xy−2y 2 2, khi đó ta có:
Vì 488 12(mod17)≡ , Suy ra 12 là thặng dư bình phương mod17, lại có
Bài 24 Chứng minh rằng phương trình x 2 + ≡5 y 3 không có nghiệm nguyên.
Giải Giả sử phương trình x 2 + ≡5 y 3 có nghiệm nguyên ( , ).x y
Nếu y chẵn thì x 2 + ≡5 0(mod 8)⇒x 2 ≡3(mod8), điều này vô lí theo định lí 7 Do đó y phải lẻ.
Từ y lẻ, nên y 2 +2y+4 lẻ, gọi p là một ước nguyên tố lẻ của y 2 +2y+4, có dạng
Vậy (1) và (2) mâu thuẫn với nhau Vậy phương trình x 2 + ≡5 y 3 vô nghiệm.
Bài 25 (Serbia MO, 2008) Tìm tất cả các nghiệm nguyên không âm của phương trình
Nếu x là số chẵn dương thì vế trái của phương trình có dạng a 2 +b a b 2 , , ∈¥ * (1)
Nếu x là số là số lẻ thì vế trái có dạng 3a 2 +b a b 2 , , ∈¥ * (2)
Mà 2008 251.8= và số p%1 là số nguyên tố lẻ và từ phương trình suy ra p không chia hết
, a b Nên từ (1) và phương trình suy ra 2 2 1
Từ (2) và phương trình suy ra 2 2 3
Ta có (1) và (2) mâu thuẫn Vậy z= ⇒ = =0 x y 0.
Do đó phương trình có nghiệm duy nhất x= = =y z 0.
Bài 26 (Tukey TST, 2013) Tìm nghiệm nguyên dương của phương trình
Xét n>1 Nếu n+1 3,M thì từ phương trình ta có:
Do đó n+1 không chia hết cho 3
Nếu n+ ≡1 1(mod 3)⇒n| 3⇒m 6 ≡ −1(mod 3) Vô lí.
Do đó n+ ≡ −1 1(mod 3) Suy ra tồn tại ước nguyên tố p của n+1 mà p≡ −1(mod 3).
Nếu n+1 2,M thì lập luận như trên, ta cũng suy ra mâu thuẫn.
Vậy n+1 phải lẻ, từ phương trình ta được m 6 + = 3 ( n n + 1 + + + 1 ) ( n 1 ) M n + 1 M p
≡ − ⇒ ÷= ⇒ ÷ ÷ (1) Theo đinhlí Euler, ta có
Theo luật tương hỗ Gaus, ta có
Từ hai kết quả trên, ta suy ra
Từ (1) và (2) suy ra mâu thuẫn Vậy phương trình có nghiệm nguyên dương duy nhất là
( , ) (1;1).m n Bài 27 ( Korea MO 2000) Chứng minh rằng với mỗi số nguyên tố p tồn tại các số nguyên , , , x y z w sao cho x 2 +y 2 +z 2 −wp=0và 0< 2 Xét trường hợp 1− là thặng dư bình phương modp Thì tồn tại số nguyên
(0 1) a < < −a p sao cho a 2 ≡ −1 (mod )p Đặt ( , , ) (0,1, )x y z = a Bởi vì x 2 +y 2 +z 2 =a 2 +1 chia hết cho p và nó lớn nhất là 1 (+ p−1) 2 < p 2 , nên tồn tại (0w <