Title 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ì: