Tài liệu Các bài luyện tập vế số học thi học sinh giỏi

LUYÊN TẬP VỀ SỐ HỌC Số học nghiên cứu các bài toán liên quan đến số nguyên, sự chia hết, số nguyên tố, số chính phương, sự hữu tỷ-vô tỷ, các phương trình nghiệm nguyên, nghiệm hữu tỷ. Số nguyên tố là khái niệm nền tảng trong số học, vì thế những định lý liên quan đến số nguyên tố như định lý cơ bản của số học, định lý về luỹ thừa của số nguyên tố p trong n!, định lý về sự tồn tại vô số số nguyên tố là những kiến thức cần nắm được. Một trong những công cụ quan trọng để giải các bài toán số học là lý thuyết đồng dư. Trong phần này, có những tính chất và định lý quan trọng như định lý nhỏ Fermat, định lý Wilson, định lý Euler, định lý Trung Hoa về số dư, định lý Bezout … Các hàm số quan trọng của số học như  hàm Euler, hàm , hàm  cũng được xuất hiện trong lý thuyết đồng dư. Khái niệm bậc của một số theo modulo m với những tính chất quan trọng của nó cũng có nhiều ứng dụng trong việc giải các bài toán số học. Chúng ta cũng cần nắm vững về USCLN, BSCNN và các tính chất của nó, thuật toán Euclide, thuật toán Euclide mở rộng, định lý Bezout và ứng dụng của nó. Trong phần nâng cao, chúng ta có thể nghiên cứu thêm về số chính phương modulo p, căn nguyên thuỷ. Phương trình Diophant cũng là một mảng quan trọng trong các bài toán số học: ngoài các phương pháp thông dụng như chọn module, chặn nghiệm, kẹp bình phương, phân tích tiêu chuẩn, ta cũng cần biết đến một số vấn đề nâng cao như phương trình Pell, phương pháp phương trình Markov. Một số bài tập có lời giải 1. Cho a, b là các số nguyên dương sao cho ( a, b)  a 1 b 1  là số nguyên. Chứng minh rằng b a a  b. Lời giải. Ta có a 1 b 1 a2  b2  a  b   . Đặt d = (a, b) thì do ab chia hết cho d 2 nên a2 + b2 + b a ab a + b chia hết cho d2. Số a2 + b2 cũng chia hết cho d2. Do đó a + b chia hết cho d 2 và như vậy a  b  d. 2. (Korea 2007) Tìm tất cả các cặp số nguyên tố p, q sao cho pp + qq + 1 chia hết cho p.q. Lời giải. Deã thaáy pq. Khoâng maát tính toång quaùt ta giaû söû p < q . Neáu p=2 . Ta coù qq + 5 ≡ 5 ≡ 0( mod q ) suy ra, q=5. Neáu p  2 thì p vaø q ñeàu laø soá nguyeân toá leû. Hôn nöõa, q – p ≥ 2 (1) Töø ñieàu kieän baøi toaùn ta suy ra : pp + 1 ≡ 0 ( mod q ) Suy ra: p2.p ≡ 1 ( mod q) Theo ñònh lyù Fermat nhoû ta coù : pq-1 ≡ 1 ( mod q ) Do ñoù : p(2.p, q-1) ≡ 1 ( mod q ) Ta coù: (2.p, q-1) = 2 hoaëc (2.p, q-1) = 2.p Neáu (2.p, q-1) = 2 thì p2 ≡ 1 ( mod q ) Suy ra: p ≡ 1 ( mod q ) hoaëc p ≡ -1 ( mod q ) Ñieàu naøy maâu thuaãn vôùi (1) Neáu (2.p, q-1) = 2.p thì q ≡ 1 ( mod p ) Suy ra: 1 + pp + qq ≡ 1 + pp + 1 ≡ pp + 2 ≡ 2 ( mod p) Töø ñieàâu kieän baøi toaùn suy ra: 2 ≡ 0 ( mod p ) Maâu thuaãn vì p > 2 . Vaäy (p , q) = (2 , 5) hoaëc (5 , 2) laø hai caëp soá nguyeân toá caàn tìm. 3. Cho a, b là các số nguyên dương nguyên tố cùng nhau. Chứng minh rằng N 0 = ab – a – b là số nguyên nhỏ nhất không biểu diễn được dưới dạng ax + by với x, y là các số nguyên không âm. Hơn nữa, với mọi p, q nguyên với p + q = N0, có đúng một trong hai số biểu diễn được dưới dạng ax + by với x, y là các số nguyên không âm (mà ta sẽ gọi tắt là biểu diễn được). Lời giải. Ta có nếu N0 biểu diễn được thì N0 = ax + by với x, y  0  ab – a – b = ax + by  a(b-x-1) = b(y+1). Từ đó suy ra a(b-x-1) chia hết cho b. Mà (a, b) = 1 nên (b-x-1) chia hết cho b. Điều này chỉ \có thể xảy ra khi b – x – 1 = 0. Nhưng khi đó y = -1, mâu thuẫn. Tiếp tục, ta sử dụng bổ đề sau: Bổ đề: Nếu (a, b) = 1 thì với mọi số nguyên n, tồn tại duy nhất cặp số nguyên x, y sao cho i) n = ax + by ii) 0  x < b Chứng minh: Từ định lý Bezout suy ra tồn tại u, v nguyên sao cho au + bv = 1. Nhân hai vế với n, ta được n = a(nu) + b(nv). Lấy nu chia cho b ta được nu = bq + r với 0  r < b. Thay vào, ta được n = a(bq + r) + b(nv) = ar + b(nv+aq) Đặt x = r, y = nv + aq, ta tìm được cặp số (x, y) thoả mãn điều kiện định lý. Tính duy nhất là hiển nhiên. Bây giờ xét hai số p, q có p + q = N 0. Rõ ràng nếu p và q cùng biểu diễn được thì N 0 cũng biểu diễn được, mâu thuẫn, do đó trong hai số p, q, chỉ có nhiều nhất một số biểu diễn được. Ta chứng minh sẽ có ít nhất một số biểu diễn được. Theo bổ đề, p, q biểu diễn được dưới dạng p = ax1 + by1, q = ax2 + by2 với 0  x1, x2 < b Ta có p + q = a(x1+x2) + b(y1+y2) = N0 = ab – a – b Suy ra a(x1+x2-b+1) + b(y1+y2+1) = 0 Từ đẳng thức này suy ra x1 + x2 – b + 1 chia hết cho b. Nhưng ta có - b + 1 < x1 + x2 – b + 1 < b-1 nên điều này chỉ có thể xảy ra khi x1 + x2 – b + 1 = 0, suy ra y1 + y2 + 1 = 0, suy ra một trong hai số y1, y2 có 1 số  0, có nghĩa là một trong hai số p và q biểu diễn được. Cuối cùng, để kết thúc lời giải bài toán, ta chú ý rằng nếu N > N 0 thì do N + (N0 – N) = N0 và N0 – N không biểu diễn được nên N biểu diễn được, do đó N 0 là số nguyên dương nhỏ nhất không biểu diễn được. 4. Tồn tại hay không một đa thức P(x)  Z[x], không có nghiệm nguyên sao cho với mọi số nguyên dương n, tồn tại số nguyên x sao cho P(x) chia hết cho n. Lời giải: Tồn tại. Ta có thể xét đa thức P(x) = (3x+1)(2x+1). Với mỗi số nguyên dương n, ta biểu diễn n dưới dạng n = 2k(2m+1). Vì (2k, 3) = 1 nên tồn tại a sao cho 3a  1 (mod 2k), từ đó 3x  -1 (mod 2k)  x  - a (mod 2k). Tương tự (2, 2m+1) = 1 nên tồn tại b sao cho 2b  1 (mod 2m+1), từ đó 2x  -1 (mod 2m+1)  x  - b (mod 2m+1) k Cuối cùng, do (2 , 2m+1) = 1 nên theo định lý Trung Hoa về số dư, tồn tại số nguyên x là nghiệm của hệ x  -a (mod 2k) x  - b (mod 2m+1) Và theo lý luận trên, P(x) = (3x+1)(2x+1) chia hết cho n. 5. Chứng minh rằng nếu a, b, c là các số nguyên và a b c    3 thì abc là lập phương của một số b c a nguyên. Lời giải. Cách 1. Không mất tính tổng quát, có thể giả sử (a, b, c) = 1. Viết phương trình dưới dạng a 2c + b2a + c2b = 3abc. Giả sử p là một ước số nguyên tố của a, khi đó p | c 2b, suy ra p là ước của c hoặc là ước của p. Do (a, b, c) = 1 nên p là ước của đúng một trong hai số. Không mất tính tổng quát, giả sử p | c. Gọi m, n là các số mũ lớn nhất sao cho p m | a và pn | c. Đặt a = p m.a’ và c = pn.c’ và thay vào phương trình, ta được p2m+n.a’2c’+ b2pm + p2n.c’b = 3.pm+n.a’bc’ + Nếu m < 2n thì chia hai vế của đẳng thức trên cho pm, ta được pm+n a’2c’+ b2 + p2n-mc’b = 3.pn.a’bc’ Điều này mâu thuẫn vì 3 số hạng chia hết cho p còn b2 không chia hết cho p. + Nếu m > 2n thì chia hai về của đẳng thức trên cho p2n, ta được p2m-na’2c’ + b2pm-2n + c’b = 3.pm-na’bc’ Điều này cũng mâu thuẫn vì 3 số hạng chia hết cho p, còn c’b không chia hết cho p. Vậy chỉ còn khả năng duy nhất m = 2n. Khi đó số mũ của p trong tích abc là 3n, chia hết cho 3. Điều này đúng với mọi ước nguyên tố của a (và do đó của b, c) nên suy ra abc là lập phương của một số nguyên. Cách 2. Đặt a/b = x, b/c = 1/y thì ta được x + 1/y + y/x = 3 2  x y + x + y2 – 3xy = 0  y2 + (x2-3x)y + x = 0 (1) Xem (1) như phương trình bậc 2 theo y, ta có  = (x2-3x)2 – 4x = x4 – 6x3 + 9x2 – 4x = x(x-4)(x-1)2 Để (1) có nghiệm hữu tỷ thì  phải là bình phương của một số hữu tỷ, suy ra x(x-4) là bình phương của một số hữu tỷ. Suy ra x(x-4) = u2  (x-2)2 – u2 = 4  (x – 2 – u)(x – 2 + u) = 4. Đặt x – 2 – u = 2k thì x – 2 + u = 2/k, từ đây ta tính được x = 2 + k + 1/k = (k+1)2/k, u = 1/k – k, suy ra  = (1/k-k)2(1+k+1/k)2 Như vậy 3 x  x 2  (1 / k  k )(1  k  1 / k ) 2 3( 2  k  1 / k )  ( 4  k 2  1 / k 2  4 k  4 / k  2)  (1 / k  k  1 / k  2 2  k  k   2  1 / k  1 / k  y  2 Từ đây suy ra, trong cả hai trường hợp xy là lập phương của một số hữu tỷ. Nhưng abc = bx.b.by = b3xy nên từ đây abc là lập phương của một số hữu tỷ. Từ một tính chất quen biết suy ra abc là lập phương của một số nguyên. 6. Chứng minh rằng nếu p là số nguyên tố dạng 4k+3 và a 2 + b2 chia hết cho p thì a và b cũng chia hết cho p. Lời giải. Giả sử ngược lại a2 + b2  0 mod p mà (a, p) = 1, (b, p) = 1. Khi đó a2  -b2 (mod p) Luỹ thừa 2k+1 hai vế, ta được a4k+2  -b4k+2 (mod p) (1) Mặt khác, theo định lý nhỏ Fermat thì a4k+2  b4k+2  1 (mod p). Do đó (1) xảy ra khi và chỉ khi 2  0 (mod p), mâu thuẫn. Hệ quả: Số nguyên có dạng x2 + 1 không có ước số nguyên tố dạng 4k+3. 7. Chứng minh các phương trình sau không có nghiệm nguyên dương a) 4xy – x – y = z2 (Euler) b) x2 - y3 = 7 (Lebesgue)  k 2 Lời giải. a) Giả sử tồn tại các số nguyên dương x, y, z thoả mãn phương trình. Viết phương trình dưới dạng (4x-1)(4y-1) = (2z)2 + 1. Số 4x - 1 có dạng 4k+3 nên tồn tại ít nhất một ước số nguyên tố p của nó có dạng 4k+3. Theo hệ quả nói trên, p không thể là ước số của (2z)2 + 1, mâu thuẫn. b) Viết phương trình lại dưới dạng x2 + 1 = 8 + y3 = (2+y)(4-2y+y2) Nếu y chẵn thì x phải lẻ, nhưng khi đó vế trái chia 4 dư 2 còn vế phải chia hết cho 4, mâu thuẫn. Vậy y lẻ. Nếu y có dạng 4k+1 thì 2 + y = 4k +3. Nếu y có dạng 4k-1 thì y 2 - 2y + 4 = 16k2 - 8k + 1 2(4k-1) + 4 = 4(4k2-4k+1) + 3. Suy ra vế phải có ít nhất một ước số nguyên tố p dạng 4k+3. Một lần nữa, theo hệ quả, p không chia hết vế trái, mâu thuẫn. 8. Cho (a, n) = 1 và h là số nguyên dương nhỏ nhất sao cho a h  1 (mod n). Khi đó với mọi số nguyên dương m sao cho am  1 (mod n) ta có m chia hết cho h. Lời giải. Giả sử ngược lại m = hq + r với 0 < r < h thì từ 1  am  ahq + r = (ah)q.ar  ar (mod n), mâu thuẫn với tính nhỏ nhất của h. n 9. Chứng minh rằng nếu p là ước số của số Fn  2 2  1 thì p có dạng 2n+1.k + 1. Lời giải. Giả sử p là một ước số nguyên tố của F n và h là số nguyên dương nhỏ nhất sao cho 2 h  1 mod p. Khi đó, vì 2 2  1 (mod p )  2 2  1 (mod p ) , nên từ đây ta suy ra h | 2n+1. Suy ra h = 2m. Nhưng cũng từ 2 2  1 (mod p ) suy ra m > n, tức là h = 2 n+1. Mặt khác, theo định lý nhỏ Fermat thì 2p-1  1 (mod p), suy ra p-1 chia hết cho h = 2 n+1, tức là p-1 = 2n+1.k, suy ra p = 2n+1.k+1 (đpcm). n 1 n n 10. a) Chứng minh tồn tại số n chẵn, n > 2008 sao cho 2009.n – 49 là số chính phương. b) Chứng minh không tồn tại số nguyên m sao cho 2009.m – 147 là số chính phương. Lời giải. Vì 2009 = 49.41 = 72.41 nên bài toán tương đương với việc chứng minh tồn tại n chẵn n > 2008 sao cho 41.n – 1 là số chính phương và không tồm tại số nguyên m sao cho 41.m – 3 là số chính phương. Để giải câu a) trước hết ta tìm một số nguyên x sao cho x 2 + 1 chia hết cho 41. Điều này có thể thực hiện được bằng các phép thử liên tiếp hoặc dùng định lý Wilson (40! + 1 chia hết cho 41 => (20!) 2 + 1 chia hết cho 41). Phép thử trực tiếp cho ta nghiệm x = 9. Bây giờ xét x = 41k + 9 và đặt n = (x 2 + 1)/41 = 41k2 + 18k + 2 thì 41.n – 1 = x 2 chính phương. Chỉ cần chọn k chẵn và đủ lớn (chẳn hạn k = 10 thì n sẽ chẵn và lớn hơn 2008). Để giải câu b), ta chứng minh rằng 41.m – 3 không thể là số chính phương, nói cách khác x 2 + 3 không chia hết cho 41. Bằng phép thử trực tiếp ta thấy -3  - 3 (mod 41) (-3)2  9 (mod 41) (-3)4  - 1 (mod 41) (-3)20  - 1 (mod 41) Nếu tồn tại x sao cho x 2 + 3 chia hết cho 41 thì x 2  -3 (mod 41) => x40  (-3)20 (mod 41) => x40  - 1 (mod 41) điều này mâu thuẫn với định lý nhỏ Fermat. 11. Chứng minh rằng nếu n là một số hoàn hảo chẵn khi và chỉ khi n có dạng là số nguyên dương sao cho 2k-1 là số nguyên tố. 2 k-1(2k-1) trong đó k Lời giải. Vì n chẵn nên ta đặt n = 2t.m, trong đó m là số lẻ. Ta có (n) = (2t)(m) = (2t+1-1)(m) Vì n là số hoàn hảo nên (n) = 2n = 2t+1.m 12. Tìm tất cả các cặp số nguyên dương a, b sao cho a 2b  b là số nguyên. ab 2  9 13. Chứng minh rằng nếu x, y, z là các số nguyên dương với (x, y, z) = 1 và 1 1 1   x y z thì x+ y, x – z và y – z là các số chính phương. Lời giải. Đẳng thức 1 1 1   x y z có thể viết lại thành z(x+y) = xy  (x-z)(y-z) = z2. Đặt d = (x-z, y-z) thì từ phương trình suy ra d | z => d | x, y => d = 1. Từ đó suy ra x–z = m 2, y – z = n2 và z = mn. Từ đó x + y = m2 + n2 + 2z = m2 + n2 + 2mn = (m+n)2. 14. Chú ý rằng nếu lấy tích của hai số bất kỳ trong các số {1, 16, 27) cộng với 9 thì ta được một số chính phương. Hãy tìm số nguyên dương n duy nhất có tính chất n + 9, 16n + 9, 27n + 9 là số chính phương. 15. Số N = 100! tận cùng bằng bao nhiêu chữ số 0? Chữ số khác 0 đầu tiên tính từ bên phải sang bằng bao nhiêu? 16. a) Chứng minh rằng với mọi số nguyên N, phương trình 5x + 8y = N có nghiệm nguyên. b) Chứng minh rằng với mọi số nguyên N  40, phương trình 5x + 8y = N có nghiệm nguyên không âm. c) Tìm số N0 lớn nhất không biểu diễn được dưới dạng 5x + 8y với x, y là các số nguyên không âm. 17. Chứng minh rằng C nk là số lẻ với mọi k = 0, 1, 2, …, n khi và chỉ khi n có dạng 2m – 1. 18. Định lý Lucas: Gọi brbr-1…b1b0 và crcr-1…c1c0 là biểu diễn nhị phân của n và k tương ứng. Chứng minh rằng C nk lẻ khi và chỉ khi bi  ci với mọi i = 0, 1, …, r. 19. Chứng minh rằng nếu p là số nguyên tố dạng 6k-1 thì không tồn tại x sao cho x 2 + 3 chia hết cho p. 20. Tìm nghiệm nguyên dương của các phương trình sau a) xy = 2x-y b) xy2 = 2x-y Bài 1. (Korea 2007) Tìm nghiệm nguyên dương của phương trình 1 + 4x + 4y = z2. Bài 2. (PTNK 2008) Với mỗi số nguyên dương n, gọi S(n) là tổng các chữ số của n. a) Chứng minh rằng các số n = 999 và n = 2999 không thể biểu diễn được dưới dạng a + b với S(a) = S(b). b) Chứng minh rằng mọi s c) ố 999 < n < 2999 đều biểu diễn được dưới dạng a + b với S(a) = S(b). Bài 3. Tìm tất cả các đa thức f(x) với hệ số nguyên sao cho với mọi n nguyên dương ta có f(n) là ước của 2n – 1. Bài 4. Tìm tất cả các cặp số nguyên dương (a, b) sao cho 2a + 3b là bình phương của một số nguyên. Bài 5. Tìm tất cả các hoán vị (a1, a2, …, an) của (1, 2, …, n) sao cho 2(a1+…+ak) chia hết cho k+1 với mọi k=1, 2, …, n. Bài 6. Tìm tất cả các cặp số nguyên dương (a, n) thỏa mãn điều kiện: mỗi ước nguyên tố của a n+1 cũng là ước nguyên tố của a+1. Bài 7. Tìm tất cả các số nguyên dương lẻ n sao cho tồn tại các số nguyên lẻ x 1, x2, …, xn thoả mãn điều kiện x12 + x22 + … + xn2 = n4. Bài 8. Ký hiệu S(n) là tổng các chữ số của số nguyên dương n. Tìm giá trị nhỏ nhất của S(n) với n chạy trong tập hợp các bội số nguyên dương của 2003. Bài 9. (a) Cho trước số nguyên dương n. Chứng minh rằng tồn tại các số nguyên dương phân biệt x, y sao cho x + k chia hết cho y + k với mọi k = 1, 2, …, n. (b) Chứng minh rằng nếu với các số nguyên dương x và y ta có x + k chia hết cho y + k với mọi số nguyên dương k thì x = y. Bài 10. Tìm tất cả các số nguyên dương n có thể biểu diễn được dưới dạng n = [a, b] + [b, c] + [c, a] trong đó a, b, c là các số nguyên dương. ([a, b] ký hiệu bội số chung nhỏ nhất của các số nguyên dương a, b).