Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Toán học Chuyên đề môn toán bài tập củng cố một sô nội dung cơ bản của lý thuyết đồng dư...

Tài liệu Chuyên đề môn toán bài tập củng cố một sô nội dung cơ bản của lý thuyết đồng dư

.PDF
15
1320
142

Mô tả:

CHUYÊN ĐỀ SỐ HỌC BÀI TẬP CỦNG CỐ MỘT SỐ NỘI DUNG CƠ BẢN CỦA LÝ THUYẾT ĐỒNG DƯ I. Bài tập sử dụng Định lý Thặng dư Trung Hoa Bài 1 Cho A là một tập con khác rỗng của Z +. Chứng minh rằng tồn tại số nguyên dương n sao cho tập hợp nA = { nx / x  A} chứa toàn lũy thừa của một số tự nhiên với số mũ lớn hơn 1.  Lời giải: Đặt A = {a1, a2,...., ak} và p 1, p2,..., p k là k số nguyên tố phân biệt. Theo định lý Thặng dư Trung Hoa, với mọi i = 1,2,..,k tồn tại số nguyên dương mi thỏa mãn mi  -1 ( mod p i) ; mi  0 ( mod p j) ( i  j, j = 1,2,....,k) Khi đó: m1 + 1 p1 m2 p1 ....... mk p1 m1 p2 m2 + 1 p2 ....... mk p2 m2 pk ....... mk + 1 pk ..... m1 pk Đến đây, ta đặt: n = a1m1 . a2 m2 . a3m3 ...... a k mk Ta có: mk m1 1 m2 p m  1 m m m na1 = a1 1 . a 2 2 . a3 3 ...... a k k = ( a1 p a2 p ..... ak p ) 1 1 1 1 m m 1 m k p 1 2 na2 = a1m1 . a 2 m2 1 . a3m3 ...... a k mk = ( a1 p a2 p ..... ak p ) 2 2 2 2 ...... mk 1 m1 m2 p m m m  1 m 1 2 3 k a a a a a a a nak = 1 . 2 . 3 ...... k = ( 1 p 2 p ..... k p ) k k k k  ĐPCM. Bài 2 Với mọi tập số nguyên {a 1, a2, a3...., an } tồn tại số nguyên dương b để tập { ba1, ba2, ba3...., ban } bao gồm những lũy thừa đúng của một số nguyên.  Lời giải: Đặt p1, p2, p3,....., pn là các số nguyên tố có mặt trong phép phân tích a1, a2,...., an thành thừa số nguyên tố. Ta có: ai = p1bi1. p2bi2.....pkbik. Ta biết rằng nếu một số nguyên được phân tích thành thừa số nguyên tố p1c1 .... pmcm là một lũy thừa bậc q khi và chỉ khi c 1, c 2,...., c n chia hết cho q. Đặt b = p1d1 . p 2 d 2 . p3d 3 ..... p k d k . Ta sẽ chứng minh có thể tìm được d 1, d2,...., dk mà b thỏa mãn điều kiện đề bài. Để có ba1 là lũy thừa bậc q 1 của một số nguyên thì b 11 + d1, b12 + d2,..., b1k + dk chia hết cho q 1. Tương tự với ba2, ba3,...., ban, ta có: + b21 + d1, b22 + d2,..., b2k + dk chia hết cho q 2 ....... + bn1 + d1, bn2 + d2,..., bnk + dk chia hết cho q n. Từ đó phải xác định d 1, d2,...., dk thoản mãn d 1  - bi1 (mod q i); i = 1,2,..,n. Tương tự với d 2, d3,..., dk. Ta chọn q 1, q2,...., qn là những số nguyên tố phân biệt. Áp dụng định lý Thặng dư Trung Hoa, tồn tại d 1, d2,..., dk. Từ đó tồn tại b (ĐPCM). Bài 3 Chứng minh rằng với mọi số nguyên n, tồn tại một tập số nguyên n phần tử để tổng các phần tử các tập con không rỗng của nó là một lũy thừa.  Lời giải: Ta xét tập số nguyên S = { x1, x2,...., xn }, tập S có 2n – 1 tập con không rỗng của S. Đặt: S 1, S2, S3,...., S n 2 1 Là tổng các phần tử của các tập này. Áp dụng bài tập 7, tồn tại số nguyên b thỏa mãn: { bS1, bS2, bS3,...., bS n } 2 1 Bao gồm toàn các lũy thừa. Từ đó ta chọn tập: F = { bx1, bx2, bx3,...., bxn } thì tập F thỏa mãn điều kiện đề bài. Bài 4 Cho m là một số nguyên dương. Tìm số lượng nghiệm của phương trình x2  x ( mod m).  Lời giải: Giải sử m = p1a1 . p 2 a 2 . p3a3 ...... pk ak . Ta có: x2  x ( mod m). Từ đó x2  x ( mod pi ai ) với i = 1,2,3,..,k. ( pi ai , p a j ) = 1 j với i  j, i,j  {1,2,..,n} hay x(x-1)  0 ( mod pi ai ) với i  {1,2,..,n}. Vậy phương trình x(x-1)  0 ( mod pi ai ) có 2 nghiệm là x  0 ( mod pi ai ) và x  1 ( mod pi ai ). Áp dụng định lý Thặng dư Trung Hoa, hệ x  ri ( mod pi ai ), i  {1,2,..,n} với ri  {0,1} chỉ có 1 nghiệm mod m nhưng lại có 2k cách chọn hệ. Vì vậy, phương trình có 2k nghiệm. Bài 5 Cho n là số nguyên dương lẻ và n > 3. Gọi k, t là các số nguyên dương nhỏ nhất sao cho kn + 1 và tn đều là số chính phương. Chứng minh n là số nguyên tố khi và chỉ khi:  min {k,t} > n 4 Lời giải: 1. Điều kiện cần: Giả sử n là số nguyên tố, khi đó: n|tn và tn là chính phương nên n2|tn  n|t. Từ đó: t  n> n 4 Hơn nữa, đặt: a2 = kn + 1 thì a2  1 (mod n). Kết hợp n nguyên tố nên a   1(mod n) Nhưng vì a > 1 nên a  n – 1 ( với n – 1 là số nhỏ nhất đồng dư với 1 mod n). Dẫn đến: kn + 1  (n – 1)2  k  n – 2  k > n , 4 vì n > 3 nên n – 2 > n 3 2. Điều kiện đủ:  Nếu n chỉ có một ước số nguyên tố duy nhất, đặt n = p  với p  3 do n lẻ. nếu  n 4 thì tn = p  là số chính phương, mâu thuẫn với giải thiết. Nếu  lẻ,   3, ta lấy: t = p < n p = thì tn = p  1 ,  + 1 chẵn nên tn là số chính phương với 4 4 chẵn, ta lấy t = 1 < t< n , 4 mâu thuẫn. Vậy  = 1 hay n là số nguyên tố.  Nếu n có ít nhất 2 ước nguyên tố phân biệt. Khi đó ta có thể viết n dưới dạng n = p  .m, trong đó p là một số nguyên tố lẻ, m là số nguyên dương lẻ, (m,p) = 1. Theo định lý Thặng dư Trung Hoa, tồn tại số nguyên s sao cho: s  1 ( mod p  ) s  -1 (mod m) n 2 Từ đó: n|s 2 – 1. Hơn nữa ta có thể chọn s sao cho: s  . Vì s không đồng dư với 1 mod m nên s  1 và s không đồng dư với -1 mod p  nên s  -1. Dẫn đến s 2  -1, từ đây lấy: k = s 2 1 thì k là số nguyên dương, hơn nữa n n2 n s 2 1 s2 kn + 1 = s 2 là số chính phương và k = <  4 = . 4 n n n Mâu thuẫn với điều kiện: min {k,t} > n . 4 Vậy trường hợp này không thể xảy ra. Vậy n là số nguyên tố. II. Bài tập Phương trình đồng dư Bài 6 : Cho p là số nguyên tố lẻ và k | p – 1. Khi đó phương trình xk – 1 = 0 (mod p) có đúng k nghiệm phân biệt.  Lời giải: Vì k | p – 1 nên dễ thấy xp-1 – 1 = (xk – 1)Q(x). Trong đó Q(x) là đa thức hệ số nguyên với deg Q = p – 1 – k. Gọi A  S  1, 2,..., p  1; B  S tương ứng là nghiệm của 2 phương trình : x p1  1 (mod p) và Q( x)  0 (mod p ) Thì ta có A  B  S | A |  | B | p  1 mà | A | k ; | B | p  1  k nên | A |  | B | k . Vậy xk – 1 = 0 (mod p) có đúng k nghiệm phân biệt. Bài 7 : Chứng minh rằng nếu p là 1 số nguyên tố thì C pk 1  (1) k (mod p) 1  k  p  1 .  Lời giải: Xét đa thức f ( x)  x  1 p1  x p 1 . x 1 Dễ thấy bậc của f (x ) không quá p  2 . (1) Mặt khác theo định lí Fermat nhỏ thì: x  1p1  1 (mod p) x p  x  x 1 x  x (mod p)   1 (mod p ) x 1 p Do đó phương trình f ( x)  0 (mod p) có p  1 nghiệm mod p là 0, 1, 2, …, p – 2. (2) Từ (1) và (2) suy ra mọi hệ số của f (x) đều chia hết cho p. Vậy C pk 1  (1) k (mod p) 1  k  p  1 . Bài 8 : Chứng minh rằng nếu p là 1 số nguyên tố thì : C pk Mp, k  1, p 1  Lời giải: p 1 Đặt f ( x)   C pk x k   x  1   x p  1 . p k 1 Theo định lý Fermat nhỏ :  x  1  x  1  x p  1(mo d p), x ¢ . p Do đó phương trình f ( x)  0 (mo d p) có p nghiệm. Mà deg f  p  1 nên mọi hệ số của f ( x) đều chia hết cho p (đpcm). Bài 9: Cho n là số tự nhiên, p là số nguyên tố, n  p. Chứng minh rằng n Cnp    (mod p) ,trong đó  x   p  là kí hiệu phần nguyên của x. Lời giải: Xét dãy n, n  1,..., n  p  1 . Dãy gồm p số tự nhiên liên tiếp nên có đúng một số của dãy chia hết cho p, giả sử số đó là N.Ta có N n  . p  p  Loại số N ra khỏi dãy và xét đồng dư modulo p, ta được dãy 1, 2,..., ( p  1) (mod p) (xếp theo thứ tự nào đó). Gọi Q là tích các số của dãy ( sau khi loại bỏ N). Ta có Q n(n  1)...(n  p  1)  ( p  1)! N Suy ra (mod p). NQ  ( p  1)! N (mod pN) QN N  ( p  1)! (mod p) p p (1) Vì (p, ( p  1)!)  1 nên ta được NQ N (mod p)  p! p (2) n Vậy Cnp    (mod p). p   Bài 10 : Xét các số tự nhiên m, n, k thoả mãn m n n m , n k k n . Chứng minh rằng m k k m .  Lời giải: Từ giả thiết suy ra m n  anm , n k  bk n . Ta có (m k ) n  m n   anm   a k n k   a k b m k m  k k m n Suy ra m k  k m  . n n Vậy m k k m . Bài 11: cho p là số nguyên tố lẻ. chứng minh rằng với mọi n )(*) có đúng p-1 nghiệm phân biệt. -1 0 (mod  1 phương trình Lời giải: Chứng minh bằng quy nạp theo n. với n=1 khẳng định đúng. Giả sử khẳng định đúng với n. xét phương trình -1 Giả sử { Ta có: (mod ) (1) } là p-1 nghiệm của (1). -1 = . Với mỗi i tồn tại duy nhất Thỏa mãn: (p-1) (mod p) vì (p-1) {1,2,…,p} không chia hết cho p Đặt Ta có: -1 +(p-1) Ta có : Do vậy là nghiệm của (*). (mod ) Đảo lại: Nếu => (mod ) => i=j. Vậy phương trình có ít nhất 9 nghiệm. Giả sừ b là nghiệm bất kì của (*). Khi đó b cũng là nghiệm của (1). Vậy tồn tại b= . Ta có  (p-1) t Vậy t 1= chia hết cho p (mod p) => t =  b , t để (mod +pl => b= ) vậy phương trình (*) có đúng p-1 nghiệm là . III. Hệ thặng dư Bài 11: Cho a, b là các số nguyên Dương nguyên tố cùng nhau Số nguyên dương n được gọi là số đẹp nếu tồn tại x,y sao cho nếu không tồn tại nguyên dương sao cho CMR 1. là số xấu lớn nhất. 2.CMR nếu . Số nguyên dương được gọi là số xấu . thì là số đẹp khi và chỉ khi khi là số xấu.  Lời giải: Ta chứng minh Giả sử là số xấu lớn nhất. là số đẹp, hay phương trình ⇒ có nghiệm nguyên dương (do ⇒ ( Khi đó phương trình (1) tương đương với Vậy điều gỉa sử sai, tức Ta chứng minh mọi vô lí. là số xấu. thì phương trình có nghiệm nguyên dương. Do là HĐĐ mod nên suy ra tồn tại sao cho . là số nguyên dương Do Vậy tồn tại nguyên dương sao cho Do đó, là số xấu lớn nhất. 2, Giả sử là số đẹp, khi đó tồn tại đều là số đẹp. sao cho . Khi đó Giả sử là số đẹp, khi đó tồn tại nguyên dương sao cho mà nguyên Từ (2) và (3) ta có dương nên là số đẹp, mâu thuẫn với câu 1). Vậy là số xấu. Ngược lại, đặt Suy . Do ra tồn là HĐĐ nên tại sao . cho Theo giả thiết k là số xấu, suy ra Do . Khi đó ta có và nguyên dương nên n là số đẹp Bài 12: Cho số nguyên dương n và số nguyên tố p lớn hơn n+1. Chứng minh rằng đa thức không có nghiệm nguyên.  Lời giải: trong đó các hệ số Ta có có dạng Từ nhất gồm suy ra tập sao cho không chia hết cho là HĐĐ mod , hơn nữa thừa số, nên tồn tại duy suy ra Tương ứng với số trong đó có hệ số còn lại đều chia hết cho Giả sử Theo Suy PT có đồng thời hệ số nhưng không chia hết cho nghiệm nguyên Khi đó thì ra không mà và với không chia hết cho chia hết Vì Vậy điều giả sử là sai, tức là PT cho nên không có nghiệm nguyên, hay nên , mâu thuẫn không có nghiệm nguyên. (đpcm) Bài 13: Cho dãy số minh rằng dãy số được xác định bởi với Chứng chứa vô hạn số nguyên chia hết cho 7.  Lời giải: Giả sử chỉ có hữu hạn số trong dãy chia hết cho 7 và là số cuối cùng của dãy chia hết cho 7. Từ công thức xác định của dãy ta có Do nên Mặt khác Do nên tập số hơn là HĐĐ mod 7, suy ra trong bảy tồn tại một số chia hết cho 7 mà số này lại lớn . Điều này mâu thuẫn với giả sử sử sai nên ta có đpcm. là số cuối cùng trong dãy chia hết cho 7. Do giả Bài 14: Cho các số nguyên không âm tại bốn số nguyên phân biệt Chứng minh rằng tồn thỏa mãn  Lời giải: Xét các tổng có tất cả Giả sử không tồn tại bốn số tổng như vậy. với sao cho là HĐĐ mod 5050. Từ đó thì là một số lẻ (1) Mặt khác là một số chẵn (2) Ta thấy (1) và (2) mâu thuẫn. Vậy tồn tại hai tổng lúc đó sao cho bốn số phân biệt và bốn số với và thỏa mãn phải là . Bài 15: Cho m là một số nguyên dương. Tìm số nghiệm của phương trình: x2  x (mod m).  Lời giải: Giả sử m  p1 p2 ... pk . Ta có: x2  x (mod m) 1 2 k  x2  x (mod pii ) i  1,2,..., k Hay x( x  1)  0 (mod pi ) i  1,2,..., k i Vì ( x; x  1)  1 nên phương trình x( x  1)  0 (mod pi ) có 2 nghiệm mod pi là: i i x  0 (mod pii ) hoặc x  1 (mod pii ). Theo Định lý Thặng dư Trung hoa: Với mỗi bộ r1 , r2 ,..., rk  thì phương trình: x  ri (mod pii ) i  1,2,..., k luôn có một nghiệm duy nhất mod m Do mỗi phương trình x( x  1)  0 (mod pi ) đều có hai nghiệm mod pi nên phương trình i đã cho có 2 k nghiệm. i Bài 16: Chứng minh rằng : với mọi số nguyên dương n , tồn tại số tự nhiên n gồm n chữ số đều lẻ và nó chia hết cho 5n.  Lời giải: Xét số Xn = a1 a2 a3… an = dương i + lẻ với mọi i=1,2,3,,,n và a nguyên Ta sẽ chứng minh bài toán bằng quy nạp : với n=1 thì a1 =5 Gỉa sử mệnh đề đứng với n . Cần chứng minh mệnh đề đúng với n+1 Xét 5 số sau đây: a1 = 1a1 a2 a3… an = a2=3a1 a2 a3… an = a3= 5 a1 a2a3… an = a4= 7a1 a2 a3… an = a5= 9a1 a2 a3… an = Do B= là HĐĐ mod 5 nên : C= cũng là HĐĐ mod 5 nên tồn tại một số trong hệ chia hết cho 5. Trong 5 số a1,a2,a3,a4,a5 có duy nhất một số trong C chia hết cho 5(n+1) mà số này gồm (n+1) chữ số lẻ . Do đó mệnh đề đúng với n+1.điều giả sử đú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 n gồm n chữ số đều lẻ và nó chia hết cho 5n. IV. Định lý Fermat nhỏ Bài 17 Tìm tất cả các số tự nhiên m sao cho nếu m n  1 ( mod n) với n là số nguyên dương tùy ý thì m  1( mod n).  Lời giải: +) Giả sử m  2. Khi đó ta có: m( m1)  1  (m  1) 2 ( m1)2  1 ( mod (m  1) 2 ) Mặt khác m 1 không chia hết cho (m  1) 2 với m  2 . Do đó mọi giá trị m  2 không thỏa mãn đề bài. +) m  1 thỏa mãn. +) m  2 ta có: 2n  1 ( mod n) n  1 Giả sử p là ước nguyên tố nhỏ nhất của n, khi đó: 2n  1 ( mod p) => p lẻ. Ta có (n; p  1)  1 . Khi đó a, b  Z sao cho an  b( p  1)  1 Theo định lí Fermat nhỏ ta có: 21  2na.2b ( p1)  1 (mod p) ( mâu thuẫn) Mâu thuẫn này chứng tỏ rằng giả thiết m n  1 ( mod n) không bao giờ xảy ra. Vậy ta có mệnh đề m n  1 ( mod n) => m  1( mod n) đúng khi và chỉ khi m=1 hoặc m=2 Bài 18 Cho p là số nguyên tố lẻ. Đặt m  9 p 1 . CMR: m là một hợp số lẻ, không chia hết 8 cho 3 và 3m1  1 ( mod m)  Lời giải: Ta có: 9 p 1 3p 1 3p 1 m  . 8 2 4 Dễ thấy 3p 1 3p 1 và đều là số nguyên dương lớn hơn 1 nên m là hợp số. 2 4 Mặt khác m 9 p 1  9 p 1  9 p  2  ...  9  1 => m  1 ( mod 3) hay m không chia hết cho 3. 8 Ta thấy 9 k có tận cùng là 9 với k lẻ, có tận cùng là 1 nếu k chẵn m  9 p 1  9 p 2  ...  9  1  (9 p 1  9 p 2 )  (9 p 3  9 p 4 )  ....  (92  9)  1 Do p lẻ => m có tận cùng bằng 1=> m lẻ. Theo định lí Fermat nhỏ: 9 p1  1 ( mod p) => 9 p  9Mp mà 9 p  9M8, (8; p)  1 Do đó 9 p  9M8 p hay m  1  9p  9 Mp 8 Do m lẻ => m-1 chẵn => m 1M2 p => 3m1  1M32 p  1 => 3m1  1Mm ( do 32 p  1  8m ) hay 3m1  1 ( mod m) Bài 19 Tìm các số nguyên tố p, q thỏa mãn  7 x  5x  7 y  5 y   7 p  5 p  7q  5q  chia hết cho pq.  Lời giải: Bổ đề: (quen Cho  7 x  5x  ⋮p, thuộc) 7 y  5 y  ⋮p với x nhỏ nhất thì y⋮x Áp dụng: Ta thấy p,q≠5,7 TH1:  7 p  5 p  ⋮p theo Fermat nhỏ thì  7 p1  5 p1  ⋮p   7 p  5 p1.7 Mp  2.5 p1 Mp  2Mp  p2 7 2  52  7 q  5q  2 q  12  7  5q M q  2.5 p1 Mp  2Mp  p  2 M q  12.2.5 p1 M q  12.2M q  q  2;3 Khi ấy: 7 2  52  7 q  5q  2 q  12  7  5q M q M q  12.2.5 p1 M q  12.2M q  q  2;3 TH2: Nếu  7q  5q  ⋮q thì 7 p  5p   cm ⇒ 7 q  5q ⋮p p tương như  7 p  5 p  ⋮p tự q⇒  7 p  5 p  ⋮q Nếu  7q  5q   vậy  7 p  5 p  ⋮q và  7q  5q  ⋮p Như Gọi  7k  5k  ⋮q với k đạt GTNN khi ấy theo bổ đề thì p⋮k nên mà p nguyên tố nên k=1,p Khi k=1⇒2⋮q⇒q=2 và dễ tìm ra p Khi k=p⇒  7 p  5 p  ⋮q với p là số nhỏ nhất thỏa đề, khi đó dẫn đến vô lý vì vẫn còn số nhỏ hơn thỏa là  7q1  5q1  ⋮q (theo mãn Fermat nhỏ) nên vô lý Do đó trường hợp này có nghiệm giống TH1 Vậy (p,q)=(2,3),(3,2),(2,2). Bài 20 Giả sử m, p là các số nguyên tố khác nhau. CMR nếu với số tự nhiên nào đó, p là ước của số x m1  x m2  ...  1 thì ta có p  1 ( mod m)  Lời giải: Giả sử p  mk  r , 1  r  m 1 . Ta có: x m 1  x m  2  ...  1 Mp => x m  1 ( mod p) (1) => x không chia hết cho p. Ta chứng minh: x r 1  1 ( mod p) (2). +) Nếu p  m thì (2) đúng do Fermat Giả sử p  m . Nâng cả 2 vế của (1) lên lũy thừa k  x pr  1 p 1 m ta được: ( mod p) Theo Fermat nhỏ: x p 1  1 ( mod p) => x p  r ( x r1  1)  0 ( mod p) => x r 1  1 ( mod p) Cần chứng minh r  1 . Giả sử r  1 . Khi đó (m; r  1)  1 . Ta có: ( x m1  1; x r 1  1)  x ( x;r 1)  1  x  1 Từ (1) và (2)=> x m  1Mp, x r 1  1Mp => x  1Mp => x  1 ( mod p) => P ( x)  m ( mod p) ( trái với giả thiết P( x)Mp ) Do đó r  1  p  1 ( mod m). ( đpcm)
- Xem thêm -

Tài liệu liên quan