Giáo án Lý thuyết đồng dư thức

Vài dòng Lịch sử Lý thuyết Đồng dư do nhà Toán học Đức lỗi lạc K.F.Gauss (Kaclơ Friđơrich Gauxơ 1777-1855, người được mệnh danh là “ông vua Toán học”) xây dựng (các bạn có nhớ bài toán Gauss ở lớp 6 không ?), đây là lý thuyết rất quan trọng trong số học. Theo lịch sử, nhiều nhà Toán học Trung Quốc đã có khái niệm về đồng dư và vận dụng nó trong việc giải nhiều bài toán từ nhiều thế kỷ trước đó. Việc hiểu biết một vài khái niệm ban đầu về đồng dư thức giúp ta giải nhiều bài toán khó trong số học một cách nhẹ nhàng, ngắn gọn và rất đẹp (cái mà người học toán cần vươn đến !) trong tập hợp số nguyên Z. PHẦN I : Định nghĩa : Hai số nguyên a, b được gọi là đồng dư với nhau theo modulo m với m nguyên dương nếu hiệu a – b chia hết cho m. Ký hiệu a º b (mod m) Chú ý : Ký hiệu a º b (mod m) được gọi là một đồng dư thức. Các thể hiện Û Û Nếu a – b không chia hết cho m (với m nguyên dương) thì ta viết a º b (mod m) PHẦN II : Tính phản xạ : Với mọi số nguyên a, ta có : a º a (mod m) Tính đối xứng : Nếu a º b (mod m) thì b º a (mod m) Tính bắc cầu : Nếu a º b (mod m) và b º c (mod m) thì a º c (mod m) Các tính chất mở rộng : a . c º b . d (mod m) a ± c º b ± d (mod m) a º b (mod m) c º d (mod m) Hệ quả 1 a º b (mod m) a ± x º b ± x (mod m) a º b (mod m) c º d (mod m) Hệ quả 2 a º b (mod m) an º bn (mod m) , nỴN º (mod m) º (mod ) a º b (mod m) a º b (mod d) c) a º b (mod m) dỴƯC(a , b) ( d , m ) = 1 e) a º b (mod m) dỴƯC(a , b , m) d) a º b (mod m1) a º b (mod m2) m = [ m1 ; m2 ] f) a º b (mod m) dỴƯ(m) Định lý nhỏ FERMAT (Pierre de Fermat – Nhà Toán học thiên tài người Pháp, thế kỷ 17 ) Tại sao là định lý nhỏ ? có định lý lớn không ? chúng ta nói về lịch sử của chúng một chút ! Chúng ta biết rằng một trong những mục tiêu trong lịch sử phát triển Toán học là đưa lý thuyết Số học vào Đại số nhằm giải quyết các bài toán thực tế. Một trong các bài toán đó là bài toán về Phương trình nghiệm nguyên – có người nói “là cái đích cuối cùng của Số học” (theo tôi là rất đúng !) – chúng thuộc vào lớp các phương trình vô định. Người đầu tiên nghiên cứu có hệ thống về Phương trình vô định là nhà Toán học Diophante , sống ở thế kỷ thứ III. Tập sách “Số học “ của ông có ảnh hưởng rất lớn đến sự phát triển của Lý thuyết Số. Khi xét phương trình Diophante sau đây : xn + yn = zn với n>2, nhà toán học Fermat (Nhà toán hoc Bell – gắn với phương trình nghiệm nguyên Bell nổi tiếng – hóm hỉnh gọi Fermat là “ Hoàng tử của những người nghiệp dư “. Bell cho rằng Fermat đã đạt được nhiều thành tựu toán học quan trọng hơn hầu hếtcác nhà toán học “chuyên nghiệp” cùng thời với ông) khẳng định rằng phương trình trên không có nghiệm nguyên dương. Kết luận này được mang tên là Định lý lớn Fermat . Năm 1983, một nhà Toán học người Đức đã chứng minh được rằng phương trình xn + yn = zn với n>2 chỉ có một số hữu hạn nghiệm nguyên. Việc giải hoàn chỉnh phương trình xn + yn = zn với n>2, cho đến ngày nay vẫn còn là một thách thức đối với các nhà Toán học trên thế giới. Vì lẽ đó, định lý lớn Fermat đúng ra nên gọi là “một giả thuyết Fermat”. Các bạn biết rằng “ một giả thuyết “ thì có thể đúng hoặc sai, siêu bài toán Fermat tưởng đã đi vào ngõ cụt. Tuy nhiên, ngày 23/06/1993 nhà toán học AndrewWiles đã công bố công trình nghiên cứu của mình trước Hội nghị toán học Quốc tế tại Đại học Cambridge (Anh) về “Bài toán Fermat” sau 8 năm nghiên cứu (công trình này dày khoảng 300 trang giấy A4). Thế là bài toán nổi tiếng của mọi thời đại đã được giải quyết xong, người ta gọi Wiles là nhà “Chinh phục Toán học” và ngay ngày hôm sau cái tên Wiles đã trở nên quen thuộc với mọi người, mọi nhà ! . *** Định lý nhỏ FERMAT p là số nguyên tố ; a là số nguyên Þ ( ap - a ) º 0 ( mod p ) Hệ quả p là số nguyên tố ; a là số nguyên sao cho ( a , p ) = 1Þ ap - 1 º 1 ( mod p ) Một số ví dụ : VÍ DỤ 1 Tìm số dư trong phép chia 15325 – 1 cho 9 Hd : Ta có 1532 º 2 (mod 9) à 15325 º 25 (mod 9) Mà 25 º 5 (mod 9) à 15325 º 5 (mod 9). Vậy : 15325 - 1 º 4 (mod 9). Ý nghĩa : Để tìm số dư trong phép chia a cho b (b Ỵ N*), thông thường a là một lũy thừa với số mũ vô cùng lớn hay a chứa các lũy thừa như thế . Ta có thể làm theo cách như sau : Xem xét : a hoặc thành phần của a đồng dư với s theo modulo b. Nếu 0 £ s < b thì s là số dư trong phép chia a cho b. Ngược lại, xét tiếp tính đồng dư của s theo modulo b, rồi lặp lại theo bước vừa rồi. VÍ DỤ 2 Chứng minh rằng với mọi số nguyên dương n, ta có : (2. 7n + 1) 3 Hd : Ta có 7 º 1 (mod 3) à 7n º 1 (mod 3), với mọi số nguyên dương n. à 2. 7n º 2 (mod 3) à 2. 7n + 1 º 3 (mod 3) º 0 (mod 3) : đpcm ! VÍ DỤ 3 Với bất kỳ số nguyên a mà ( a, p ) = 1 trong đó p là số nguyên tố. Chứng minh rằng: nếu x, y là hai số nguyên dương thỏa (x – y) (p – 1) thì (ax – ay) p . Hd : Theo định lý nhỏ Fermat, ta có : ap – 1 º 1 (mod p) Vì (x – y) (p – 1) nên x – y = k.(p – 1) (k Ỵ Z) ax – y = ak.(p – 1) º 1 (mod p) ax : ay º 1 (mod p) à ax º ay (mod p) ax – ay º 0 (mod p) à (ax – ay) p - đpcm ! *** Trên đây chỉ là một vài ví dụ cơ bản của một lý thuyết lớn…muốn hiểu một cách tương đối, đề nghị bạn đọc làm thêm một số bài tập dưới đây nhằm khám phá “sự hấp dẫn” của Lý thuyết này… *** PHẦN III : Bài 1 : Chứng minh rằng ( 2147 - 1 ) 343 ( 235 + 292 ) 260 ( 301293 - 1 ) 13 ( 61000 - 1 ) 7 ( 19831983 - 19171917 ) 10 ( 2015 - 1 ) ( 11.31.61 ) ( 29 + 299 ) 100 ( 22225555 + 55552222 ) 7 ( 61001 + 1 ) 7 ( 19711917 - 19171960 ) 10 ( 270 + 370 ) 13 ( 18901930 + 19451975 + 1 ) 7 Hd h/ : 2222 º 3 (mod 7) , 22224 º 34 º 4 (mod 7) ; 5555 º 4 (mod 7) , 55552 º 42 º 2 (mod 7) Bài 2 : Chứng minh rằng abc º 0 ( mod 21 ) Û ( a - 2b + 4c ) º 0 ( mod 21 ) Bài 3 : Tìm số dư trong phép chia : 21997 cho 31 31997 cho 13 232 cho 11 21000 cho 3 , 5 , 7 Tổng 3100 + 3105 cho 13 Hiệu 15325 - 1 cho 9 24n + 1 cho 5 31000 cho 2 , 5 , 7 , 11 , 13 và 17 Bài 4 : Tìm hai chữ số tận cùng của 2999 ; 3999 ? Hd : Xét 2 chữ số tận cùng của 21000 ; 31000 hoặc để ý 210 = 1024 º 24 ( mod 100 ) Bài 5 : Chứng minh rằng 11991 + 21991 + 31991 + ... + 19911991 chia hết cho 11 Hd : Theo Fermat : a11 º a (mod 11) Þ a1991 º a (mod 11) Bài 6 : Chứng minh rằng với mọi n Ỵ N* 122n + 1 + 11n + 2 º 0 ( mod 133 ) 7.52n + 12.6n º 0 ( mod 19 ) 2.7n + 1 º 0 ( mod 3 ) 212n + 1 + 172n + 1 + 15 º 0 ( mod 19 ) 9n + 1 º 0 ( mod 4 ) 32n + 2 + 26n + 1 º 0 ( mod 11 ) 52n + 1 + 2n + 4 + 2n + 1 º 0 ( mod 23 ) º 0 ( mod 22 ) Hd : 24n + 1 = 5k + 2 Þ + 2 = 9.(22.11 + 1)k + 2 11 34n + 1 = 10q + 3 Þ + 3 = 8.322q + 3 = 8.(3.11 – 1)2q + 311 và để ý 2 Bài 7 : Số 3105 + 4105 chia hết cho 13 , 49 , 181 và 379 nhưng không chia hết cho 5 và 11 . Kiểm tra điều đó như thế nào ? Hd : Nhận xét rằng xn + yn chia hết cho x + y khi n lẻ . a/ 3105 + 4105 = (33)35 + (43)35 chia hết cho 33 + 43 = 7.13 Tương tự , ta chứng minh được 3105 + 4105 chia hết cho 49 , 181 , 379 . b/ Ta có 43 º -1 ( mod 5 ) { Điều này có nghĩa là 43 chia cho 5 dư -1 } Þ 4105 º (-1)35 ( mod 5 ) ; tương tự 3104 º 1 ( mod 5 ) nên 3105 º 3 ( mod 5 ) Þ 3105 + 4105 º 2 ( mod 5 ) : đpcm ! ----- Phần còn lại dành cho Bạn đọc. Bài 8 : Tìm tất cả các số nguyên n sao cho An = n3 + n2 + n + 1 º 0 ( mod 3 ) { n = 3k - 1 } Bn = n3 + n + 1 º 0 ( mod 3 ) { ( n3 - n ) + 3n + ( 1 - n ) ; n = 1 - 3k } Bài 9 : Tìm tất cả các số tự nhiên n sao cho 2n + 1 º 0 ( mod 3 ) { 2n + 1 º (-1)n + 1 ( mod 3 ) ; n lẻ } 11n + 7n º 0 ( mod 9 ) { n = 2k + 1 } 79 º 15 ( mod n ) { 64 º 0 ( mod n ) } Bài 10 : Chứng minh rằng với mọi số tự nhiên n , ta có Sn = n2 + 3n + 5 không chia hết cho 121. Hd : Sn = ( n - 4 )( n + 7 ) + 33 ; n + 7 º n - 4 ( mod 11 ) Bài 11 : Chứng minh rằng S = 1n + 2n + 3n + 4n ( n nguyên dương ) chia hết cho 5 khi và chỉ khi n không chia hết cho 4 . Hd : Ta có 14 º 1 ( mod 5 ) 24 º 1 ( mod 5 ) 34 º 1 ( mod 5 ) 44 º 1 ( mod 5 ) Từ đó với n = 4k + r ( r = 0, 1, 2, 3 ) Þ S = 1n + 2n + 3n + 4n º 1r + 2r + 3r + 4r ( mod 5 ) Bài 12 : Chứng minh rằng nếu a º 3 ( mod 5 ) thì 3a º 4 ( mod 5 ) Bài 13 : Chứng minh rằng nếu p là một số nguyên tố thì với mọi số nguyên a , b ta có : ap. b - a. bp º 0 ( mod p ) Hd : Ta có ap. b - a. bp = b( ap - a ) - a( bp - b ) ; sau đó áp dụng đ/l nhỏ Fermat Bài 14 : Tìm số dư trong phép chia n2 + 3n + 5 cho n + 1 ( nỴ N* ) Bài 15 : Tìm số dư trong phép chia A = cho 7 Hd : Theo Fermat 106 º 1 ( mod 7 ) , mà 10n º 4 ( mod 6 ) Þ 10n = 6k + 4 Þ = 106k + 4 º 104 ( mod 7 ) Þ A º 10.104 = 105 º 5 ( mod 7 ) Bài 16 : Chứng minh rằng với mọi số x nguyên dương lẻ:A(x) = 46x + 296.13x chia hết cho 1947 Hd : Ta có 1947 = 3 . 11 . 59 là tích của 3 số nguyên tố nên ta chứng minh A( x ) chia hết cho mỗi số đó . Bài 17 : Chứng minh rằng 19631965 - 1963 chia hết cho 3151733910 Hd : Ta chứng minh 19631965 - 1963 chia hết cho các số nguyên tố 2, 3, 5, 13, 109, 151, 491 . `Bài 18 : Tìm 5 chữ số tận cùng của 158k với k Ỵ N* Hd : Ta có 158k = 2562890625k º 90625k ( mod 105 ), 906252 = 8212890625 º 90625 (mod 105 ) Bài 19 : Chứng minh rằng 14k + 24k + 34k + 44k không chia hết cho 5 Hd : Theo Fermat ta có a4 º 1 ( mod 5 ) với a = 1, 2, 3, 4 Þ a4k º 1 ( mod 5 ) Bài 20 : Chứng minh rằng nếu ( a , 240 ) = 1 thì a4 º 1 ( mod 240 ) Hd : Vì 240 = 24.3.5 ; ( a , 240 ) = 1 Þ ( a , 2 ) = ( a , 3 ) = ( a , 5 ) = 1 . Từ đó suy ra : a4 º 1 ( mod 5 ) và a4 º 1 ( mod 48 ) Bài 21 : Chứng minh rằng : 130 + 230 + 330 + ... + 1030 º -1 ( mod 11 ) Hd : Theo Fermat ta có a10 º 1 ( mod 11 ) Þ a30 º 1 ( mod 11 ) với a = 1, 2, 3, ... , 10 Bài 22 : Nếu p là số nguyên tố lớn hơn 7 thì A = 3p - 2p - 1 chia hết cho 42p Hd : Vì 42p = 2.3.7.p nên ta chứng minh A º 0 ( mod 2.3.7.p ) Ta có 3p - 1 º 0 ( mod 2 ) Þ A º 0 ( mod 2 ) ; 2p + 1 º 0 ( mod 3 ) Þ A º 0 ( mod 3 ) 3p º 3 ( mod p ) ; 2p º 2 ( mod p ) Þ A º 3 – 2 – 1 º 0 ( mod p ) Mặt khác , vì p nguyên tố lớn hơn 7 nên p chỉ có thể có dạng 6k + 1 hoặc 6k + 5. Khi thay dạng thức p vào A , ta đều có A º 0 ( mod 7 ) ; với chú ý 36k º 1 ( mod 7 ) và 26k º 1 (mod 7) Bài 23 : Chứng minh rằng, nếu a2 º a (mod m) thì an º a (mod m) . Bài 24 : Tìm chữ số tận cùng của các tổng sau : 2943+ 3443 + 4343 + 5043 Bài 25 : Gọi A là tổng các chữ số của 44444444, B là tổng các chữ số của A và C là tổng các chữ số của B. Tìm tổng các chữ số của C ? (IMO-1980) Bài 26 : Chứng minh rằng không có giá trị nguyên nào của các xi thỏa mãn pt : (1) Hd Có º 0 (mod 16) nếu xi chẵn và º 1 (mod 16) nếu xi lẻ => chia cho 16 dư : 0 hoặc 1 => VT(1) º a (mod 16) với a ≤ 14 mà 1999 º 15 (mod 16) => (1) không có nghiệm nguyên Bài 27 : CMR số 1 + 919 + 93199 + 19931994 không phải là số chính phương . Phát biểu bài toán tổng quát ? Hd Ta có : 1 + 919 + 93199 + 19931994 º 2 (mod 3) Bài toán tổng quát : 1 + 9m + 93n + 1993p (m, n, p ỴN*) không phải là số chính phương . -----HẾT-----