Nội dung

Chương 7 Một số bài toán số học hay trên VMF 7.1 7.2 . m3 + 17..3n 129 c(ac + 1)2 = (5c + 2)(2c + b) 136 n .v Phần này gồm một số bài toán hay được thảo luận nhiều trên Diễn đàn Toán học. Bạn đọc có thể vào trực tiếp topic của bài toán đó trên Diễn đàn Toán học, bằng cách click vào tiêu đề của bài toán đó. 7.1 h 4 2 c . m3 + 17..3n o h Bài toán 7.1. Chứng minh rằng với mọi số nguyên dương n, tồn tại một số tự nhiên m sao cho i u .
. m3 + 17 ..3n 4 V Đầu tiên, chúng ta đến với chứng minh đề xuất cho bài toán đầu bài. Chứng minh. Ta sẽ chứng minh bài toán bằng quy nạp. Với n = 1, ta chọn m = 4. Với n = 2, ta chọn m = 1. . Giả sử bài toán đúng đến n = k, hay ∃m ∈ N : m3 + 17..3k Ta chứng minh rằng đối với trường hợp n = k + 1 cũng đúng tức là tồn . tại một số m0 sao cho m03 + 17..3k+1 . . Đặt m3 + 17 = 3k .n ⇒ n 6 ..3. 129 . 7.1. m3 + 17..3n 130  ⇒ n≡2 (mod3) ⇒ n≡1   m3 + 17 ≡ 2.3k  k+1 mod3 m3 + 17 ≡ 3k • Trường hợp 1: m3 + 17 ≡ 2.3k (mod 3k+1 ) Xét: (m + 3k−1 )3 = m3 + m2 3k + m32k−1 + 33k−3 ≡ m3 + m2 3k (mod 3k+1 ) . . (Do k ≥ 2 ⇒ 32k−1 ..3k+1 và 33k−3 ..3k+1 ). Suy ra:  m + 3k−1 3 + 17 ≡ m3 + m2 .3k + 17 ≡ 2.3k + m2 .3k ≡ 0 n .v (mod 3k+1 ) h 4 . . . (vì m 6 ..3 ⇒ m2 ≡ 1 (mod 3) ⇒ 2 + m2 ..3 ⇒ (2 + m2 ).3k ..3k+1 ).
3 . Như vậy, ở trường hợp 1, ta có: m + 3k−1 + 17..3k+1 . m3 2 c 3k 3k+1 ). • Trường hợp 2: + 17 ≡ (mod Xét:  3 m − 3k−1 = m3 −m2 3k +m32k−1 −33k−3 ≡ m3 −m2 3k o h (mod 3k+1 ) . . (Do k ≥ 2 ⇒ 32k−1 ..3k+1 và 33k−3 ..3k+1 ). Suy ra:  m − 3k−1 3 i u + 17 ≡ m3 − m2 3k + 17 ≡ 3k − m2 3k ≡ 0 V (mod 3k+1 )
. . . (vì m 6 ..3 ⇒ m2 ≡ 1 (mod 3) ⇒ 1 − m2 ..3 ⇒ 1 − m2 .3k ..3k+1 ).
3 . Như vậy, ở trường hợp 2 ta có: m − 3k−1 + 17..3k+1 . . . Tóm lại, ta đều tìm được số nguyên t 6 ..3 mà t3 + 17..3k+1 . Ta đã chứng minh được vấn đề đúng trong trường hợp n = k + 1. Theo nguyên lý quy nạp, ta có đpcm. Mấu chốt bài toán này là bổ đề sau: Diễn đàn Toán học Chuyên đề Số học . 7.1. m3 + 17..3n 131 Bổ đề 7.1– Cho a, b, q là các số nguyên thỏa (a; q) = 1 và q > 0. . Khi ấy, luôn tồn tại k ∈ Z sao cho ak ± b..q.  .. Chứng minh. Ta chứng minh đại diện cho trường hợp ak + b.q. Trường hợp còn lại tương tự. Xét A = {1; 2; 3; ...; q} là 1 hệ đầy đủ HĐĐ mod q. Theo tính chất của Hệ thặng dư, ta có tập B = {a; 2a; 3a; ...; qa} cũng là HĐĐ mod q. ⇒ C = {a + b; 2a + b; 3a + b; ...; qa + b} cũng là HĐĐ mod q. . Do đó, tồn tại k ∈ [1; q] sao cho ak + b..q.  n .v Nhận xét. Bài toán đã cho thực chất là yêu cầu tìm 1 số x nguyên sao . cho x + 17..3n và x là lập phương 1 số nguyên. Bổ đề trên đã cho thấy . sự tồn tại của x nguyên để x + 17..3n . Còn việc tìm x để là x là lập phương 1 số nguyên thì ta sẽ dùng phương pháp quy nạp như trên. Đối với 1 người yêu toán, ta phải không ngừng sáng tạo. Ta hãy thử tổng quát bài toán đã cho: h 4 2 c • thay vì m3 , ta thử thay mk với k là số nguyên dương cố định. • thay vì 3n , o h ta thử thay i u pn với p là 1 số nguyên tố. • thay số 17 bởi y ∈ N với y cố định. Kết hợp các thay đổi trên, ta có 1 bài toán "tổng quát" hơn Dự đoán 7.1– Cho p là số nguyên tố. y, k ∈ N và y, k cố định. Khẳng định hoặc phủ định mệnh đề sau V . ∀n ∈ N, ∃x ∈ N : xk + y ..pn (7.1) Ta thử thay một vài giá trị p, k, y vào để thử xem (7.1) có đúng không. Khi thay k = 2, y = 1, p = 3 thì mệnh đề (7.1) trở thành . ∀n ∈ N, ∃x ∈ N : x2 + 1..3n Chuyên đề Số học (7.2) Diễn đàn Toán học . 7.1. m3 + 17..3n 132 Rất tiếc, khi này, (7.2) lại sai!!!. Ta sẽ chứng minh (7.2) sai khi n ≥ 1. Thật vậy, để chứng minh dự đoán 7.1 sai, ta cần có bổ đề sau Bổ đề 7.2– Cho p là số nguyên tố dạng 4k + 3 và a, b ∈ Z. Khi đó . . . a2 + b2 ..p ⇔ (a..p) ∧ (b..p) . . Từ (7.2), suy ra x2 + 1..3. Áp dụng bổ đề 7.2 với p = 3, ta suy ra 1..3: vô lý. n .v . Vậy khi n ≥ 1 thì 6 ∃x ∈ Z : x2 + 1..3n . Không nản lòng, ta thử thêm một vài điều kiện để (7.1) trở nên chặt hơn và đúng. Nếu bạn đọc có ý kiến nào hay, xin hãy gửi vào topic này để thảo luận. Sau khi thêm một số điều kiện, ta có 1 bài toán hẹp hơn nhưng luôn đúng. h 4 2 c Định lý 7.1– Cho p nguyên tố lẻ. y, k ∈ N và y, k cố định. Biết rằng gcd(k, p) = gcd(k, p − 1) = gcd(y, p) = 1. Chứng minh rằng: o h . ∀n ∈ N, ∃x ∈ N : xk + y ..pn i u (7.3) Chứng minh. Trước hết, để chứng minh (7.3), ta cần có bổ đề sau Bổ đề 7.3– Cho p là số nguyên tố lẻ. k nguyên dương thỏa V (k; p) = (k − 1; p) = 1 Khi đó, {1k ; 2k ; ...; (p − 1)k } là HTG modp.  Chứng minh. Gọi g là căn nguyên thủy của p tức là ordp (g) = p − 1. Khi đấy thì g 1 , g 2 , ..., g p−1 lập thành 1 HTG modp và rõ ràng g a1 , g a2 , ..., g ap−1 là HTG modp ⇔ a1 , a2 , .., ap−1 là HĐĐ của p − 1. Với 1 ≤ i ≤ p − 1 thì tồn tại ai để mà i ≡ g ai (mod p) và rõ ràng ai lập thành 1 HTG modp nên hệ 1k , 2k , .., (p − 1)k có thể viết lại là g k , g 2k , ..., g (p−1)k , nó là HTG modp khi và chỉ khi k, 2k, ..., (p − 1)k là hệ thặng dư đầy đủ của p − 1, tức là k nguyên tố cùng nhau với p − 1. Bổ đề được chứng minh.  Diễn đàn Toán học Chuyên đề Số học . 7.1. m3 + 17..3n 133 Quay lại bài toán. Ta chứng minh (7.3) bằng phương pháp quy nạp. Với n = 1, theo bổ đề 7.3 thì ∃x0 ∈ {1; 2; ...; p − 1} : xk0 ≡ −y . (mod p) ⇒ xk0 + y ..p . Giả sử bài toán đúng đếnn hay tồn tại xk + y ..pn . Ta sẽ chứng minh n + 1 cũng đúng hay tồn tại xk0 + y ..pn+1 Thật vậy, từ giả thiết quy nạp suy ra xk + y = pn .q . • Trường hợp 1: q ..p ⇒ đpcm n .v • Trường hợp 2: gcd(q, p) = 1 Khi đó ta chọn x0 = v.pn + x Do đó (7.4) h 4 xk0 + y = (v.pn + x)k + y     1 k−1 k nk k−1 n(k−1) = v .p + .v .p .x + ... + .v.pn .xk−1 + (xk + y) k k (7.5) 2 c o h Dễ dàng chứng minh     1 k−2 n+1 k nk k−1 n(k−1) p | v .p + .v .p .x + ... .v 2 .p2n .xk−2 k k i u Do vậy ta xét   k−1 .v.pn .xk−1 + (xk + y) = k.v.pn .xk−1 + pn .q = pn (k.v.xk−1 + q) k V . Nhận thấy giả sử k.xk−1 ≡ t (mod p) mà gcd(k, p) = 1 và xk + y ..p ⇒ gcd(x, p) = 1 (do gcd(y, p) = 1) suy ra gcd(t, p) = 1 Do đó (k.v.xk−1 +q) ≡ tv+q (mod p) mà từ (7.4) ta đã có gcd(q, p) = 1 . Cho nên luôn tồn tại v thỏa mãn tv + q ..p. Do đó bài toán được khẳng đinh với n + 1. Theo nguyên lý quy nạp, bài toán đã được chứng minh. Chuyên đề Số học Diễn đàn Toán học . 7.1. m3 + 17..3n 134 Chưa dừng lại ở đây, nếu trong (7.3), ta thay k bởi x, ta sẽ được 1 bài toán khác: Định lý 7.2– Cho p nguyên tố lẻ. y ∈ N và y cố định. Biết rằng gcd(y, p) = 1. Khi đó: . ∀n ∈ N, ∃x ∈ N : xx + y ..pn (7.6) Chứng minh. Ta chứng minh bài toán này bằng phương pháp quy nạp. Ta coi định lý 7.1 như 1 bổ đề. Dễ thấy nếu x thỏa (7.6) thì gcd(x; p) = 1. Khi đó, với n = 1, ta xét hệ đồng dư (I)  x ≡ k (mod (p − 1)) x ≡ x0 (mod p) n .v h 4 . trong đó, x0 ; k ∈ N thỏa xk0 + y ..p. Do gcd(p − 1; p) = 1 nên theo định lý Thặng dư Trung Hoa thì hệ (I) luôn có nghiệm x0 . Chọn x = x0 , ta chứng minh x thỏa (7.6) khi n = 1. Thật vậy 2 c o h gcd(x; p) = 1 ⇒ xp−1 ≡ 1 (mod p) ⇒ xk ≡ xx (mod p) ⇒ xx + y ≡ xk + y ≡ xk0 + y ≡ 0 (mod p) Vậy ∃x ∈ N : i u xx . + y ..p. . Giả sử (7.6) đúng đến n − 1, tức là tồn tại x0 để x0 x0 + y ..pn−1 . Theo cách chứng minh quy nạp ở (7.6), ta chọn được xn = apn + x0 . thỏa xx0 + y ..pn . n V Khi đó, dễ nhận thấy xn ≡ x0 (mod pn−1 ). Ta xét hệ đồng dư (II)  X ≡ x0 (mod (pn−1 (p − 1))) X ≡ xn (mod pn ) Do gcd(pn−1 (p − 1); pn ) = 1 nên theo định lý Thặ ng dư Trung hoa, hệ (II) có nghiệm X. Ta chứng minh x = X thỏa (7.6). Thật vậy Do (p − 1)pn−1 = φ(pn ) ⇒ X X ≡ X x0 (mod pn ) (định lý Euler). Diễn đàn Toán học Chuyên đề Số học . 7.1. m3 + 17..3n 135 Mặt khác X x0 ≡ xn x0 (mod pn ) (do cách chọn trong hệ (II)). ⇒ X X + y ≡ x n x0 + y ≡ 0 (mod pn ) Theo nguyên lý quy nạp, bài toán đã được chứng minh.  Mở rộng của bài toán đầu đề vẫn còn nhiều, như tăng thêm điều kiện . . để chặn như (m3 + 17..3n ) ∧ (m3 + 17 6 ..3n+1 ), v.v. Rất mong nhận được ý kiến đóng góp cho việc mở rộng. n .v Lời cảm ơn Rất cảm ơn Nguyen Lam Thinh, Karl Heinrich Marx,nguyenta98, The Gunner đã đóng góp ý kiến và mở rộng cho bài viết này. h 4 2 c o h i u V Chuyên đề Số học Diễn đàn Toán học 7.2. c(ac + 1)2 = (5c + 2)(2c + b) 136 7.2 c(ac + 1)2 = (5c + 2)(2c + b) Bài toán 7.2. Cho 3 số nguyên dương a; b; c thoả mãn đẳng thức: c(ac + 1)2 = (5c + 2b)(2c + b) (7.7) 4 Chứng minh rằng : c là số chính phương lẻ. Nhận xét. Thoạt nhìn vào bài toán, thật khó để tìm 1 phương pháp cho loại này. Nhận xét trong giả thiết ở VP (7.7), thì b xuất hiện với bậc là 2. Thế là ta có 1 hướng nghĩ là dùng tam thức bậc 2 cho bài toán này. Ta không nên chọn c vì bậc của c là 3, không chọn a vì phương trình mới theo a hiển nhiên trở lại (7.7) Chứng minh (Chứng minh 1). n .v h 4 c (ac + 1)2 = (5c + 2b) (2c + b) 2 2 ⇔ 2b2 + 9bc + 10c  − c (ac + 1) = 0 ∆b = 81c2 − 4.2. 10c2 − c (ac + 1)2 = c2 + 8c (ac + 1)2 h i ⇒ ∆b = c c + 8 (ac + 1)2 = x2 , (x ∈ N∗ ) ) d = GCD(c; c + 8(ac + 1)2 ) ⇒ d|8 (ac + 1)2   ⇒ d|8 Đặt d|c ⇒ (ac + 1)2 ; d = 1 c c  • Trường hợp 1: d=8 ⇒ ; + (ac + 1)2 = 1 8 8 h   x 2 i c c c c + 8 (ac + 1)2 = x2 (x ∈ N) ⇔ . + (ac + 1)2 = 8c  8c 8  ⇒ 8|x ⇒ x = 8x2 (x2 ∈ N∗ ) ⇒ . + (ac + 1)2 = x22 8 8  c    = t2 t; p ∈ N∗ 8 ⇒ (t; p) = 1  c + (ac + 1)2 = p2 8  c = 8t2
2 ⇒ t2 + 8t2 a + 1 = p2 2 c o h i u V Mà dễ chứng minh
2
2
2 8t2 a + 1 < t2 + 8t2 a + 1 < 8t2 a + 2
2
2 ⇒ 8t2 a + 1 < p2 < 8t2 a + 2 : mâu thuẫn Diễn đàn Toán học Chuyên đề Số học 7.2. c(ac + 1)2 = (5c + 2)(2c + b) 137 Do đó, d = 8 bị loại. c c  • Trường hợp 2: d=4 ⇒ ; + 2 (ac + 1)2 = 1 4 4 c c 2 ⇒ ; + 2 (ac + 1) là những số chính phương (*) 4 4 . c c Nếu là số chẵn ⇒ + 2 (ac + 1)2 ..2 4  c4 c 2 ; + 2 (ac + 1) = 2: mâu thuẫn. ⇒ 4 4 c c c Do đó, là số lẻ. Mà là số chính phương ⇒ ≡ 1 (mod 4) 4 4 4 Mặt khác, do c chẵn nên ac + 1 là số lẻ ⇒ (ac + 1)2 ≡ 1 (mod 4) c ⇒ + 2 (ac + 1)2 ≡ 1 + 2.1 ≡ 3 (mod 4): vô lý do (*). 4 Do đó, d = 4 bị loại. • Trường hợp 3: d=2 . c c Tương tự tự Trường hợp 2, ta có lẻ ⇒ ≡ 1 (mod 8) 2 2 c chẵn nên ac + 1 lẻ ⇒ (ac + 1)2 ≡ 1 (mod 8) n .v h 4 ⇒ o h 2 c c + 4(ac + 1)2 ≡ 1 + 4.1 ≡ 5 2 i u (mod 8) : vô lý Do đó, d = 2 bị loại. • Trường hợp 4: d=1 Tương tự trường hơp 2, ta có ngay c lẻ và do (c; c + 8(ac + 1)2 ) = 1 nên c là số chính phương. Vậy ta có đpcm.  V Nhận xét. Ta thấy trong bài này, b và c có 1 mối liên quan khá chặt chẽ với nhau nên ta thử giải theo b, c sử dụng kĩ thuật GCD tức là đặt d = GCD(b; c) ta có cách chứng minh thứ 2.  Chứng minh (Chứng minh 2). Đặt d = (b; c) ⇒ Chuyên đề Số học c = dm b = dn  m; n ∈ N∗ (m; n) = 1 Diễn đàn Toán học  7.2. c(ac + 1)2 = (5c + 2)(2c + b) 138 Khi đó 2 (7.7) ⇔ m (dam + 1) = d (5m + 2n) (2m + n) ⇒ d|m (dam + 1)2 ⇒ d|m ⇒ m = dp ⇒ (p; n) = (d; n) = 1 (d; dam + 1) = 1
2 (7.7) ⇔ p d2 ap + 1 = (5dp+ 2n) (2dp + n) ⇒ p| (5dp + 2n) (2dp + n) ⇒ p|5dp + 2n ⇒ p|2n (p; 2dp + n) = 1 (p; n) = 1 ⇒ p|2 ⇒ p ∈ {1; 2} n .v
2 • Trường hợp 1: p=2 , khi đó 2 2ad2 + 1 = (10d + 2n) (4d + n),
2 suy ra 2ad2 + 1 = (5d + n) (4d + n). Nhưng vì (5d + n; 4d + n) = (d; 4d + n) = (d; n) = 1 Cho nên ta phải có  5d + n = x2 (x; y ∈ N∗ , (x; y) = 1) 4d + n = y 2 2ad2 + 1 = xy ⇔ a = h 4 2 c Suy ra d = x2 − y 2 . Mặt khác xy − 1 xy − 1 = 2 2d 2 (x2 − y 2 )2 o h Ta chứng minh 2 x2 − y 2 Thật vậy
2 i u > (x + y)2 > xy − 1 (x + y)2 ≥ 4xy > xy − 1  
2 2 x2 − y 2 − (x + y)2 = (x + y)2 2 (x − y)2 − 1 > 0
2 ⇒ 2 x2 − y 2 > xy − 1 ⇒ a < 1 : Trái gt V Vậy p = 2 bị loại. • Trường hợp 2: p=1 c = d2 , (i) b = dn
2

(7.7) ⇔ d2 ad2 + 1 = 5d2 + 2dn 2d2 + dn
2 ⇔ ad2 + 1 = (5d + 2n) (2d + n)  ⇒d=m⇒ Diễn đàn Toán học (7.8) Chuyên đề Số học