Định Lý Phần Dư Trung Hoa Và Các ứng Dụng Trong Giải Toán Số Học

• Trang chủ
• Toán
• Đề thi thử THPT quốc gia môn Toán

Định lý phần dư Trung Hoa và các ứng dụng trong giải toán số học - Đặng Đình Sơn

Gửi bởi: Phạm Thọ Thái Dương 20 tháng 7 2020 lúc 14:37:55 | Update: 11 tháng 12 lúc 18:45:11 Kiểu file: PDF | Lượt xem: 789 | Lượt Download: 10 | File size: 0.672931 Mb

Nội dung tài liệu

Tải xuống Link tài liệu: Copy Đã copy link!

Các tài liệu liên quan

Có thể bạn quan tâm

Thông tin tài liệu

Đặng Đình Sơn Ứng dụng định lí Phần dư Trung Hoa giải các bài toán số học 1. ĐỊNH LÍ PHẦN DƯ TRUNG HOA Định lí: Cho n số nguyên dương m1 , m2 ,..., mn số nguyên dương đôi một nguyên tố cùng nhau. Khi đó hệ đồng dư tuyến tính  x  ai (mod mi )  i  1, n có nghiệm duy nhất mođun M  m1m2 ...mn . Chứng minh: Đặt M i  M  (M i , mi )  1, i  1, n và M i  m j , i  j. mi Suy ra i  1, n , tồn tại số nguyên yi thoả mãn M i yi  ai (mod mi ) . n  x  ai (mod mi ) Xét x   M i yi ta có:  . i 1 i  1, n  x  ai (mod mi )  x  x(mod mi ) Do đó:    x  x(mod M ) i  1, n i  1, n Vậy định lí được chứng minh. Nhận xét: Định lí phần dư Trung Hoa khẳng định về sự tồn tại duy nhất của một lớp thặng dư các số nguyên thoả mãn đồng thời nhiều đồng dư tuyến tính. Do đó có thể sử dụng định lí để giải quyết những bài toán về sự tồn tại và đếm số các số nguyên thoả mãn một hệ các điều kiện quan hệ đồng dư, chia hết…, hay đếm số nghiệm của phương trình đồng dư. Việc sử dụng hợp lí các bộ m1 , m2 ,..., mn và bộ a1 , a2 ,..., an (trong định lí) cho ta nhiều kết quả rất thú vị và từ đó có thể đưa ra nhiều bài tập hay và khó. Sau đây là một số ứng dụng của định lí phần dư Trung Hoa giải các bài toán số học. 1 Đặng Đình Sơn Ứng dụng định lí Phần dư Trung Hoa giải các bài toán số học 2. MỘT SỐ ỨNG DỤNG Bài toán 1. Cho hai số nguyên dương p, q nguyên tố cùng nhau. Chứng minh rằng tồn tại số nguyên k sao cho ( pq  1)n k  1 là hợp số với mọi số nguyên dương n. Lời giải: Vì (p,q)=1 nên theo định lí phần dư Trung Hoa, tồn tại số nguyên k thoả mãn:  k  1(mod p )   k  1(mod q ) Khi đó: + Nếu n chẵn thì ( pq  1) n  1(mod q )  ( pq  1)n k  1(mod q )  ( pq  1) n k  1 q + Nếu n lẻ thì ( pq  1) n  1(mod p )  ( pq  1) n k  1(mod p )  ( pq  1) n k  1 p Vậy ( pq  1)n k  1 là hợp số với mọi số nguyên dương n. Nhận xét: Chứng minh trên thật gọn gàng nhờ vào việc sử dụng định lí đồng dư Trung Hoa. Mấu chốt của vấn đề ở đây là chúng ta phải thấy rằng để ( pq  1) n k  1 là hợp số ta cần chỉ ra ( pq  1) n k  1 chia hết cho p hoặc q, khi phân  k  1(mod p ) .  k  1(mod q ) tích tính chẵn lẻ của n ta dễ dàng thấy được sự xuất hiện của hệ  Bài toán 2. Chứng minh rằng tồn tại số nguyên k sao cho 2n k  1 là hợp số với mọi số nguyên dương n. Lời giải: Nhận xét: Bài tập này gần giống với bài tập số một nhưng nó phức tạp hơn bài toán 1 nhiều vì trong bài toán này ta không thể nhìn thấy ngay để 2n k  1 là hợp số ta cần chỉ ra nó chia hết cho số nào. Để ý thấy trằng trong bài toán 1 ta xét hai trường hợp n chẵn và n lẻ hay tổng quát là xét n ở dạng sau 2m l với m, l là các số tự nhiên, l lẻ. m m m Khi đó 2 n k  1  2 2 l k  1 và ta có 2 2 l  1mod(2 2  1) , do đó để 2n k  1 là hợp m số ta chỉ ra 2n k  1 chia hết cho Fm  22  1 (Dãy Fermat). 2 Đặng Đình Sơn Ứng dụng định lí Phần dư Trung Hoa giải các bài toán số học Ta trình bày lời giải bài toán này như sau: Trước hết ta có F0 , F1 , F2 , F3 , F4 là các số nguyên tố, F5  641.6700417 và ( Fi , F j )  1, i  j. Theo định lí phần dư Trung Hoa, tồn tại số nguyên dương k thoả mãn:  k  1(mod Fm )  m  0,1, 2, 3, 4  (p = 641, q = 6700417, (p,q)=1).   k  1(mod p )  k  1(mod q ) Ta có n  2m l , với m, l là các số tự nhiên, l lẻ. m + Nếu m < 5 thì 2 n  2 2 l  1(mod Fm )  2 n k  1(mod Fm )  2n k  1 Fm m + Nếu m = 5 thì 2n  22 l  1(mod F5 )  2n k  1(mod p )  2 n k  1 p 5 + Nếu m > 5 thì 2 n  (2 2 ) 2 m 5 l  1(mod F5 )  2 n k  1(mod q )  2 n k  1 q Do đó 2n k  1 là hợp số với mọi số nguyên dương n. Bài toán 3. Cho là tập S  {p1 ,p2 ,...pk } gồm k số nguyên tố phân biệt, và f ( x) là đa thức với hệ số nguyên sao cho với mọi số nguyên dương n đều tồn tại p i trong S sao cho p i | f (n) . Chứng minh rằng tồn tại i sao cho p i | f (n ), n  N * . Lời giải: Giả sử không tồn tại i sao cho p i | f (n), n  N * , suy ra với mọi i=1;k luôn tồn tại ai sao cho pi | f (ai ) . Mặt khác theo định lí Phần dư Trung Hoa tồn tại số tự  x  ai (mod pi )  f ( x)  f ( ai )(mod pi ) nhiên x thỏa mãn  , do đó  hay p i | f ( x), i  1; k i  1, k i  1, k (Mâu thuẫn) Bài toán 4. Cho n  p1 p2 ... pk và f ( x) là một đa thức với hệ số nguyên. Khi 1 đó phương trình đồng dư k 2 f ( x)  0(mod n) có nghiệm khi và chỉ khi tất cả các phương trình đồng dư f ( x)  0(mod pi ), i  1; k có nghiệm. Nếu gọi là số nghiệm i của phương trình f ( x)  0(mod pi ) là ni , i  1; k thì phương trình n  p1 p2 ... pk có i 1 đúng n1.n2…nk nghiệm (môđun n) 3 2 k Đặng Đình Sơn Ứng dụng định lí Phần dư Trung Hoa giải các bài toán số học Lời giải:  Giả sử x là một nghiệm của f ( x )  0(mod n) , hiển nhiên x là một nghiệm của  f ( x)  0(mod pi i ) hệ  . i  1; k  Giả sử xi là một nghiệm của f ( x)  0(mod pi ), i  1; k . Theo định lí Phần dư i  x  xi (mod pii ) Trung Hoa tồn tại duy nhất x là nghiệm của hệ  (mod n). Mà i  1; k x  xi (mod piai )  f ( x)  f ( xi )(mod piai ) (vì ( f ( x )  f ( xi ))  ( x  xi ) ), suy ra x là một nghiệm của f ( x )  0(mod n) . Mỗi bộ ( x1 , x2 ,..., xk ) với xi là một nghiệm của f ( x)  0(mod pi ), i  1; k cho ta một i nghiệm của f ( x )  0(mod n) và hiển nhiên các nghiệm này là phân biệt (vì trong hai bộ khác nhau phải tồn tại ít nhất một cặp xii , xi2 là hai nghiệm khác nhau của f ( x)  0(mod pi ) , do đó hai nghiệm tương ứng với hai bộ đó không đồng dư theo i mod pii ). Do đó số nghiệm của f ( x)  0 đúng bằng n1.n2…nk. Như vậy dựa vào định lí Phần dư Trung Hoa ta có thể đếm được số nghiệm của một phương trình đồng dư. Bài toán 5, bài toán 6 sau đây là các ví dụ cụ thể cho bài toán 4. Bài toán 5. Cho số nguyên dương n  p1 p2 ... pk , trong đó p1 , p2 ,..., pk là các 1 2 k số nguyên tố đôi một khác nhau. Tìm số nghiệm của phương trình đồng dư x 2  x  0(mod n) . Lời giải:   x  0(mod pii ) i  x ( x  1)  0(mod p )   i x 2  x  0(mod n)      x  1(mod pii ) i  1, k  i  1, k  x  ai (mod pii )  Theo định lí phần dư Trung Hoa mỗi hệ phương trình  ai  {1;0} có duy  i  1, k nhất một nghiệm (thặng dư modn) và ta có 4 2k hệ (bằng số bộ Đặng Đình Sơn Ứng dụng định lí Phần dư Trung Hoa giải các bài toán số học ( a1 , a2 ,..., ak ), ai  {1; 0} ), nghiệm của các hệ khác nhau. Suy ra phương trình x 2  x  0(mod n) có đúng 2k nghiệm. Bài toán 6. Cho số nguyên dương a  p1 p1... pk , trong đó p1 , p2 ,..., pk là các số nguyên tố đôi một khác nhau và số nguyên dương n thoả mãn k < n < p1 , p2 ,..., pk . Chứng minh rằng trong dãy sau có n k số chia hết cho a. u1  1.2...n, u2  2.3...(n  1), u3  3.4...(n  2),..., u a  a ( a  1)...( a  n  1) Lời giải: Nhận xét: Bài tập này tư tưởng giống như bài 4. i  ai (mod pi )  u j  a   ai  {0, 1, 2,..., (n  1)},  i  1, k j  1, a. Do đó ta có n k số chia hết cho a. * Cùng với tư tưởng như bài 4, ta có thể chứng minh công thức của Phi hàm Ơl bằng cách đưa về đếm số nghiệm của một hệ đồng dư. Bài toán 7. Cho số nguyên dương n,  (n) là số các số nguyên dương không vượt quá n và nguyên tố cùng nhau với n. Chứng minh rằng với n  p1 p2 ... pk , 1 2 k trong đó p1 , p2 ,..., pk là các số nguyên tố đôi một khác nhau, ta có :  (n)  n(1  1 1 1 )(1  )...(1  ) p1 p2 pk (Phi hàm Ơle ) Lời giải Nhận xét: Công thức trên đã được chứng minh bằng cách sử dụng tính chất  (n) là hàm nhân tính. Và để chứng minh tính chất trên ta phải sử dụng đến các tính chất của hệ thặng dư. Cách này khá phức tạp. Bài toán này có thể giải đẹp hơn bằng định lí đồng dư Trung Hoa An  a  N |1  a  n, (a, n)  1 Khi n  p   (n)  p  p 1 Khi n  p1 p2 ... pk , trong đó p1 , p2 ,..., pk là các số nguyên tố đôi một khác 1 2 k nhau. Với số nguyên dương a thoả mãn 1  a  n ta có: 5 Đặng Đình Sơn Ứng dụng định lí Phần dư Trung Hoa giải các bài toán số học  a  a (mod pi ) i i  a  An  (a, pi i )  1, i  1, k   ai  Api  i  1, k Mà theo định lí phần dư Trung Hoa, tồn tại duy nhất số nguyên dương a,  a  a (mod pi ) i i  và ta có   ai  Api  i  1, k 1  a  n thoả mãn k k  | Apai |   ( pii  pii 1 ) hệ dạng i 1 i i 1 trên, nghiệm của các hệ khác nhau. k Do đó | An |   ( pi  pi 1 )  n(1  i i i 1 1 1 1 )(1  )...(1  ) . p1 p2 pk Bài toán 8. Cho An  a  N |1  a  n, (a, n)  (a  1, n)  1 . Tìm | An | . Lời giải: Nhận xét: Bài toán này có thể giải tương tự như cách chứng minh công thức phi hàm Ơle  (n) . Giả sử n  p1 p2 ... pk , trong đó p1 , p2 ,..., pk là các số nguyên tố 1 2 đôi một khác nhau, ta có | An |  n(1  * k 2 2 2 )(1  )...(1  ) . p1 p2 pk Sử dụng định lí đồng dư Trung Hoa chứng minh công thức của Phi hàm Ơle, cho ta một lời giải đẹp, nhưng cũng với tư tưởng trên và tính chất của hệ thặng dư ta còn có thể giải bài toán mở rộng của định lí Wilson. Bài toán 9. Tìm số nguyên dương n lẻ sao cho với mọi hệ thặng dư thu gọn mođun n a1 , a2 ,..., a ( n )  ta có a1a2 ...a ( n)  1(mod n) . Lời giải:  Theo định lí Wilson ta suy ra n nguyên tố thoả mãn.  Với n  p m với p là số nguyên tố lẻ. Ta có a1 , a2 ,..., a ( n )  là một hệ thặng dư thu gọn mođun n, suy ra với mỗi a  a1 , a2 ,..., a ( n )  đều tồn tại duy nhất a  a1 , a2 ,..., a ( n )  thoả mãn aa  1(mod n) và a  b  a  b. 6 Đặng Đình Sơn Ứng dụng định lí Phần dư Trung Hoa giải các bài toán số học  a  1(mod n) a  1 a  a  a 2  1 n  (a  1)(a  1) n    (vì (a-1,a+1)1) số nguyên tố lẻ, 1 2 k phân biệt. Tương tự như trên: Với mỗi a  a1 , a2 ,..., a ( n)  đều tồn tại duy nhất a  a1 , a2 ,..., a ( n )  thoả mãn aa  1(mod n) và a  b  a  b .   a  1(mod pii )  a  a  a 2  1 n  (a  1)(a  1) n    a  1(mod pii ) (Vì (a-1,a+1)