SỞ GIÁO DỤC VÀ ĐÀO TẠO VĨNH PHÚC
TRƯỜNG THPT CHUYÊN VĨNH PHÚC
BÁO CÁO KẾT QUẢ
SÁNG KIẾN KINH NGHIỆM
TÊN SÁNG KIẾN KINH NGHIỆM: SỬ DỤNG HỆ THẶNG DƯ ĐẦY ĐỦ,
THẶNG DƯ THU GỌN, THẶNG DƯ TRUNG HOA ĐỂ GIẢI TOÁN SỐ HỌC.
MÔN
: TOÁN HỌC
TỔ BỘ MÔN
: TOÁNTIN
MÃ
: 55
NGƯỜI THỰC HIỆN : NGUYỄN DUY LIÊN
ĐIỆN THOẠI : 01233045361
E mail :
[email protected]
Bài viết này của thầy Nguyễn Duy Liên đã được đăng trong Tạp chí Toán Học và
Tuổi Trẻ trong hai số tháng 8 và 9 năm 2013. Cảm ơn thầy gửi đến chia sẻ với
www.laisac.page.tl
1
LỜI NÓI ĐẦU
Ngạn ngữ Pháp có câu: "Le Mathématique est le Roi des Sciences mais
L’Arithmétique est la Reine",dịch nghĩa:"Toán học là vua của các khoa học nhưng
Số học là Nữ hoàng". Điều này nói lên tầm quan trọng của Số học trong đời sống và
khoa học. Số học giúp con người ta có cái nhìn tổng quát, sâu rộng hơn, suy luận
chặt chẽ và tư duy sáng tạo.
Trong các kì thi chọn học sinh giỏi các cấp THCS, THPT cấp tỉnh, cấp Quốc
gia,cấp khu vực, cấp quốc tế, các bài toán về Số học thường đóng vai trò quan
trọng. Chúng ta có thể làm quen nhiều dạng bài toán Số học, biết nhiều phương
pháp giải, nhưng cũng có bài chỉ có một cách giải duy nhất. Mỗi khi gặp một bài
toán mới chúng ta lại phải suy nghĩ tìm cách giải mới. Sự phong phú đa dạng của
các bài toán Số học luôn là sự hấp dẫn đối với mỗi giáoviên, học sinh giỏi yêu
toán. Xuất phát từ những ý nghĩ đó tôi đã sưu tầm và hệ thống lại một số bài toán
để viết lên chuyên đề "Sử dụng hệ thặng dư đầy đủ, hệ thặng dư thu gọn,thặng dư
Trung Hoa để giải toán Số học ".
Chuyên đề gồm các phần :
Phần I: Kiến thức cơ bản.
Phần II:Ứng dụng hệ thặng dư để giải toán
· Ứng dụng 1: Sử dụng hệ thặng dư để tính tổng
· Ứng dụng 2: Sử dụng hệ thặng dư trong các bài toán đa thức, dãy số nguyên.
· Ứng dụng 3: Sử dụng hệ thặng dư trong tập con tập số nguyên dương, bài
toán số học chia hết
· Ứng dụng 4: Sử dụng hệ thặng dư trong phương trình Đi Ô Phăng bậc nhất.
Phần III: Bài tập tương tự.
Mục tiêu ở đây là một số bài mẫu, một số bài khác biệt căn bản đã nói lên
được phần chính yếu của chuyên đề. Tuy vậy, những thiếu sót nhầm lẫn cũng
không thể tránh khỏi được tất cả , về phương diện chuyên môn cũng như phương
diện sư phạm. Lối trình bày bài giải của tôi không phải là một lối duy nhất. Tôi đã
cố gắng áp dụng cách giải cho phù hợp với chuyên đề, học sinh có thể theo mà
không lạc hướng. Ngoài ra lúc viết tôi luôn luôn chú ý đến các bạn vì nhiều lí do
phải tự học, vì vậy giản dị và đầy đủ là phương châm của tôi khi viết chuyên đề
này.
Tôi xin trân thành cảm ơn các thầy cô giáo,các em học sinh góp ý thêm cho
những chỗ thô lâu và phê bình chân thành để có dịp tôi sửa chữa chuyên đề này
hoàn thiện hơn.
Vĩnh Yên, Trung Thu, năm 2012
NGUYỄN DUY LIÊN
2
PHẦN I. KIẾN THỨC CƠ BẢN
1.Hệ thặng dư đầy đủ
Cho tập A = {a 1 ,a 2 ,...,a n } . Giả sử ri ,0 £ ri £ n - 1 là số dư khi chia a i cho r .
i
Nếu tập số dư {r1 ,r2 ,..., r n } trùng với tập {0,1,..., n - 1} thì ta nói A là một hệ thặng
dư đầy đủ (gọi tắt là HĐĐ) modun n.
Dễ thấy: Tập A lập thành một HĐĐ(modun n) nếu và chỉ nếu:
i ¹ j Þ a i ¹ a j ( mod n ) .
Nếu A = {a1 ,a 2 ,...,a n } là HĐĐ mod n thì từ định nghĩa dễ suy ra
· Với mọi m Î Z tồn tại duy nhất a i Î A sao cho a i º m ( mod n ) .
· Với mọi a Î Z tập a + A = {a + a1 ,a + a 2 ,...,a + a n } là HĐĐ mod n
· Với mọi cÎ Z , ( c, n ) = 1 , tập cA = {ca 1 ,ca 2 ,...,ca n } là HĐĐ mod n.
Tập A * = {0,1,2,...,n - 1} là HĐĐ mod n không âm nhỏ nhất.
Số phần tử của tập A bằng A = n
2. Hệ thặng dư thu gọn.
Cho tập B = {b1 , b 2 ,...,b k } là một tập hợp k số nguyên và ( bi ,n ) = 1với mọi
i = 1, 2,..., k .Giả sử b i = q i n + ri ,1 £ ri < n .Khi đó dễ thấy ( ri ,n ) = 1 . Nếu tập
{r1 ,r2 ,..., r k } bằng tập K gồm tất cả các số nguyên dương bé hơn n và nguyên tố
cùng nhau với n thì B được gọi là hệ thặng dư thu gọn mod n , gọi tắt là HTG mod
n.
Dễ thấy tập B = {b1 , b 2 ,...,b k } gồm k số nguyên lập thành một HTG mod n
khi và chỉ khi:
1) ( bi ,n ) = 1;
2) b i ¹ b j ( mod n ) với 1 £ i ¹ j £ k ;
3) Số phần tử của B là j ( n ) ( trong đó j ( n ) là hàm Ơle của n.
Điều kiện 3) tương đương với
'
3 ) Với mọi x Î ¢ , ( x,n ) = 1tồn tại duy nhất b i Î B sao cho x º b i ( mod n ) .
Từ định nghĩa ta suy ra nếu tập B = {b1 , b 2 ,...,b k } là HTG mod n
với c ΢, ( c, n ) = 1 thì tập B = {cb1 ,cb 2 ,...,cb k } cũng là HTG mod n.
3
Ngày xưa người ta đã sử dụng HĐĐ,HTG để chứng minh các định lí
Ơle,Féc ma ….trong chuyên đề ta không nói lại nữa.
2. Định lý thặng dư Trung Hoa.
Định lí thặng dư Trung Hoa là một trong những viên Kim cương của toán học
.Định lí này vừa mang tính đẹp mắt của Toán học thuần tuý,vừa có ứng dụng sâu
xa.Trải qua nhiều thời đại,nó được cải biên dưới nhiều hình thức,cho cả Toán học
cổ điển lẫn hiện đại.
a)Định lý thặng dư Trung Hoa dạng đơn giản.
Gọi r và s là các số nguyên dương nguyên tố cùng nhau, a và b là hai số nguyên
ìï N º a ( mod r )
tuỳ ý.Khi đó tồn tại một số nguyên N sao cho : í
ngoài ra, N được
ïî N º b ( mod s )
xác định duy nhất theo modulo rs
b)Định lý thặng dư Trung Hoa dạng tổng quát.
Cho k số nguyên dương n1 , n2 , n3 ,...., n k đôi một nguyên tố cùng nhau và k số
nguyên bất kì a1 , a2 , a3 ,..., a k .Khi đó tồn tại số nguyên a thoả mãn hệ :
a º ai ( mod ni ) với "i = 1,2,..., k (1).Số nguyên b thoả mãn (1) khi và chỉ khi
b º a ( mod n ) trong đó n = n1.n2 n3 ... nk .
PHẦN II. ỨNG DỤNG HỆ THẶNG DƯ ĐỂ GIẢI TOÁN
· Ứng dụng 1.Sử dụng hệ thặng dư để tính tổng,số nghiệm
của một phương trình.
Ví dụ 1.1.
Với mỗi cặp số nguyên dương nguyên tố cùng nhau ( p,q ) đặt
é ( p - 1) q ù
é q ù é 2q ù
S = ê ú + ê ú + L + ê
ú ,trong đó [ x ] là số nguyên lớn nhất không vượt
p
p
p
ë û ë û
ë
û
quá x. Hãy xác định các giá trị của p, q để S là một số nguyên tố.
Lời giải :
Với mỗi a Î ¡ đặt {a} = a - [ a ] .Khi đó với k Î ¥ ta có
ì kq ü r k
í ý = ở đây r k là số dư trong phép chia kq cho p do vậy : 0 £ rk £ p - 1 ,
î p þ p
q 2q
( p - 1) q - æ r1 + r 2 + L + r p-1 ö
S = +
+L+
çp p
p p
p
p ÷ø
è
4
vì ( p,q ) = 1 Þ rk ¹ 0"k = 1,2,....,p - 1 từ đó ta thấy tập A = {r1 , r2 ,...,rp -1 } chính là
một hoán vị của tập A = {1, 2,....,p - 1} thậy vậy ngược lại :
ì1 £ j - i £ p - 2 ì1 £ j - i £ p - 2
$i, j Î {1,2,...,p - 1} ,i < j mà ri = rj Þ í
Ûí
vô lí
j
i
q
M
p
j
i
M
p
(
)
î
î
r
( p - 1)( q - 1 )
r r
1 + 2 + L + p - 1 p - 1
Từ đó 1 + 2 + L + p-1 =
=
Þ S =
(1 )
2
p p
p
p
2
Từ (1 ) để S là số nguyên tố cần có p ¹ 1,q ¹ 1 và ít nhất 1 trong 2 số p,q lẻ
Trường hợp 1: p,q cùng là số lẻ Þ p,q ³ 3,p ¹ q do ( p,q ) = 1 ,kết hợp (1)
Þ S là số chẵn lớn hơn 2 Þ S không là số nguyên tố.
Trường hợp 2: p là số chẵn q là số lẻ.
éì
êï( p,q ) = 1
êï
êí p - 1 = 1
é ìp = 2
êï q - 1
ÎÃ êíq = 2h + 1( h ÎÃ)
êï
êî
î 2
S ÎÃÛ ê
Ûê
(2)
êì
q
=
3
ì
ï
êï( p,q ) = 1 ê í
ê ïp = t + 1( t ÎÃ, t º/ 2 ( mod 3 ) )
êï
ëî
êí p - 1 ÎÃ
êï q - 1
êï
= 1
ë î 2
ở đây kí hiệu à là tập số nguyên tố
Trường hợp 3: q là số chẵn p là số lẻ do tính đối của p,q của biểu thức xác định S
é ì p = 2m + 1( m ÎÃ)
êí
ê îq = 2
theo trường hợp 2 : ê
(3)
p = 3
ì
ï
êí
ê ïîq = n + 1( n ÎÃ, n º/ 2 ( mod 3 ) )
ë
Vậy tóm lại tất cả các giá trị p,q cần tìm là các cặp xác định ở (2) và (3).
2006
é17 k ù
Ví dụ 1.2. Tính tổng : S = å ê
ú .
k = 4 ë 11 û
Lời giải:
é a ù a - r
Nhận xét 1: nếu a º r ( mod b ) ,với a,b, r Î Z ,0 £ r £ b - 1 thì ê ú =
b
ëbû
5
Nhận xét 2: Vì 1710 º 1( mod11) nên tập B = {1710 t ,1710 t +1 ,....,1710 t +9 } là HTG mod
11 nó là một hoán vị của tập {1,2,....,10 } .
Nhận xét 3:
mỗi
i Î Z Ç [ 0;9 ] gọi
n i là số
phần
tử
của
tập
hợp
D i = {k Î Z 4 £ k £ 2006,k º i ( mod10 )} kiểm tra ta dễ thấy :
n 4 = n 5 = n 6 = 201, và n 0 = n1 = n 2 = n 3 = n 7 = n 8 = n 9 = 200 .
Từ các nhận xét suy ra:
2006
- ( n 0 + 6n1 + 3n 2 + 7n 3 + 9n 4 + 10n 5 + 5n 6 + 8n 7 + 4n 8 + 2n 9 )
é17 ù k =4
å
ê
ú=
11
k =1 ë 11 û
2003
10
17 - 1
17 4 .
- ( 9 + 10 + 15 ) - 200å j
17 2007 - 259905
17 - 1
j=1
=
=
.
11
176
17 2007 - 259905
Vậy S =
176
Ví dụ 1.3. Cho m,n là 2 số nguyên dương nguyên tố cùng nhau với m chẵn và n lẻ
n -1
é mk ù
ì mk ü 1
.Chứng minh rằng :Tổng S = å ( -1) êë n úû . í
ý + không phụ thuộc vào m,n.
k =1
î n þ 2n
Lời giải:
n -1
é mk ù
ì mk ü 1 1
*
Ta chứng minh rằng S = å ( -1) êë n úû . í
ý= k =1
î n þ 2 2n
é mk ù
Ta có: mk = n ê
+ r k trong đó 0 £ rk £ n - 1"k Î {1,2,...,n - 1} .
ë n úû
Ta thấy rằng :
a) Do ( m, n ) = 1 Þ rk ¹ 0"k Î{1,2,..., n - 1} từ đó tập
2006
k
å 17
k
B = {r1 ,r2 ,...,rn -1 } là một hoán vị của tập: {1,2,..., n - 1} .
ì mk ü r k
b) í
ý = với k = 1, 2,..., n - 1 .
î n þ n
é mk ù
c) Với m chẵn n lẻ ê
º rk ( mod 2 ) .
ë n úû
Từ đó ( -1)
é nk ù
ê m ú
ë û
r k
= ( -1) "k = 1,2,3,...,n - 1
n -1
1
1 1
r
S* = å ( -1) rk = éë( 2 + 4 + L + n - 1) - (1,3,L ,n - 2 ) ùû = -
(Đpcm)
k =1
n
2 2n
Ví dụ 1.4.
Cho p là số nguyên tố p º 3 ( mod8 ) Ú p º 5 ( mod8 ) ,và p=2q+1 ( q ÎÃ)
k
6
p -1
Tính tổng S = w2 + w4 + L + w2 (với w ¹ 1 là nghiệm của pt: wp = 1 )
Lời giải:
æ 2 ö
p º ±3 ( mod8 ) Þ 2 không là số chính phương mod p Û ç ÷ = -1
èpø
Û2
p -1
2
(* )
º -1( mod p ) Û 2q º -1( mod p ) Þ 22q º 1( mod p ) .Gọi h là cấp của 2 theo
mod p Þ 2 h º 1( mod p ) .Vậy ta có h p - 1 = 2q
do q ÎÃ Þ h = 1 Ú h = 2 Ú h = q Ú h = 2q .
· h = 1 Þ 2 º 1( mod p ) Û 1 º 0 ( mod p ) (loại)
· h = 2 Þ 2 2 º 1( mod p ) Þ p = 3 Þ q = 1 không là số nguyên tố (loại)
· h = q Þ 2q º 1( mod p )
(** )
từ (*),(**) Þ 2 º 0 ( mod p ) Þ p = 2 (loại)
· h = 2q = p - 1 Þ 2 là căn nguyên thuỷ mod p Þ A = {21 ,2 2 ,...,2 p -1 } là HTG
mod p nó là một hoán vị của tập {1,2,3,...,p - 1} từ đó ta có tổng
S = w + w + L + w
2
4
2p -1
= w + w + L + w
Ví dụ 1.5 .
Cho p là số
p
hiệu: i º ri ( mod p ) ( r phần
i
S = r1 + r2 + L + rp -1 .
2
p -1
w ( wp-1 - 1 ) wp - w 1 - w
=
=
=
= -1
w -1
w - 1 w - 1
nguyên tố lẻ với mỗi i = 1, 2,..., p - 1 .Kí
dư của i p khi chia cho p).Tính tổng :
Lời giải:
2S = ( r1 + rp-1 ) + ( r2 + rp- 2 ) + L + ( rp -1 + r1 ) ta có
p
ri + rp-i = i p + ( p - i ) "i = 1,2,...,p - 1 mà
p
i p + ( p - i ) = p p - C1p p p-1i + Cp2 p p - 2i 2 + L + C pp -11pi p -1
do p ÎÃÞ Ci p º 0 ( mod p ) "i = 1,2,...,p - 1 Þ ri + rp -i º 0 ( mod p 2 )
mà 0 < ri < p 2 ,0 < rp-i < p 2 Þ ri + rp -i = p 2 "i = 1,2,...,p - 1 .Từ đó ta thu được
( p - 1) p
S =
2
2
p3 - p 2
=
.
2
Ví dụ 1.6
Tìm sốnguyên dương nhỏ nhất có tính chất: Chia 7dư 5,chia 11dư7vàchia 13dư 3.
Giải
7
ì x º 5 ( mod 7 )
ï
Xét hệ phương trình: í x º 7 ( mod11 ) ta có
ï
î x º 3 ( mod13 )
( 7,11) = (11,13) = (13,7 ) = 1 nên theo
3
định lý thăng dư Trung hoa hệ trên có 1 nghiệm là a = å N j b j a j trong đó
j =1
n1 = 7, N1 = 11 × 13143, n2 = 11, N 2 = 13.7 = 91, n3 = 13, N 3 = 7.11 = 77 .Nên ta có:
N1b1 º 3b1 º 1( mod 7 ) Þ b1 = - 2 tương tự b2 = 4, b3 = - 1 vậy
a = 143.( -2 ) .5 + 91.4.7 + 77.( -1) .3 = 887 .Tất cả các nghiệm của hệ có dạng
b = 887 + 1001 t ( t Î ¥ ) .Vậy số cần tìm là 887.
Ví dụ 1.7.
Cho m là một số nguyên dương ,tìm số nghiệm của phương trình : x 2 º x ( mod m ) .
Giải. Giả sử m = p1a p2 a ... pka ( pi ÎÃ, a i Î ¥ ) . Ta có x 2 º x ( mod m ) khi và chỉ khi
1
x 2 º x ( mod pia
2
k
) ( "i = 1,2,..., k ) Û x ( x - 1) º 0 ( mod p ) ( "i = 1,2,..., k )
Vì ( x, x - 1) = 1 Þ pt : x ( x - 1) º 0 ( mod p ) có hai nghiệm modulo p là
x º 0 ( mod p ) và x º 1( mod p ) .Theo định lí thặng dư Trung Hoa ,với mỗi bộ
ìï x º a ( mod p )
a , a ,..., a . Hệ phương trình
luôn có nghiệm duy nhất modulo m .
ai
i
i
ai
i
ai
i
a i
i
ai
i
i
ai
i
í
ïî i = 1, 2,..., k
Do mỗi phương trình. x ( x - 1) º 0 ( mod pi a
1
2
k
i
) đều có hai nghiệm modulo p
a i
i
nên
phương trình đã cho có 2 k nghiệm.
Ví dụ 1.8 (VMO2008)
Cho m = 2007 2008 . Hỏi có bao nhiêu số nguyên dương n £ m thoả mãn điều kiện :
n ( 2 n + 1)( 5n + 2 ) M m .
Giải:
Ta có m = 9 2008.2232008 = 34016.2232008 = n1.n2 . Do (10, m ) = 1 nên n ( 2 n + 1)( 5n + 2 ) M m
Û m |10.5.2n.( 2n + 1)( 5n + 2 ) = 10n (10n + 5 )(10n + 4 ) Û m | x ( x + 5 )( x + 4 ) trong
ì x º 0 ( mod10 )
ï
đó x = 10 n .Ta có m | x ( x + 5 )( x + 4 ) Û í x ( x + 5 )( x + 4 ) º 0 ( mod n 1 )
ï
î x ( x + 5 )( x + 4 ) º 0 ( mod n2 )
Vì 3 không là ước chung của x, x + 4, x + 5 nên x ( x + 5 )( x + 4 ) º 0 ( mod n1 ) khi và
chỉ khi x º r1 ( mod n1 ) ở đó r1 Î{0, -4, - 5 } .Tương tự x ( x + 5 )( x + 4 ) º 0 ( mod n2 )
khi và chỉ khi x º r2 ( mod n2 ) ở đó r1 Î{0, -4, - 5 } .
Vậy m | n ( 2n + 5 )( 5n + 4 ) Û x º 0 ( mod10 ) ; x º r1 ( mod n1 ) ; x º r2 ( mod n2 ) .(1)
8
Vậy các số n £ m thoả mãn điều kiện bằng số các số x £ 10n1. n2 thoả mãn (1) .Với
mỗi cách chọn r1 Î {0, -4, -5} & r2 Î {0, -4, - 5 } theo định lí Trung Hoa ta có duy
nhất một số x £ 10n1. n2 thoả mãn (1) .Vậy có 9 số thoả mãn điều kiện bài ra.
· Ứng dụng 2: Sử dụng hệ thặng dư trong các bài toán đa
thức ,dãy số nguyên…
Ví dụ 2.1 .Cho số nguyên dương n và số nguyên tố p lớn hơn n+1.Chứng minh
x
x2
x p
rằng đa thức P ( x ) = 1 +
+
+ L +
không có nghiệm nguyên.
n + 1 2n + 1
pn + 1
Lời giải:
P ( x ) = 0 Û a p x p + a p-1x p-1 + L + a 2 x 2 + a 1x + a 0 = 0 (*) trong đó
a i =
( n + 1)( 2n + 1)...( pn + 1 ) Î Z i = 0,1,2,...,p .Từ giả thiết p,n = 1 Þ
( )
(
)
in + 1
Tập A = {1.n + 1,2.n + 1,...,p.n + 1} là HĐĐ mod p Þ $ k duy nhất k Î {1,2,...,p}
sao cho kn + 1 º 0 ( mod p ) hơn nữa k ¹ 1,0 < kn + 1 < p 2 Þ kn + 1 M p 2 .
Vì vậy với số k đó có a k M p đồng thời p hệ số còn lại trong đó có a 0 ,a 1 của
pt (*) đều chia hết cho p nhưng không chia hết cho p 2 (**).
Giả sử pt (*) có nghiệm nguyên x = c . Khi đó:
Þ a pc p + a p -1c p-1 + L + a 2c 2 + a 1c + a 0 = 0 ,
theo (**) thì a i M p"i Î{0,1,2,...,0} ,i ¹ k, k ¹ 0;1 .Từ đó suy ra a k c k M p
( do p ÎÃ) Þ c k M p Þ cM p Þ a i ci M p 2 ( "i Î {2,3,..p}) & a1 cM p 2 vì a1 M p,cM p .Từ đó suy
ra a 0 M p 2 mâu thuẫn với (**) vậy điều giả sử là sai ,tức là pt (*) không có nghiệm
nguyên Û P ( x ) không có nghiêm nguyên (đpcm).
Ví dụ 2.2 .Cho đa thức P ( x ) = x 3 - 11x 2 - 87x + m trong đó m Î Z .Chứng minh
rằng với mọi m tồn tại số nguyên n sao cho P ( n ) M 191 .
Lời giải:
Bổ đề:Cho p ÎÃ,p º 2 ( mod 3) , "x, y Î Z , x 3 º y 3 ( mod p ) Þ x º y ( mod p )
Thật vậy :
· Nếu x º 0 ( mod p ) Þ y 3 º 0 ( mod p ) Þ y º 0 ( mod p ) Û x º y ( mod p )
/ p ,do p º 2 ( mod 3) Þ p = 3k + 2 ( k Î ¥ ) ,theo định lí Fécma:
· Nếu x M/ p Þ y M
x p-1 = x 3k +1 º 1( mod p ) , y p-1 = y 3k +1 º 1( mod p )
9
Þ x 3k +1 º y3k +1 ( mod p ) theo giả thiết x 3 º y 3 ( mod p ) Þ x 3k º y 3k ( mod p )
Vậy y 3k +1 º x.x 3k º x.y3k ( mod p ) Û x º y ( mod p ) ( do ( y, p ) = 1)
Trở lại bài toán : P ( n ) = n 3 - 11n 2 - 87n + m
Ta chứng minh P ( n1 ) º P ( n 2 )( mod191) với n 1 ,n 2 ÎZ thì n 1 º n 2 ( mod191) .Thật
vậy do
P ( n1 ) º P ( n 2 )( mod191) Û 27P ( n1 ) º 27P ( n 2 )( mod191) Û
3
3
( 3n - 11) - 18.191n + 11 + 27m º ( 3n - 11) - 18.191n + 11 + 27m ( mod191)
Û ( 3n - 11) º ( 3n - 11) ( mod191) theo bổ đề ta có :
3n - 11 º 3n - 11( mod191) Û n º n ( mod191) (do (27,191)=(3,191)=1)
"n ,n Î A = {1, 2,...,191} A là HĐĐ mod191 thoả mãn n ¹ n thì
P ( n ) º/ P ( n )( mod191) . Û A = {P (1) ,P ( 2 ) ,...,P (191)} là HĐĐ mod191
Từ đó suy ra $n Î A = {1, 2,...,191} sao cho P ( n ) º 191( mod191)
Û P ( n ) M 191 .Vậy với mọi m tồn tại số nguyên n sao cho P ( n ) M 191 .
3
1
1
3
1
1
2
3
2
2
1
3
2
1
2
2
1
2
*
1
2
Ví dụ 2.3.
+¥
Cho dãy số {a n } n = 1 được xác định bởi a1 = 1,a n = a n -1 + a é n ù với "n = 2,3,....
ëê 2 ûú
+¥
Chứng minh rằng dãy {a n } n = 1 chứa vô số số nguyên chia hết cho 7.
Lời giải:
Phản chứng. Giả sử chỉ có hữu hạn số trong dãy chia hết cho 7 và a k là số
cuối cùng của dãy chia hết cho 7, khi đó từ công thức xác định của dãy ta có:
a 2k = a 2k -1 + a k ;a 2k +1 = a 2k + a k
nên
a 2k -1 º a 2k º a 2k +1 º b ( mod 7 ) , b º/ 0 ( mod 7 ) ( b Î Z )
Mặt khác : a 4k -3 = a 4k -3 + 0.b
a 4k - 2 = a 4k -3 + a 2k -1 º a 4k -3 + 1.b ( mod 7 )
a 4k -1 = a 4k -2 + a 2 k -1 º a 4 k -3 + 2.b ( mod 7 )
a 4k = a 4k -1 + a 2k º a 4 k -3 + 3.b ( mod 7 )
a 4k +1 = a 4k + a 2 k º a 4 k -3 + 4.b ( mod 7 )
a 4k + 2 = a 4k +1 + a 2 k +1 º a 4k -3 + 5.b ( mod 7 )
a 4k +3 = a 4 k + 2 + a 2k +1 º a 4 k -3 + 6.b ( mod 7 )
6
do ( b,7 ) = 1 Þ tập A = {a 4k -3 + ib} i =0 là HĐĐ mod7
nên trong bảy số : a 4 k -3 ;a 4 k - 2 ;a 4 k -1 ;a 4 k ;a 4 k +1 ;a 4 k + 2 ;a 4 k + 3 tồn tai một số chia hết
cho 7 mà số này lại lớn hơn a k mâu thuẫn với a k là số cuối cùng của dãy chia hết
cho 7.Điều giả sử sai nên ta có đpcm.
10
Ví dụ 2.4.
+¥
Cho dãy số {u n } n = 1 được xác định bởi u 1 = 2,u n = 3u n -1 + 2n 3 - 9n 2 + 9n - 3
p -1
với n = 2,3,... .Chứng minh rằng với mỗi số nguyên tố p thì å u i chia hết cho p.
i =1
Lời giải:
3
Từ giả thiết ta có u n + n 3 = 3 é u n -1 + ( n - 1) ù
ë
û
3
3
3
2
Từ đó Þ u n + n = 3 é u n -1 + ( n - 1) ù = 3 é u n - 2 + ( n - 2 ) ù = L = 3n -1 ( u1 + 13 ) = 3n
ë
û
ë
û
n
3
Û u n = 3 - n "n = 1,2,....
· p = 2 Þ u1 = 2M 2
p -1
· p ÎÃ,p ³ 3 thì
åu
i =1
{
i
3
= 3 + 32 + L + 3p -1 - éë13 + 23 + L + ( p - 1) ùû
} là HTG mod p.Với mọi i = 1, 2,..., p - 1
1
º 0 ( mod p ) Þ å i = å ( i + ( p - i ) ) º 0 ( mod p )
2
Ta thấy A = 1 , 2 ,3 ,..., ( p - 1)
3
3
ta có : i3 + ( p - i )
3
3
3
p -1
p -1
3
i =1
p -1
trong khi đó 3 + 32 + L + 3p -1 = 3.
3
3
i =1
3 - 1 1 p
= .( 3 - 3) M p .
3 -1 2
p -1
Vậy với mỗi số nguyên tố lẻ p thì å u i M p
i =1
p -1
Có thể nói
åi
i =1
p -1
3
º å i º
i =1
p ( p - 1 )
3
º 0 ( mod p ) do A = 13 , 23 ,33 ,..., ( p - 1) là HTG
2
{
}
mod p.
Ví dụ 2.5.
Cho p ³ 3 là một số nguyên tố và a1 ,a 2 ,...,a p- 2 là một dãy các số nguyên
dương sao cho p không là ước số của a k và a k k - 1 với "k = 1,2,...,p - 2 .Chứng
minh rằng tồn tại một số phần tử trong dãy a1 ,a 2 ,...,a p- 2 có tích đồng dư với 2
modulo p.
Lời giải:
Ta chứng minh bằng quy nạp mệnh đề sau:
Với mỗi số nguyên k = 1, 2,..., p - 1 tồn tại một tập các số nguyên
{b
,b k,2 ,..., b k ,k } thoả mãn
1. Mỗi b k ,i hoặc bằng 1 hoặc bằng tích của một số phần tử trong dãy
a1 ,a 2 ,...,a p- 2 .
k ,1
2. b k ,i º/ b k , j ( mod p ) với 1 £ i ¹ j £ k
Thật vậy:
11
/ p )
Với k = 2 chọn b 21 = 1,b 22 = a1 º/ 1( mod p ) (do a1 1 - 1M
Giả sử với 2 £ k £ p - 2 ta đã chọn được tập {b k ,1 ,b k,2 ,..., b k ,k } thoả mãn 2 t/c trên .
Ta có:
/ p nên hai phần tử khác nhau
· Vì a k M
bất kì trong tập
{a b
k
k ,1
,a k b k ,2 ,...,a k b k ,k } là phân biệt theo mod p
· Vì a k k º/ 1( mod p ) Þ ( a k b k ,1 )( a k b k ,2 ) ...( a k b k ,k ) º/ b k ,1b k ,2 ..b k ,k ( mod p )
Từ hai điều trên suy ra tồn tại chỉ số j,1 £ j £ k sao cho a k b k , j Î
/ {b k ,1 , b k ,2 ,...,b k,k } .
Xét tập {b k ,1 ,b k ,2 ,...,b k,k ,a k b k , j } ,sau khi đánh số lại các phần tử ta được tập:
{b
,b k +1,2 ,...,b k +1,k ,b k +1,k + 1 } ta thấy tập hợp này có k + 1 phần tử thoả mãn hai tính
chất trên,theo nguyên lí quy nạp mệnh đề được chứng minh.
Áp dụng xét tập {b p-1,1 ,b p-1,2 ,..., b p -1,p- 1 } ta thấy tập hợp này là một HTG mod p nên
nó chứa đúng một phần tử đồng dư với 2 mod p.Vì phần tử này khác 1 nên nó phải
đồng dư với tích của một số a k ,suy ra đpcm .
Ví dụ 2.6. Giải phương trình f ( x ) = x 4 + 2 x 3 + 8 x + 9 º 0 ( mod 35 )
Giải: Phương trình f ( x ) º 0 ( mod 5 ) có tập nghiệm C1 = {1;4} .
k +1,1
Phương trình f ( x ) º 0 ( mod 7 ) có tập nghiệm C2 = {3;5;6} .
ìï a º a 1 ( mod 5 )
Ta giải hệ phương trình í
ở đó a1 Î C1 , a2 Î C2 .Từ định lí thặng dư
a
º
a
mod
7
(
)
ïî
2
Trung Hoa ta tìm được a º 21a1 + 15a2 ( mod 35 ) .Từ đó lần lượt cho a1 Î C1 , a2 Î C2
ta tìm được A = {6,19,24,26,31,34 }
Ví dụ 2.7. Chứng minh rằng không tồn tại đa thức P ( x ) ÎZ [ x ] ( deg P ³ 1 ) sao
cho P ( k ) là số nguyên tố với mọi số nguyên dương k .
Giải.
Xét đa thức trên bằng đa thức nhận giá trị nguyên khi x Î Z .deg P = n ( n ³ 1 ) . Ta
chứng minh n ! P ( x ) Î Z [ x ]
n
Thật vậy :
P( x) = å
i=0
n C j f
x - x i
( j ) -1 n- j
f ( x i ) å
= å n
( )
j - 1
j = 0,i ¹ j xi - x j
j = 0
n
n -i
f ( i ) C n i ( -1 )
Þ n!P ( x ) = x ( x - 1)( x - 2 ) ... ( x - n ) å
Î Z [ x ]
i = 0
x -i
Giả sử tồn tại đa thức P ( x ) ÎZ [ x ] ( deg P ³ 1 ) sao cho P ( k ) là số nguyên tố với
mọi số nguyên dương k . .Chon hai số nguyên tố phân biệt p, q, p > q > n thoả mãn
n
12
P ( a ) = p; P ( b ) = q ( a, b Î ¥ * ) . Theo định lý thặng dư Trung Hoa thì tồn tại
c Î ¥* :
ïìc º a ( mod p )
ïìn !P ( c ) º n!P ( a ) º 0 ( mod p )
Þ n! P ( c ) M pq Þ n! M pq vô lí do
Ûí
í
ïîc º b ( mod q )
ïîn !P ( c ) º n!P ( b ) º 0 ( mod q )
p, q ÎÃ, p > q > n Þ ( pq, n !) = 1 còn P ( c ) ÎÃ.
Ví dụ 2.8. Chứng minh rằng phương trình x 2 - 34 y 2 º - 1( mod m ) cos nghiệm với
mọi m Î ¥ * .
Giải.Trường hợp 1
( m,3) = 1 Þ x 2 - 34 y 2 º -1( mod m ) Û ( x - 5 y )( x + 5 y ) º ( 3 y + 1)( 3 y - 1 ) ( mod m )
Tập hợp các số {3 y + 1,3 y - 1 } chạy qua các số không chia hết cho 3
Þ $y0 Î Z : ( 3 y0 + 1)( 3 y0 - 1 ) M m chọn x0 = 5 y0 Þ ( x0 , y0 ) cần tìm.
Trường hợp 2
( m,5) = 1 Þ x 2 - 34 y 2 º -1( mod m ) Û ( x - 3 y )( x + 3 y ) º ( 5 y + 1)( 5 y - 1)( mod m )
Tập hợp các số {5 y + 1,5 y - 1 } chạy qua các số không chia hết cho 5
Þ $y0 Î Z : ( 5 y0 + 1)( 5 y0 - 1 ) M m chọn x0 = 3 y0 Þ ( x0 , y0 ) cần tìm.
Trường hợp 3
( m,3) = ( m,5) ¹ 1
đặt m = m1. m2 với m1 = 3a ( a Î ¥ * ) , m2 Î ¥* : ( m1; m2 ) = 1, ( m1 ,5 ) = 1
+
2
+
2
( 3, m ) = 1 Þ $( x ; y ) Î ( Z ) : x - 34 y º 1( mod m )
( 5, m ) = 1 Þ $( x ; y ) Î ( Z ) : x - 34 y º 1( mod m ) từ đó theo đnh lí
thặng dư Trung Hoa tồn tại ( x, y ) Î ¥ sao cho
ìï x º x ( mod m ) ìï x º x ( mod m )
& í
ta có điều phải chứng minh.
í
y
º
y
mod
m
y
º
y
mod
m
(
)
(
)
ï
îï
î
2
1
1
2
1
2
1
2
1
2
2
2
2
2
1
2
*
1
1
2
2
1
1
2
2
· Ứng dụng 3: Sử dụng hệ thặng dư trong tập con tập số
nguyên dương, bài toán số học chia hết
Ví dụ 3.1.Cho n,k là các số nguyên dương thoả mãn các điều kiện sau:
/ 3 .
1. n M
2. k ³ n .
13
Chứng minh rằng tồn tại số nguyên dương T sao cho TM n & S ( T ) = k (trong đó
S ( x ) là tổng các chữ số của số nguyên dương x trong biểu diễn thập phân )
Lời giải:
Đặt n = 2a.5b.n1 với n 1 Î ¥* , ( n1 ,10 ) = 1& a, b Î ¥ .
/ 3 Û ( n1 ,9 ) = 1 .Tập A = {k,k + 9,k + 9.2,..., k + 9.( n1 - 1)} là HĐĐ
Do n M/ 3 Þ n1 M
mod n1
Þ $t Î {0,1, 2,..., n1 - 1} sao cho k + 9t º 0 ( mod n1 ) .
m
m
Vì ( n1 ,10 ) = 1 Þ $m Î ¥ * sao cho 111...11
1
424
3 M n1 Û 10 - 1M n1 Û 10 º 1( mod n1 ) .
( k -1) m +1
( k - 2 ) m +1
m
( k - t ) m +1
(
)
Xét số T1 = 10
+ 10 42444444
+ L + 10 3 + 10
+2444
L + 10 m +
1
144444
1444
3
k - t -1 m
( k - t ) so
tso
Ta
có
10 º 1( mod n1 ) "i Î ¥ Þ T1 º 10t + k - t º 9t + k ( mod n1 )
im
*
và
S ( T1 ) = t + k - t = k từ đó số T = 10a+b.T1 thoả mãn yêu cầu bài toán.
Ví dụ 3.2 Cho n là số nguyên dương lẻ lớn hơn 1.Các tập hợp số nguyên dương
A = {k Î ¥ * / kn + 1Î cp} và B = { j Î ¥ * / jn Î cp} ( với kí hiệu Î cp là số chính
phương).
ìk ³ n - 2"k Î A
Chứng minh rằng: n ÎÃÛ í
î j ³ n"j Î B
Lời giải:
ìk ³ n - 2"k Î A
Þ n ÎÃÞ í
î j ³ n"j Î B
é x + 1M n
· kn + 1 = x 2 ( x Î ¥* ) Û ( x + 1)( x - 1) = kn Û ê
( do n ÎÃ)
x
1
M
n
ë
Þ x ³ n - 1 vậy kn = ( x + 1)( x - 1) ³ n ( n - 2 ) Û k ³ n - 2 .
· jn = y 2 Þ y 2 M n Þ yM n ( do n ÎÃ) Þ y ³ n vậy jn = y 2 ³ n 2 Û j ³ n
ì k ³ n - 2"k Î A
Ü í
Þ n ÎÃ
î j ³ n"j Î B
Phản chứng .Giả sử n là hợp số Þ n ³ 4
Trường hợp 1: n = p a với p ÎÃ, a Î ¥ * , a > 1
· Nếu a chẵn chọn j = 1 < n mà jn = p a Î cp (vô lí)
2
· Nếu a lẻ a = 2t + 1( t Î ¥ * ) chọn j = p < n mà jn = ( p t +1 ) Î cp (vô lí)
Trường hợp 2: n = pq với p,q Î ¥ * \ {1}, ( p,q ) = 1 .
Ta chứng minh: $ 1 £ k < n - 2 ( k Î ¥ )
14
mà kn + 1Î cp
Xét
p -1
D = {xq + 2} x =0
là HĐĐ mod
p Þ $x Î{0,1,2,..., p - 1}
sao cho
xq + 2 º 0 ( mod p ) Þ xq + 2 = mp với m Î ¥ .
*
Chọn k = mx £ m ( p - 1) < xq £ ( p - 1) q < n - 2
2
Ta có: kn + 1 = mx.n + 1 = mpxq + 1 = xq ( xq + 2 ) + 1 = ( xq + 1) Î cp ( vô lí)
Từ hai trường hợp ta thấy điều giả sử là sai .Vậy n ÎÃ .
Ví dụ 3.3 Cho p ÎÃ,p ³ 3,f ( x ) = ( p - 1) x p -2 + ( p - 2 ) x p-3 + L + 3x 2 + 2x + 1 .
Tập A = {a1 ,a 2 ,...,a p } là HĐĐ mod p .
{
}
Chứng minh rằng tập B = f ( a1 ) ,f ( a 2 ) ,...,f ( a p ) cũng là HĐĐ mod p .
Lời giải:
f ( x ) = ( p - 1) x p- 2 + ( p - 2 ) x p-3 + L + 3x 2 + 2x + 1
Nếu x = 1 Þ f (1) = ( p - 1) + ( p - 2 ) + L + 2 + 1 =
p ( p - 1 )
M p
2
Nếu: x ¹ 1
1
éë( p - 1) ( x p-1 - x p- 2 ) + ( p - 2 ) ( x p- 2 - x p -3 ) + L + 3 ( x 3 - x 2 ) + 2 ( x 2 - x ) + x - 1 ùû
f (x) =
x -1
( x - 1) f ( x ) = ( p - 1) x p-1 - ( x p -2 + x p-3 + L + x 2 + x + 1)
2
( x - 1) f ( x ) = ( p - 1)( x - 1) x
p -1
- ( x p -1 - 1) º 1 - x ( mod p )
Giả sử B không là HĐĐ mod p Þ $a i ,a j Î A (1 £ i < j £ p ) sao cho
f ( a i ) º f ( a j ) º m ( mod p ) khi đó ta có
ìï m ( a i - 1)2 m º 1 - a i ( mod p )
:í
( m Î [0;p - 1])
2
ïî m ( a j - 1) m º 1 - a j ( mod p )
· Nếu m = 0 từ hệ Þ a i º a j ( mod p ) (vô lí)
· Nếu m ¹ 0 do f (1) M p Þ a i ¹ 1,a j ¹ 1 từ hệ suy ra:
2
2
m ( a i - 1) (1 - a j ) º m ( a j - 1) (1 - a i )( mod p )
Û 1 - a i º 1 - a j ( mod p ) Û a i º a j ( mod p ) (vô lí).
Vậy điều giả sử là sai . Vậy tập B cũng là HĐĐ mod p .
Ví dụ 3.4 . Cho số nguyên tố lẻ p = mk + 2 trong đó m,k Î ¥ * , m > 2. Tìm số dư
p
của phép chia của S = Õ ( t m-1 + t m - 2 + L + t + 1) cho p .
t =1
15
Lời giải:
Bổ đề : nếu
A = {a1 ,a 2 ,...,a p } là HĐĐ mod p .
Thì B = {a1m ,a m2 ,...,a m
cũng là HĐĐ mod p .Thật vậy
p }
Giả sử: a im ,a m j Î B sao cho a im º a m j ( mod p ) Þ a ikm º a km
mod p )(*)
j (
· Nếu a i º 0 ( mod p ) Þ a j º 0 ( mod p ) Û a i º a j ( mod p ) Þ i = j
theo
định
lí
Fécma
( a , p ) = 1 Þ ( a ,p ) = 1
a =a
º 1( mod p ) ,a = a
º 1( mod p ) Û a
º a ( mod p )( **)
Từ (*) , (**) Þ a º a ( mod p ) Þ a = a nên B là HĐĐ mod p .
· Nếu
p -1
i
i
j
km +1
i
p -1
j
i
km +1
j
j
i
km +1
i
km +1
j
j
p
p
Áp dụng : S = Õ ( t m-1 + t m - 2 + L + t + 1) = mÕ ( t m -1 + t m- 2 + L + t + 1)
t =1
t = 2
p
p
p
t =2
t = 2
t = 2
S.Õ ( t - 1) = Õ ( t m - 1) Þ S.( p - 1) ! = mÕ ( t m - 1) (1)
Do A = {1,2,...,p} là HĐĐ mod p Þ B = {1m ,2 m ,..., p m } là HĐĐ mod p
Û B* = {1m - 1,2 m - 1,...,p m - 1}
là
p Û B** = {2 m - 1,3m - 1,...,p m - 1} là
HTG
HĐĐ
mod
mod
p.Từ
(1)
p
Þ S.( p - 1) ! = mÕ ( t m - 1) º m ( p - 1) ! ( mod p ) Û S º m ( mod p )
t = 2
Vậy S chia cho p được số dư là m.
Ví dụ 3.5 .Cho các số nguyên không âm : a1 < a 2 < L < a 101 < 5050 .Chứng minh
rằng tồn tại bốn số nguyên phân biệt a k ,a l ,a m ,a n thoả mãn
( a k + a l - a m - a n ) M 5050
Lời giải:
2
Xét các tổng a i + a j (1 £ i < j £ 101) có tất cả C101
= 5050 tổng như vậy.
· Nếu
tồn
tại
2
tổng
a k + a l º a m + a n ( mod 5050 )
với
k < l,m < n,{k,l} ¹ {m,n} thì k,l,m,n phải là 4 số phân biệt .Khi đó bộ 4
số a k ,a l ,a m ,a n thoả mãn điều kiện
( a k + a l - a m - a n ) M 5050 .
· Nếu không tồn tại 4 số k,l,m,n với k < l,m < n,{k,l} ¹ {m,n} sao cho
a k + a l º a m + a n ( mod 5050 ) Þ S = {a i + a j 1 £ i < j £ 101} là HĐĐ mod
5050.
Từ đó å ( a i + a j ) º 0 + 1 + 2 + L + 5049 º 25255049 ( mod 5050 ) Þ
1£ i < j£101
å ( a
1£ i < j£101
i
+ a j ) là một số lẻ (1)
16
Mặt khác
å (a
1£ i < j£101
i
+ a j ) = 100 ( a 1 + a 2 + L + a 100 ) là một số chẵn (2) .
Ta thấy (1) và (2) mâu thuẫn .Vậy điều giả sử là sai và ta có đpcm .
Ví dụ 3.6 .Chứng minh rằng với mọi số nguyên dương n, tồn tại số tự nhiên gồm n
chữ số đều lẻ và nó chia hết cho 5 n .
Lời giải:
Xét số a1a 2 ...a n = 5n .a thoả mãn (với a i ÎZ + lẻ, "i = 1,2,...,n và a Î Z + )
Ta chứng minh bài toán bằng quy nạp toán học .
Với n = 1 Þ $a1 = 5M 51 vậy mệnh đề đúng với n = 1 .
Giả sử mệnh đề đúng với n Û a1a 2 ...a n = 5n .a ,cần chứng minh mệnh đề
đúng với n + 1 .
Xét 5 số sau đây :
· 1a1a 2 ...a n = 5n (1.2n + a )
· 3a1a 2 ...a n = 5n ( 3.2 n + a )
· 5a1a 2 ...a n = 5n ( 5.2 n + a )
· 7a1a 2 ...a n = 5n ( 7.2n + a )
· 9a1a 2 ...a n = 5n ( 9.2 n + a )
Do B = {1,3,5,7,9} là HĐĐ mod 5
Þ B* = {1.2 n + a,3.2 n + a,5.2n + a,7.2 n + a,9.2 n + a} cũng là HĐĐ mod 5 nên tồn
tại một số duy nhất trong B * chia hết cho 5 Þ trong 5 số
1a1a 2 ...a n , 3a1a 2 ...a n , 5a1a 2 ...a n , 7a1a 2 ...a n , 9a1a 2 ...a n ,có một số duy nhất chia hết cho
5n + 1 mà số này gồm n + 1 chữ số lẻ vậy mệnh đề đúng với n + 1 .Theo nguyên lí
quy nạp mệnh đề đúng với mọi n.Vậy với mọi số nguyên dương n, tồn tại số tự
nhiên gồm n chữ số đều lẻ và nó chia hết cho 5 n .
Ví dụ 3.7 Cho p, q Î ¥ * \ {1}, ( p, q ) = 1 .Chứng minh rằng tồn tại k Î Z sao cho ta
n
có số ( pq - 1) k + 1 là hợp số với mọi n Î ¥ *
Giải
ìï k º 1( mod p )
Do ( p, q ) = 1 theo định lí thặng dư Trung Hoa $k Î ¥ * thoả mãn í
ïî k º -1( mod q )
n
n
n
nM 2 Þ ( pq - 1) º 1( mod q ) Þ ( pq - 1) k º -1( mod q ) Û ( pq - 1) k + 1 º 0 ( mod q )
n
n
n
n M 2 Þ ( pq - 1) º -1( mod p ) Þ ( pq - 1) k º -1( mod p ) Û ( pq - 1) k + 1 º 0 ( mod p )
n
n
Do ( p, q ) = 1 Þ ( pq - 1) k + 1 M pq Û ( pq - 1) k + 1 là hợp số với mọi n Î ¥ *
17
Ví dụ 3.8. Chứng minh rằng với mọi n Î ¥ * tồn tại n số tự nhiên liên tiếp sao cho
bất kì số nào trong các số ấy cũng đều không phải là luỹ thừa (với số mũ nguyên
dương) của số nguyên tố.
Giải: Cách 1. Mỗi n Î ¥ * xét n số nguyên tố phân biệt p1 , p2 ,..., p n
ì x º p1 - 1( mod p 1 2 )
ï
2
ï x º p2 - 1( mod p 2 )
Xét hệ phương trình í
Theo định lý thặng dư Trung Hoa thì hệ
...............................
ï
ï x º p - 1 mod p 2
(
n
n )
î
phương trình trên có nghiệm Û $a Î Z : a º pi - 1( mod pi 2 ) "i = 1, n . Từ đó suy ra
các số a + 1, a + 2,..., a + n đều không phải là luỹ thừa với số mũ nguyên dương của
một số nguyên tố.
Cách 2. Mỗi n Î ¥ * xét 2n số nguyên tố phân biệt p1 , p2 ,..., pn , q1 , q2 ,..., q n
ì x º -1( mod p1q 1 )
ï
ï x º -2 ( mod p2 q 2 )
Xét hệ phương trình í
Theo định lý thặng dư Trung Hoa thì hệ
...............................
ï
ï x º -n ( mod p q )
n n
î
phương trình trên có nghiệm Û $a Î Z : a º -i ( mod pi qi ) "i = 1, n . Từ đó suy ra
các số a + 1, a + 2,..., a + n đều không phải là luỹ thừa với số mũ nguyên dương của
một số nguyên tố.
Ví dụ 3.9. (Shortlisted IMO 1998)Xác định tất cả n Î ¥ * sao cho với n này tồn tại
m ÎZ sao cho: 2 n - 1| m 2 + 9 .
Giải. Ta chứng minh 2 n - 1| m 2 + 9 Û n = 2 s ( s Î ¥ * )
Điều kiện cần .
Đặt n = 2 s t ( s Î ¥ , t Î ¥ * , ( t ,2 ) = 1 ) .Nếu t ³ 3 Þ 2t - 1| 2n - 1 Þ 2t - 1| m 2 + 9 .
Ta có 2t - 1 º -1( mod 4 ) Þ $p ÎÃ: p º -1( mod 4 ) , p | 2t - 1( p ¹ 3 ) Þ p | m 2 + 9
2
2
Û p | m + 3 theo định lý Fecma 1 º m
p -1
º (m
2
)
p -1
2
º ( -9 )
p -1
2
º - 1( mod p ) vô lí
điều này không xẩy ra nếu tồn tại t Þ p = 3 mâu thuẫn ,Nên 2t º -1 º 1( mod p )
vậy n = 2 s ( s Î ¥ * )
Điều kiện đủ.
2 n - 1 = 22 - 1 = ( 2 - 1)( 2 + 1) ( 22 + 1) 2 2 + 1 ... 2 2 + 1 từ đó suy ra
(
s
t
2
) (
)
s -1
(
a
b
)
Þ 2 n - 1| m 2 + 9 Þ 2 2 + 1| m 2 + 9"t = 1, s - 1 . Mà 22 + 1;2 2 + 1 = 1( a ¹ b )
18
t
(
t
)
Theo Định lí thặng dư Trung Hoa hệ phương trình x º 2 2 mod 22 + 1 "t = 0, s - 2
có nghiệm nên tồn tại
c Î Z : c º 2 2 mod 22 + 1 Þ c 2 + 1 º 0 mod 2 2 + 1 "t = 0, s - 2 từ đây suy ra
(
t
)
t +1
(
)
t +1
2 n - 1| 9 ( c 2 + 1) = m 2 + 9 trong đó m = 3 c
Ví dụ 3.10.(Shortlisted IMO 2001) Cho số nguyên dương a chỉ có ước nguyên tố
dạng 4 k + 1 ( k Î ¥ * ) . Chứng minh rằng tồn tại b Î ¥ * sao cho b 2 + 1 M a 4 + a 2 .
Giải. Bổ đề; cho p ÎÃ, p = 4 k + 1 Þ $x Î ¥ * : x 2 + 1 M p n ( n Î ¥ * cho trước) Quy nạp
n = 1 chọn x = ( 2k ) ! thoả mãn bổ đề
Giả sử bổ đề đúng với n = h Î ¥* Û $xh : xh2 + 1M p h Û xh 2 + 1 = up h ( u Î ¥ * )
2
Đặt xh+1 = xh + tp h Þ xh2+1 + 1 = ( xh + tp h ) + 1 = p h ( u + 2 xh t ) + p 2 ht 2 M p h +1
Ta cần chọn t Î ¥ : u + 2 xh t M p
x
s
Áp dụng a 2 = Õ pha ( ph º 1( mod 4 ) ) Þ a 2 + 1 = å pha ( ph º 1( mod 4 ) )
h
h
h =1
h =1
s
a 2 ( a 2 + 1 ) = å pk a
k
k =1
"h = 1,2,..., s Þ $bh Î Z : bh 2 + 1 M p h (theo bổ đề ) , b02 + 1M 2 ( b0 Î Z )
ìï x º b0 ( mod p h a
Xét hệ í
a
ïî x º bs ( mod ps
h
s
)
theo định lí thặng dư Trung Hoa thì hệ có nghiệm
)
s
x = b Î Z : b + 1 MÕ ph a
2
h
h =1
·
Ứng dụng 4: Sử dụng hệ thặng dư trong phương trình
Đi Ô Phăng bậc nhất.
Ví dụ 4.1:Cho a,b Î Z + , ( a,b ) = 1. Số nguyên dương n được gọi là đẹp nếu tồn tại
x, y Î Z + ,
sao cho : n = ax + by .
1. Chứng minh rằng : n = ab là số xấu lớn nhất.
2. Chứng minh rằng nếu n Î I = [ a + b;ab ] ,n là đẹp Û số ab + a + b - n là xấu
3. Tìm số lượng các số xấu .
Lời giải:
1/Ta chứng minh n = ab là số xấu lớn nhất.
19
· Giả sử n = ab đẹp Û phương trình ab = ax + by (*) có nghiệm nguyên
dương
ìax M b
ì x M b ì x = bx 1
Þí
do ( a,b ) = 1) Þ í
Þí
x1 , y 1 Î Z + ) khi đó phương trình (*)
(
(
îbyMa
î yMa î y = ay1
Û ab ( x1 + y1 ) = ab Û x1 + y1 = 1 Vô lí .Vậy điều giả sử sai tức là n = ab là số xấu.
· Ta chứng minh mọi n > ab thì thì phương trình n = ax + by có nghiệm
nguyên dương .
b
Do ( a,b ) = 1 Þ A = {ai} i =1 là HĐĐ mod b Þ $x Î {1, 2,..., b} sao cho
ax º n ( mod b ) Û n - ax = by ( y Î Z ) Û ax + by = n
do1 £ x £ b Þ n - ax ³ n - ab > 0 Þ by > 0 Þ y Î Z + vậytồntại
x, y Î Z + : ax + by = n Û "n > ab đều là số đẹp.
Từ hai điều trên ta thấy n = ab là số xấu lớn nhất.
2/ Þ n là đẹp $x, y Î Z + : ax + by = n .
Khi đó ab + a + b - n = ab + a + b - ( ax + by ) = ab - ( x - 1) a - ( y - 1) b (**)
Giả sử ab + a + b - n là số đẹp $x 1 , y1 Î Z + : ab + a + b - n = ax1 + by1
(***) từ
(**)
và
(***)
ta
có
ab = ( x + x1 - 1) a + ( y + y1 - 1) b
mà
x + x1 - 1 Î Z + , y + y1 - 1Î Z + Þ n = ab đẹp vô lí.
Ü
đặt
k = ab + a + b - n .Do
b
( a,b ) = 1 Þ A = {ai}
i =1
làHĐĐmodb
Þ $x Î {1, 2,..., b} saocho
ax º k ( mod b ) Û k - ax º 0 ( mod b ) Û k - ax = by Û ax + by = k ( y Î Z ) .Theo
giả thiết k là số xấu Þ k £ ab Þ y £ 0 .Khi đó ta có:
n = ab + a + b - k = ab + a + b - ( ax + by ) = a ( b + 1 - x ) + b (1 - y ) đẹpdo
b + 1 - x ÎZ + , 1 - y ÎZ + .
3/ Theo phần (1) mọi n > ab đều là số đẹp.
· "n Î [1;a + b - 1] đều là số xấu ,trong đoạn này có tất cả a + b - 1 số xấu
· "n Î [ a + b;ab ] thì ab + a + b - n Î [ a + b;ab ] theo phần (2) ta thấy nếu lấy
một số đẹp thuộc đoạn [ a + b;ab ] thì có một số xấu cũng thuộc đoạn
ab - a - b + 1
.
[a + b;ab ] ,từ đó số số xấu trong đoạn [a + b;ab ] là:
2
ab - a - b + 1 ab + a + b - 1
Vậy tổng cộng có tất cả : a + b - 1 +
=
số số xấu.
2
2
Ví dụ 4.2: Cho a,b,c Î Z + , ( a,b ) = ( b,c ) = ( c,a ) = 1. Số nguyên dương n được gọi là
đẹp nếu tồn tại x, y,z ÎZ + , sao cho : n = bcx + cay + abz .
20