Đăng ký Đăng nhập
Trang chủ Giáo án - Bài giảng Sáng kiến kinh nghiệm Skkn sử dụng hệ thặng dư đầy đủ, thặng dư thu gọn, thặng dư trung hoa để giải to...

Tài liệu Skkn 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

.PDF
27
1066
94

Mô tả:

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ÁN­TIN  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 )  {5 y + 1,5 y - 1 } chạy  qua  các  số  không  chia  + 1)( 5 y - 1 ) M m chọn  x = 3 y Þ ( x , y )  cần tìm.  Tập  hợp  các  số Þ $y0 Î Z : ( 5 y0 Trường hợp 3 ( m,3) = ( m,5) ¹ 1  0  0 0  0 hết  cho  5 0  đặ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
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng