Bổ đề nâng số mũ và ứng dụng

Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 BỔ ĐỀ NÂNG SỐ MŨ VÀ ỨNG DỤNG Trịnh Khắc Tuân Trường THPT Thọ Xuân 5, Thanh Hóa Tóm tắt nội dung Bổ đề nâng số mũ là một công cụ rất hiệu quả, giải quyết nhanh gọn nhiều bài toán số học khó như chia hết,phương trình nghiệm nguyên, chứng minh sự tồn tại. . .Do khuôn khổ bài viết nên các tính chất đơn giản, không trình bày chứng minh ở đây, bạn đọc xem như bài tập nhỏ; các chứng minh công thứcLegendre, định lý Kummer, bổ đề nâng lũy thừa có trong một số tài liệu đã dẫn, chúng tôi không nêu lại. 1 Số mũ đúng Định nghĩa 1.1. Cho p là số nguyên tố, a là số nguyên và α là số tự nhiên. Ta gọi pα là lũy thừa đúng của a và α là số mũ đúng của p trong khai triển của a nếu pα|a và pα+1 - a. Khi đó ta viết pα ‖ a hay vp (a) = α. Ví dụ: Ta có v3 (54) = 3 vì 33|54 và 34 - 54. Từ định nghĩa ta có một số tính chất đơn giản sau. Tính chất 1.1. Với a, b, c là các số nguyên, p là số nguyên tố thì: - vp (ab) = vp (a) + vp (b). - vp (an) = n.vp (a). - min { vp (a) , vp (b) } ≤ vp (a+ b), dấu đẳng thức xảy ra chẳng hạn khi vp (a) 6= vp (b). - vp {gcd (|a| , |b| , |c|)} = min { vp (a) , vp (b) , vp (c) } . - vp {lcm (|a| , |b| , |c|)} = max { vp (a) , vp (b) , vp (c) } . - b|a↔ vp (a) ≥ vp (b). Tính chất của số mũ đúng được sử dụng nhiều trong các bài toán số học như chia hết, chứng minh sự tồn tại hoặc không tồn tại, giải phương trình nghiệm nguyên. . . Sau đây ta xét một số ví dụ. Ví dụ 1.1 (Poland 2016). Cho k, n nguyên dương lẻ lớn hơn 1. Chứng minh rằng nếu tồn tại số tự nhiên a thỏa mãn k|2a + 1, n|2a − 1 thì không tồn tại số tự nhiên b thỏa mãn k|2b − 1, n|2b + 1. Lời giải. Giả sử tồn tại b thỏa mãn. Ta có k | 2a + 1 | 22a − 1 và n | 2a − 1 nên ordk (2) | 2a, ordk (2) | b và ordk (2) - a. Do đó v2 (ordk (2)) = v2 (a) + 1→ 2v2(a)+1 | b→ v2 (a) + 1 ≤ v2 (b). Tương tự 2v2(b)+1 | a −→ v2 (b) + 1 ≤ v2 (a). Mâu thuẫn này chứng tỏ không tồn tại b thỏa mãn. 1 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ví dụ 1.2. Cho a, b, c nguyên dương thỏa mãn c(ca+ 1)2 = (2c+ b) (3c+ b). Chứng minh rằng c là số chính phương. Lời giải. Ta có c(ca+ 1)2 = 6c2 + 5bc+ b2 → c|b2. Gọi p là ước nguyên tố tùy ý của c, ta có vp ( b2 ) ≥ vp (c)→ 2vp (b) ≥ vp (c). (1) Nếu vp (b) ≥ vp (c) thì do gcd (ca+ 1, c) = 1 nên vp (ca+ 1) = 0. Do đó vp (c) = vp (2c+ b) + vp (3c+ b) ≥ 2vp (c), vô lý. Vậy vp (c) > vp (b)→ vp (c) = vp (2c+ b) + vp (3c+ b) ≥ 2vp (b). (2) Từ (1) và (2) suy ra vp (c) = 2vp (b), như vậy mọi lũy thừa trong khai triển ra thừa số nguyên tố của c đều chẵn, tức là c là số chính phương. Ví dụ 1.3 (Greece 2015). Tìm x, y nguyên dương và p nguyên tố sao cho xy3 x+ y = p. Lời giải. Ta có xy3 = p (x+ y)→ x|py, y|px. Do đó với mọi số nguyên tố q 6= p ta có vq (x) ≤ vq (y) ≤ vq (x). Nên vq (x) = vq (y) và ∣∣vp (x)− vp (y)∣∣ ≤ 1. Do đó x = py hoặc x = y hoặc y = px. - Nếu x = py → py4 = p (py+ y) → y3 = p + 1 → p = y3 − 1 = (y− 1) (y2 + y+ 1). Do đó y− 1 = 1, y2 + y+ 1 = p→ y = 2, p = 7, x = 14. - Nếu x = y→ x4 = p.2x → x3 = 2p, mâu thuẫn do v2 ( x3 ) ∈ {1, 2} không chia hết cho 3. - Nếu y = px → p3x4 = p (x+ px)→ p2x3 = 1+ p, vô lý. Vậy (x, y, p) = (14, 2, 7). Ví dụ 1.4 (Turkey MO). Cho n là số nguyên dương thỏa mãn điều kiện: Với mọi a nguyên dương lẻ và nguyên tố cùng nhau với n thì 2n2 ∣∣ an − 1. Chứng minh rằng n là số square - free. (Một số nguyên được gọi là số square - free nếu nó là tích của các số nguyên tố phân biệt) Lời giải. Xét ước nguyên tố p bất kỳ của n và đặt m = vp (n). Nếu p chẵn thì chọn a sao cho a ≡ 5 (mod8) , a ≡ 1 ( mod n pm ) thì dễ thấy v2 ( 2n2 ) = 1+ 2m vàv2 (an − 1) = v2 (a− 1) + v2 (n) = 2+m. Suy ra 1+ 2m ≤ 2+m −→ m ≤ 1. Tương tự với p lẻ. Do đó tất cả số mũ cua p| n đều là 1 nên n là số square - free. Ví dụ 1.5 (Đề đề nghị Olympic 30.4). Gọi A là tập hợp các ước chung của 310. Hai số x, y ∈ A gọi là liên kết với nhau nếu tồn tại k ∈ Z+ sao cho xy| (xk + yk). Hỏi có bao nhiêu cặp có tính thứ tự, không nhất thiết phân biệt (x, y) liên kết với nhau trong A ? Lời giải. Trước hết chứng minh điều kiện cần và đủ để có 2 sốx, y liên kết với nhau là x, y có cùng tập ước nguyên tố. Thật vậy, chiều thuận là hiển nhiên vì a| bk vàb| akchứng tỏ không thể có các ước nguyên tố riêng; chiều đảo thì chỉ cần chọn k đủ lớn để với p là ước nguyên tố củaab thì vp (ab) = vp (a) + vp (b) ≤ kmin { vp (a) , vp (b) } ≤ vp (ak + bk) . Xét sự cómặt của ước nguyên tố 2 trong hai sốa, b: Nếu cùng làmũ 0thì có 1 cách chọn, nếu cùng là mũ lớn hơn 0 thì mỗi số có 10 cách chọn nên tổng cộng có 102+ 1 = 101 cách. Do các ước nguyên tố2, 3, 5 độc lập nhau nên theo nguyên lý nhân có 1013 cặp liên kết nhau. 2 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Định lý 1.1 (Công thức Legendre). Cho plà số nguyên tố, nlà số nguyên dương. Khi đó, ta có: vp (n!) = +∞ ∑ k=1 ⌊ n pk ⌋ . Cách viết khác: vp (n!) = n− sp (n) p− 1 , trong đó sp (n) là tổng các chữ số của n khi viết trong hệ cơ số p. (Bạn đọc có thể xem chứng minh định lý này có thể xem Number Theory: Concepts and ProblemscủaGabriel Dospinescu) Ví dụ 1.6 (USA 2016). Chứngminh rằng với mọi số nguyên dương k, số ( k2 ) !. k−1 ∏ j=0 j! (j+ k)! là số nguyên. Lời giải. Xét số nguyên tố p bất kỳ. Ta cóvp (( k2 ) !. k−1 ∏ j=0 j! (j+ k)! ) = +∞ ∑ i=1 (⌊ k2 pi ⌋ + k−1 ∑ j=0 (⌊ j pi ⌋ − ⌊ j+ k pi ⌋)) Ta chứng minh với m = pi bất kỳ thì ⌊ k2 m ⌋ ≥ k−1∑ j=0 (⌊ j+ k m ⌋ − ⌊ j m ⌋) . Thật vậy⌊ 0 m ⌋ + · · ·+ ⌊ k− 1 m ⌋ + ⌊ k2 m ⌋ ≥ ⌊ k m ⌋ + · · ·+ ⌊ 2k− 1 m ⌋ ⇔ ⌊ 0 m ⌋ + · · ·+ ⌊ k− 1 m ⌋ +⌊ k2 m ⌋ > −1+ ⌊ k m ⌋ + · · ·+ ⌊ 2k− 1 m ⌋ Mà ta dễ có { 0 m } + · · ·+ { k− 1 m } ≤ { k m } + · · ·+ { 2k− 1 m } . Ngoài ra 0 m + · · ·+ k− 1 m + k2 m = k m + · · ·+ 2k− 1 m và ⌊ k2 m ⌋ + 1 > k2 m ta suy ra điều phải chứng minh. Ví dụ 1.7 (Mathematical Reflections S 206). Tìm tất cả các số nguyên n > 1 có thừa số nguyên tố p sao cho vp (n!) ∣∣ n− 1. Lời giải. Viết n = kp, từ công thức Legendre có vp (n!) = k+ ⌊ n p2 ⌋ + · · · ≥ k. Vì thế p = n k > n− 1 k ≥ n− 1 vp (n!) ≥ n− sp (n) vp (n!) = p− 1. Do n− 1 vp (n!) là một số nguyên thuộc (p− 1; p] nên sp (n) = 1, điều này chứng tỏ n lũy thừa của p. Ngược lại, nếun = pk, k ∈ Z+ thì vp (n!) = n− 1p− 1 là ước của n− 1. Định lý 1.2 (Định lý Kummer). Với n ≥ i ≥ 1 nguyên dương và p nguyên tố, khi đóvp ( Cin ) bằng tổng số lần “nhớ” khi thực hiện phép cộng (n− i) và itrong hệ cơ số p. Chứng minh định lý này có thể xem trong cuốn Number Theory: Concepts and Prob- lemscủaGabriel Dospinescu. 3 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ví dụ 1.8 (China 2015). Tìm các số nguyên k sao cho tồn tại vô hạn số nguyên dương n thỏa mãn n+ k - Cn2n. Lời giải. Nếu k = 0 chọn n = 2α với α ≥ 2 nguyên dương bất kỳ, từ định lý Kummer ta có v2 (Cn2n) = 1mà 4 |n+ k . Nếu k = 1 ta có 1 n+ 1 Cn2n = C n 2n − n n+ 1 Cn2n = C n 2n − Cn+12n là số tự nhiên nên (n+ 1) |Cn2n ( 1 n+ 1 Cn2n là số Catalan). Nếu k 6= 0, 1 chọn n = 2α − k với α ≥ 3+ log2 |k| nguyên dương bất kỳ, từ định lý Kummer ta có v2 (Cn2n) ≤ α− 1mà n+ k = 2α. Nếu k 2 |k|, chọn n = p − k từ định lý Kummer ta có vp (Cn2n) = vp ( Cp−k2(p−k) ) = 0→ p = n+ k - Cn2n. Kết luận: mọi số nguyên k 6= 1 đều thỏa mãn điều kiện bài toán. 2 Bổ đề nâng lũy thừa Định lý 2.1. Cho x, y là các số nguyên, n là số nguyên dương,p là số nguyên tố thỏa mãnx p, y p: Nếu n p, x− y ... p thì vp (xn − yn) = vp (x− y). (1) Nếu p 6= 2, x− y ... pthì vp (xn − yn) = vp (x− y) + vp (n).(2) Nếu x, y lẻ và x− y ... 4thì v2 (xn − yn) = v2 (x− y) + v2 (n).(3) Nếu n chẵn, x, y lẻ thìv2 (xn − yn) = v2 ( x2 − y2 2 ) + v2 (n).(4) Nếu n lẻ, x+ y ... p thì vp (xn + yn) = vp (x+ y) + vp (n).(5) Chứngminh định lý trên bạn đọc có thể xem trong [1] (AmirHossein Parvardi: Lifting The Exponent Lemma) hoặc trong cuốn Number Theory: Concepts and Problemscủacác tác giảGabriel Dospinescu, and Oleg Mushkarov. Ví dụ 2.1. Cho Fn = 22 n + 1 là số Fermat thứ n. Chứng minh rằng:22 m+2n ∣∣ FFm−1n − 1, ∀m, n ∈N. Lời giải. Từ(4) có v2 ( FFm−1n − 1 ) = v2 (Fn − 1) + v2 (Fm − 1). Từ v2 (Fm − 1) = 2m, v2 (Fn − 1) = 2n cóv2 ( FFm−1n − 1 ) = 2m + 2n → 2m + 2n| FFm−1n − 1. Ví dụ 2.2. Cho k ∈ Z+. Tìm tất cả các số nguyên dương n sao cho 3k∣∣ 2n − 1. Lời giải. n lẻ không thỏa mãn vì 2n − 1 ≡ 1 (mod3) .Nếun chẵn, đặt n = 2m có v3 (4m − 1) = v3 (m) + 1 ≥ k −→ v3 (m) ≥ k− 1, suy ra m = 3k−1s, s ∈N∗. Ví dụ 2.3. Cho a, n là 2 số nguyên dương,p là số nguyên tố sao cho pn| ap − 1. Chứng minh rằng a ≡ 1 (mod pn−1) . Lời giải. Theo định lý Fermat ta cóa ≡ ap ≡ 1 (mod p), do đóvp (a− 1) = vp (ap − 1)− 1 ≥ n− 1 −→ a ≡ 1 (mod pn−1).(đpcm). 4 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ví dụ 2.4. Tìm a để 4 (an + 1) là lập phương của một số nguyên dương với mọi n ∈ Z+. Lời giải. Nếu a > 1 thì a2 + 1 không thể là lũy thừa của 2 (do a2 + 1 ≡ 1, 2 (mod4)). Chọn p là ước nguyên tố lẻ của a2 + 1. Lấyn = 2m,m lẻ và để ý rằng vp ( 4 ( a2 + 1 )) = vp ( a2 + 1 ) + vp (m), nhưng vp (m) ≡ b (mod3) , b tùy ý. Suy ra, khi a > 1 thì 4 (an + 1) không thể là số lập phương. Với a = 1 thì 4 (an + 1) = 8 = 23thỏa mãn. Ví dụ 2.5. Cho k ∈ Z, k > 1. Chứng minh rằng tồn tại vô hạn số nguyên dương n sao cho n| 1n + 2n + · · ·+ kn. Lời giải. Nếu 1 + k không là lũy thừa của 2, chọn 1 số nguyên tố lẻp, p| 1 + k và lấy n = pm. Khi đó, với mỗi j không chia hết chop, ta có: vp ( jn + (k+ 1− j)n) = vp (k+ 1) + vp (n) ≥ m + 1. Cũng thế, nếu p| j(và bằng cách ấy p| k + 1− j) thì n| pm| pn| jn do đó tổng tron đề bài chia hết cho pm = n. Nếu 1+ k là lũy thừa của 2, lấy một ước nguyên tố lẻ p của k và lặp lại lập luận trên với k− 1 thay vìk. Ví dụ 2.6. Cho p là một số nguyên tố, a vàn là các số nguyên dương. Chứng minh rằng nếu 2p + 3p = an thì n = 1. Lời giải. p = 2, dễ thấy a = 13, n = 1. Xét p > 2, ta có 2p+ 3p ≡ 2 (mod3) nên nó không thể là số chính phương, mà v5 (2p + 3p) = 1+ v5 (p) ≤ 2 −→ v5 (an) = 1 −→ n = 1. Ví dụ 2.7 (VMO 1997). Chứng minh rằng với mỗi số nguyên dương n đều tồn tại k nguyên dương để cho 2n| 19k − 97. Lời giải. Chứng bằng bằng quy nạp. Với n = 1 chọn k = 1. Giả sử khẳng định trên đúng đến n, tức có k để 2n| 19k − 97. Có 2 trường hợp: Nếu v2 ( 19k − 97 ) ≥ n+ 1 thì quy nạp hoàn tất. Nếu v2 ( 19k − 97 ) = n thì t = 2s chẵn, ta có v2 ( 19t − 97) = v2 (192s − 97) = v2 (192 − 1)+ v2 (s) = 3+ v2 (s). Chọn t = 2n−2 thì v2 (s) = n − 3 nên v2 ( 19t − 1) = n. Đặt 19k+2n−2 − 19k = 2nx và19k − 97 = 2ny vớix, y ∈ Z+ và x, y lẻ thì 19k+2n−2 − 97 = 2n (x+ y) chia hết cho2n+1. Theo nguyên lý quy nạp ta có đpcm. Ví dụ 2.8 (Chuyên KHTN 2015). Chứng minh rằng nếu n là số nguyên dương thỏa mãn3n + 4n + 5n| 60n thìn ∈ {1, 2, 3}. Lời giải. Đưa về phương trình nghiệm nguyên 3n + 4n + 5n = 2x.3y.5z (∗) với0 ≤ x ≤ 2n, 0 ≤ y ≤ n, 0 ≤ z ≤ n. Xét các trường hợp: Nếu n lẻ thìv2 (3n + 5n) = v2 (8) = 3 vàv5 (3n + 4n) = 0 nênz = 0. Thử trực tiếpn = 1, n = 3 thỏa mãn nên chỉ xétn ≥ 5. Khi đóv2 (3n + 4n + 5n) = 3vàx = 3. Ta đưa về phương trình 3n + 4n + 5n = 8.3y ≤ 8.3n −→ ( 4 3 )n + ( 5 3 )n ≤ 7. Điều này không đúng, vì theo BĐT Bernoulli thì ( 4 3 )n + ( 5 3 )n > 7với mọi n ≥ 5. 5 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Nếu n chẵn thì n ≥ 2, ta cóv3 (4n + 5n) = 0 vàv2 (3n + 5n) = 1. Đưa (*) về 3n + 4n + 5n = 2.5z. Nếu z = n thì 3n + 4n = 5n → n = 2. Nếuz ≤ n− 1 thì2.5z ≤ 2.5n−1 < VT, không thỏa mãn. Tóm lại, n ∈ {1, 2, 3}. Ví dụ 2.9 (IMO 2019). Tìm các số nguyên dương k vàn sao cho k! = (2n − 1) (2n − 2) . . . (2n − 2n−1). Lời giải. Dễ thấy 2 cặp (n, k) = (1, 1) hoặc (n, k) = (2, 3) thỏa mãn. Đặt A = n−1 ∏ i=1 ( 2n − 2i), và giả sử A = k!, k ≥ 4. Ta có v3 (2t − 1) = 0 nếu t lẻ, v3 ( 2t − 1) = 1+ v3 (t) nếu t chẵn. Lại có: k > v2 (k!) = v2 (A) = 1+ 2+ · · ·+ (n− 1) = n (n− 1) 2 ; k 3 ≤ v3 (k!) = v3 (A) = ⌊n 2 ⌋ + ⌊n 6 ⌋ + · · · < 3 4 n. Suy ra 9 4 n > k > n (n− 1) 2 −→ n ≤ 11 2 , Bằng cách thử trực tiếp ta thấy không tồn tại cặp (n, k) với n, k ∈N, k ≥ 3 thỏa mãn. Tóm lại, có 2 cặp (n; k) thỏa mãn như trên. 3 Bài tập tương tự Bài 3.1. Tìm tất cả các số nguyên dương n để tồn tại các số nguyên dương x, y vàk thỏa mãn gcd (x, y) = 1, k > 1 và3k = xk + yk. Bài 3.2 (Romania 2005). Tìm tất cả các nghiệm nguyên dương của phương trình3x = 2xy+ 1. Bài 3.3. Giả sử a và b là các số thực dương sao cho a − b, a2 − b2, a3 − b3, . . . là các số nguyên dương. Chứng minh rằng a và b là các số nguyên dương. Bài 3.4 (Romania TST 2015). Cho trước số nguyên dương k ≥ 2, khi n là số nguyên dương thay đổi không nhỏ hơn k, trong tập {n− k+ 1, . . . , n} có nhiều nhất bao nhiêu ước nguyên dương của Ckn? Bài 3.5 (Baltic Way 2015). Tìm các số nguyên dương n thỏa mãn v2 ( nn−1 − 1) = 2015. Bài 3.6 (Bosnia and Herzegovina TST 2015). Chứng minh rằng tồn tại vô hạn hợp số n thỏa mãn n|3n−1 − 2n−1. Bài 3.7 (Japan 2015). Tìm các số nguyên dương n thỏa mãn 10n n3 + n2 + n+ 1 là số nguyên. Bài 3.8 (Vietnam TST 2016). Tìm các số nguyên dương a, n với a > 2 thỏa mãn mỗi ước nguyên tố của an − 1 cũng là ước nguyên tố của a32016 − 1. Bài 3.9 (China TST 2009). Cho n là một số nguyên dương và cho a > b > 1 là các số nguyên sao cho b lẻ và bn| an − 1. Chứng minh ab > 3 n n . Bài 3.10 (MEMO 2015). Tìm tất cả các cặp số nguyên dương (a, b) thỏa mãna! + b! = ab + ba 6 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Tài liệu [1] Amir Hossein Parvardi: Lifting The Exponent Lemma. [2] Gabriel Dospinescu, and Oleg Mushkarov. Publisher: XYZ Press: Number Theory: Concepts and Problems [3] https://artofproblemsolving.com/community [4] Andreescu, Titu, Andrica, Dorin, Feng, Zuming:104 Number Theory Problems: From the Training of the USA IMO Team [5] https://diendantoanhoc.net/ 7