Nội dung text Tài liệu bồi dưỡng học sinh giỏi - Chuyên đề 17 - LÝ THUYẾT SỐ.doc
Trang 1 CHUYÊN ĐỀ 17: LÍ THUYẾT SỐ 1. KIẾN THỨC TRỌNG TÂM Số chính phương - Số chính phương là bình phương của một số tự nhiên - Số chính phương 2n tận cùng bằng 0, 1, 4, 5, 6, 9. Số nguyên tố - Hợp số - Số nguyên tố là số nguyên lớn hơn 1 và chỉ có 2 ước số là 1 và chính nó. - Các số nguyên tố 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, …. Nếu số nguyên a > 1 và không chia hết cho số nguyên tố a thì a nguyên tố - Số nguyên lớn hơn 1, không phải số nguyên tố gọi là hợp số. - Phân tích số tự nhiên m lớn hơn 1 ra thừa số nguyên tố một cách duy nhất 12k 12kmp.p...p - Số các ước nguyên dương của m là 12kdm11...1 - Tổng các ước nguyên dương của m là 12k11112k 12k p1p1p1 m.... p1p1p1 Số nguyên tố cùng nhau – Số nguyên – Số hữu tỉ - Nếu hai số nguyên a, b trong đó có ít nhất một khác 0 thì ƯCLN d = (a, b), (a, b) = ax + by với x, y nguyên, (a, b) = (a, a b) và BCNN ma,b thì a,b.a,ba.b , mm ,1 ab - Nếu (a, b) = 1 thì a và b nguyên tố cùng nhau. Nếu (a, b) = 1 thì nna,b1 . - Các số nguyên dương a và b nguyên tố cùng nhau khi và chỉ khi tồn tại các số nguyên x và y sao cho: ax + by = 1. - Hàm Ơle m : các số bé hơn số nguyên dương m và nguyên tố cùng nhau với m. Nếu 12k 12kmp.p...p thì 12k 111 mm11...1 ppp Nếu m = p nguyên tố thì pp1 Nếu (a, b) = 1 thì aba.b - Số hữu tỉ có dạng *m p,mZ,nN n Phần nguyên – phần lẻ - Phần nguyên của số thực x là số nguyên lớn nhất không vượt quá x, kí hiệu [x], nghĩa là xxx1 - Nếu x = m + r với m nguyên và 0r1 thì [x] = m và r gọi là phần lẻ, r = {x}. - Nếu n nguyên thì [n + x] = n + [x] với mọi x Chứng minh chia hết - Phép chia số nguyên a cho số nguyên b 0: a = b.q + r với thương q nguyên và dư r nguyên thỏa 0rb . Nếu r = 0 thì số nguyên a chia hết cho số nguyên b 0 (b chia hết a, a là bội số của b, b là ước của a), kí hiệu a ⋮ b hay ba .
Trang 2 - Dấu hiệu chia hết cho 2 là số chẵn; cho 5 là chữ số tận cùng 0, 5; cho 4 (hoặc 25) là hai chữ số tận cùng ⋮ 4 (hoặc 25); cho 8 (hoặc 125) là ba chữ số tận cùng ⋮ 8 (hoặc 125); cho 3 (hoặc) 9 là tổng các chữ số ⋮ 3 (hoặc 9); cho 11 là hiệu của tổng các chữ số hàng thứ chẵn với hàng thứ lẻ ⋮ 11. Dư và đồng dư - Cho số nguyên m > 1. Nếu hai số a, b có cùng dư khi chia cho m thì a đồng dư với b theo modun m, kí hiệu a b (modm) Nếu a b (modm), c d (modm) thì acbdmodm , acbdmodm - Định lý Ơle: với (a, m) = 1 thì ma1modm - Định lý Fecma: với p nguyên tố thì paamodp với (a, p) = 1 thì p1a1modp - Tập 12na,a,...,a là hệ thăng dư đầy đủ modulo m nếu với mọi i, 0im1 , tồn tại duy nhất j sao cho jaimodm - Định lý phần dư Trung Hoa: Nếu r và s là 2 số nguyên dương nguyên tố cùng nhau, a và b là 2 số nguyên bất kì, thì hệ 2 phương trình đồng dư: Namodr và Nbmods có nghiệm duy nhất N theo modulo (rs). Tổng quát: Nếu 12km,m,...,m là các số nguyên tố cùng nhau từng đôi một và 12ka,a,...,a là các số nguyên, thì hệ k phương trình đồng dư: iixamodm ; I = 1, 2 …, k có nghiệm x nguyên duy nhất theo modulo 12kMm.m...m . Chú ý: 1) Nếu a tận cùng 0, 1, 5, 6 thì na cũng tận cùng 0, 1, 5, 6 tương ứng. Vì 104 , nếu n = 4k + r và nếu a tận cùng 3, 7 thì chữ số tận cùng của na là chữ số tận cùng của ra , còn nếu a tận cùng 2 thì chữ số tận cùng của na là chữ số tận cùng của r6.2 . 2) Nếu a tận cùng là x thì 20a có hai chữ số tận cùng là 2 chữ số tận cùng của 20x . Tìm hai chữ số tận cùng của na đưa về tìm dư trong phép chia n cho 20. 3) Hệ nhị phân của số tự nhiên nn1 n110ka.2a2...a2a là nn110kaa...aa (2) với ina0;1,a0 . Tổng quát, số tự nhiên s viết trong hệ g – phân nếu: nn1 nn110sagag...aga là nn110saa...aa (g) Với ina0,1,...,g1,a0 4) Phương trình Pell: Nếu (a, b) là nghiệm nguyên dương bé nhất của phương trình 22 xdy1 thì mọi nghiệm nguyên dương đều có dạng: nnnn nn abdabdabdabd x,y, 22d 2. CÁC BÀI TOÁN Bài toán 17.1: Chứng minh a) 100110170.2731.38 chia hết cho 13.
Trang 3 b) Nếu ba số a, a + k và a + 2k đồng thời là ba số nguyên tố phân biệt lớn hơn 2 thì k6⋮ . Hướng dẫn giải a) Ta có 1001271mod13271mod13 Và 101381mod13381mod13 10012713n1nN và 1013813m1mN 100110170.2731.387013n13113m170n31m1339 đpcm. b) Ta biết rằng các số nguyên tố lớn hơn 3 có thể biểu diễn dưới dạng 6p + 1 hoặc 6p + 5 (p nguyên dương) (*) ? Ba số a, a + k, a + 2k lớn hơn 3 chỉ có thể biểu diễn trong hai dạng nên theo nguyên tắc Đirichlê, nhất định phải có hai số được biểu diễn trong cùng một dạng, chẳng hạn đó là 6p + r và 6s + r với r là 1 hoặc 5. Hiệu của hai số này bằng 6s – 6p = 6 (s – p) ⋮ 6. Mặt khác hiệu của hai trong ba số trên hoặc bằng k hoặc bằng 2k nên k ⋮ 3, nhưng k là số chẵn nên k ⋮ 6. Bài toán 17.2: Chứng minh với mọi m, tồn tại số nguyên n để: 32 n11n87nm chia hết cho 191. Hướng dẫn giải Đặt 32Pxx11x87xm Giả sử: 3Pxxabmod191 322332x3ax3axabx11x87xmmod191 2 3 3a11mod1911 3a87mod1912 bmamod1913 13a180mod191a90mod191 23a87mod191 . Vậy mZ , tồn tại số nguyên a, b để: 3Pxxabmod191 Nhận xét: 191 là số nguyên tố dạng 191 = 3k + 2 33PiPjmod191iajamod191 Đặt u = i + a, v = j + a thì 33uvmod191 3k3kuvmod191 3k23k2191uvvvmod191vmod191 (định lý Ferma) (1) 23k33k3vuvumod191 3k23k3k33k13k23k11913k1uvu.uu.uu.uu.umod191 3k2191uuumod191 (2) (1) và (2) suy ra: uvmod191ijmod191 Nếu i,j1,2,...,191;ijmod191 thì PiPjmod191 Suy ra tồn tại n1,2,...,191 sao cho P (n) = 191 (mod 191) tức là: Pn0mod191 .
Trang 4 Bài toán 17.3: Cho x, y là các số nguyên, x1;y1 sao cho 44 x1y1 y1x1 là số nguyên. Chứng minh 444xy1 chia hết cho x + 1 Hướng dẫn giải Ta chứng minh 4y1 chia hết cho x + 1. Đặt 44 x1ay1c ; y1bx1d Trong đó a,b,c,dZ , (a, b) = 1; (c, d) = 1; b > 0, d > 0 Từ giả thiết, ta có adbc bd nguyên, suy ra d | b và b | d. Mặt khác, do ac . bd nguyên; (a, b) = 1 và (c, d) = 1, nến b = d = 1. Suy ra 4 y1 chia hết cho x +1. Từ đó 4444444xy1xy1x1 chia hết cho x + 1 (do 44y1 chia hết cho 4y1 nên nó chia hết cho x + 1 và 4x1 chia hết cho x + 1). Bài toán 17.4: Với mọi số tự nhiện n, chứng minh rằng tổng n 2k13k 2n1 k0 C.2 không chia hết cho 5. Hướng dẫn giải Đặt x8 , dùng công thức khai triển nhị thức Newton để biến đổi: 2n11xABx* với n 2k13k 2n1 k0 BC.2 Tương tự: 2n11xABx (**) Nhân vế theo vế (*) và (**) ta được: 2n12278BA Mặt khác, 2n172mod5 Do vậy, nếu B là bội của 5 thì: 2A2mod5 : vô lý. Bài toán 17.5: Chứng minh phần nguyên của 2n1113 thì chia hết cho n12 và không chia hết cho n22 với mọi n là số tự nhiên. Hướng dẫn giải Ta có: 2n12n1113113 là số tự nhiên Mà 2n11130;1 nên 2n12n12n1113113113 (Vì abkNakb với b0;1 nên [a] = k = a – b) Với n = 0; 111131136 chia hết cho 0122 nhưng không chia hết cho 2 24 . Mà: 2211311340 nên với n = 1 thì: