Hai bổ đề Lifting trong số học - Lê Phúc Lữ

Chủ đề C. HAI BỔ ĐỀ LIFTING TRONG SỐ HỌC

Hai bổ đề này mà tác giả muốn nhắc đến ở đây chính là Bổ để nâng lũy thừa LTE và bổ đề Hensel (còn gọi là Hensel Lifting, cũng dùng để nâng lũy thừa trong phương trình đồng dư). Cả hai bổ đề này cũng đã từng xuất hiện cách đây rất lâu trong đề thi VMO. Ta nhắc lại sơ lược về hai bổ đề này như sau:

(LTE 1) Với p là số nguyên tố lẻ, xét ,a b là các số nguyên không chia hết cho p nhưng p a b|  . Khi đó, với mọi n nguyên dương thì

( ^{n n}) ( ) ( ).

p p p

v a b v a b v n

Đặc biệt, khi n lẻ, ta còn có v a_p( ⁿbⁿ)v a b_p(  ) v n_p( ).

(LTE 2) Với p2, xét ,a b lẻ mà 4 |a b thì với mọi số nguyên dương n, ta có

2( ^{n n}) 2( ) 2( ).

v a b v a b v n

Nếu n chẵn, áp dụng công thức trên cho a b², ² vì ta luôn có 4 |a²b² với ,a b lẻ:



^{2 /2 2 /2}



^{2 2}

2( ^{n n}) 2 ( )ⁿ ( )ⁿ 2( ) 2( / 2) v a b v a  b v a b v n .

(Hensel) Cho đa thức P x( ) hệ số nguyên và số nguyên tố p. Giả sử có r số nguyên

 

1, 2, , _r 1;

x x x  p thỏa mãn ( )_i 0(mod )

P x  p và P x( )_i 0 (mod )p với mọi i1, 2, , .r

Khi đó, với mọi số nguyên dương k, tồn tại đúng r số nguyên dương với 1 x p^k sao cho P x( ) chia hết cho p^k.

Ý tưởng mấu chốt để chứng minh bổ đề này là dựa vào tính chất tiếp tuyến:

2

0 0 0

( ) ( ) ( ) ( )(mod )

P x P x  x x P x p với mọi p nguyên tố, các số x x, ₀ và p x| x₀.

Chứng minh tính chất này dễ dàng bằng khai triển Taylor

2

0 0

0 0 0

( )

( ) ( ) ( ) ( )

1! 2!

x x x x

P x P x   P x   P x 

và chú ý rằng

( )( )

! Pk x

k  với mọi x vì đạo hàm cấp _k có các số hạng chia hết cho k!.

Bạn Trần Hoàng Anh, SV trường ĐH KHTN Hà Nội cũng đã chỉ ra được mối liên hệ giữa hai bổ đề trên. Tác giả bài viết sẽ giới thiệu nội dung đó trong một dịp khác.

Tiếp theo, ta xét hai bài toán trong đề VMO trước đây có dùng hai bổ đề trên:

Bài 1. (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 2 |19^{n k}97.

Lời giải. Quy nạp theo n. Với n1 thì chọn k0.

Giả sử khẳng định đúng đến n, tức là ta đã có k để 2 |19^{n k} 97. Có hai trường hợp xảy ra:

- Nếu v₂(19^k97) n 1 thì quy nạp hoàn tất.

- Nếu v₂(19^k 97)n thì với t2s chẵn, ta có

2 2

2(19^t 1) 2(19 ^s 1) 2(19 1) 2( ) 3 2( ).

v  v  v  v s  v s

Chọn t2^n2 thì v s₂( ) n 3 nên v₂(19^t  1) n.

Đặt 19^k2n2 19^k 2ⁿx và 19^k 97 2ⁿ y với ,x y ^ và x y, lẻ thì rõ ràng

2 2

19^{k n} 972 (ⁿ xy) chia hết cho 2^n1. Theo nguyên lý quy nạp, ta có đpcm.

Bài 2. (VMO 2000) Xét đa thức P x( )x³153x²111x38. Chứng minh rằng trên [1;3²⁰⁰⁰], có đúng 9 số nguyên dương a sao cho 3²⁰⁰⁰| ( ).P a

Thay vì giải quyết bài toán này, trong điều kiện không dùng máy tính, ta đổi bằng bài toán sau với cùng tính chất của các hệ số.

Bài 3. Xét đa thức P x( )x³3x²6x4. Hỏi trên miền 1;3²⁰¹⁷ thì có bao nhiêu số a để ( )

P a chia hết cho 3²⁰¹⁷?

Lời giải. Ta thấy P x( )3x²6x6 không thỏa mãn điều kiện của bổ đề Hensel, bởi vậy nên ở đây, ta sẽ dùng một mẹo nhỏ.

Dễ thấy rằng 3 | ( )P a  a 1(mod 3), ta đặt a3k1 thì k[0;3²⁰¹⁶1], thay vào

3 2 3

( ) (3 1) (3 1) 3(3 1) 6(3 1) 4 27 9

P a P k  k  k  k   k  k. Do đó 3²⁰¹⁷| ( )P a khi và chỉ khi 3²⁰¹⁵| (3k³k).

Xét hàm số Q k( )3k³k thì Q k( )9k²1 không chia hết cho 3 với mọi k; trên miền [0; 2]

thì có đúng 1 số k sao cho 3 |Q k( ) nên theo bổ đề Hensel thì trên mỗi miền

2015 2015 2015 2015 2016

0;3 1 , 3 ; 2 3 1 , 2 3 ;3 1

          

     ,

thì có đúng một số k sao cho 3²⁰¹⁵| ( )Q k . Vậy nên có đúng 3 số k thỏa mãn đề bài.

Ở bài VMO 2000, bằng phép đặt tương tự, ta đưa về

3 2

( ) (3 1) 27( 52 22 3)

P a P k  k  k  k .

Đến đây, bài toán giải quyết một cách hoàn toàn tương tự (nhưng cho số hơi lớn, khó tính toán).

Bên dưới là một số bài toán áp dụng nhẹ nhàng cho bổ đề Hensel:

Bài 4. (KHTN 2011) Chứng minh rằng với mỗi số nguyên dương n, tồn tại duy nhất số nguyên dương x[1;5 ]ⁿ sao cho 5 |ⁿ x³ x 1.

Gợi ý. Bài toán trên là hệ quả trực tiếp của bổ đề vì nếu xét P x( )x³ x 1 thì (3) 0(mod 5), (3) 0

P  P  theo mod 5.

Bài 5. Cho đa thức P x( )x³4x²6x c với ^c



^{1, 2, , 2017}



. Hỏi có tất cả bao nhiêu số c sao cho ứng với mỗi giá trị c đó, số lượng x 1;7²⁰¹⁷ để cho 7²⁰¹⁷| ( )P x là nhiều nhất?

Gợi ý. Vẫn theo ý tưởng Hensel. Thử các số x1, 2,3, 4,5, 6, 7, ta thấy với c4(mod 7) thì phương trình đồng dư sẽ có nhiều nghiệm nhất. Đếm được 288 số c.

Quay lại bổ đề LTE, ta xét hai bài toán rất thú vị bên dưới:

Bài 6. (KHTN 2015) Chứng minh rằng nếu n là số nguyên dương thỏa mãn 3ⁿ4ⁿ5 | 60^{n n}

thì ^n



^{1, 2,3}



^.

Lời giải.

Đưa về phương trình nghiệm nguyên 3ⁿ4ⁿ5ⁿ 2 3 5^x ^{y z} với 0 x 2 , 0n  y n, 0 z n. Xét hai trường hợp:

(1) Nếu n lẻ thì v₂(3ⁿ5 )ⁿ v₂(8)3 và v₅(3ⁿ4 )ⁿ 0 nên z0. Thử trực tiếp thấy n1,n3 thỏa mãn nên chỉ xét n5. Khi đó v VT₂( )3 và x3.

Ta đưa về phương trình 3 4 5 8 3 8 3 ^{4 5} 7

3 3

n n

n n n   y   n          .

Điều này sai theo BĐT Bernoulli vì ^{4 5} 7

3 3

n n

    

   

    với mọi n5.

(2) Nếu n chẵn thì n2, xét v₃(4ⁿ5 )ⁿ 0 và v₂(3ⁿ5 ) 1ⁿ  . Ta đưa về 3ⁿ4ⁿ5ⁿ  2 5^z.

Nếu zn thì 3ⁿ4ⁿ 5ⁿ nên n2. Nếu z n 1 thì 2 5 2 5 ^{1 2} 5 5

z n n

 VT

      , không thỏa.

Tóm lại, ta có ^n



^{1, 2,3}



^.

Bài 7. (Thổ Nhĩ Kỳ 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ì 2n² |aⁿ1. Chứng minh rằng n là số square-free.

Lời giải.

Xét ước nguyên tố p bất kỳ của n và đặt mv n_p( ). Nếu p chẵn thì chọn a sao cho 5(mod 8), 1(mod n_m)

a a

  p thì dễ thấy

2

2(2 ) 1 2

v n   m và v a₂( ⁿ 1) v a₂(  1) v n₂( ) 2 m. Suy ra 1 2 m 2 m hay m1.

Tương tự với p lẻ. Do đó, tất cả mũ của p n| đều là 1 nên n square-free.

Bài 8. Cho biết rằng với n nguyên dương thì ( !) ^{( )} 1

p p

n s n

v n p

 

 trong đó s n_p( ) là tổng các chữ số của n trong hệ p- phân; hãy giải các bài toán sau.

a) Cho , ,a b c là các số nguyên dương và ! !| !a b c . Chứng minh rằng 2^{a b c  2}c².

b) Với n là số nguyên dương chẵn, đặt ^{1 1 1}

1!( 1)! 3!( 3)! ( 1)!1!

an

n n n

   

   .

Tìm tất cả các số nguyên dương n sao cho 2^x a_n(2y1) có nghiệm nguyên dương ( ; ).x y Gợi ý.

a) Tính v₂ hai vế ! !| !a b c , ta có v a₂( !)v b₂( !)v c₂( !) hay a s a ₂( ) b s b₂( ) c s c₂( ). Với mọi n, ta có s n₂( )log ( ) 1.₂ n  Suy ra

2

2 2 2 2 2 2

2 ( ) ( ) ( ) 2 log ( ) log ( ) log ( ).

a b c   s a s b s c   a  b  c

Do đó 2^{a b c  2} c².

b) Thu gọn biểu thức đã cho, ta được 2 1

!

n

an

n

  .

Dùng hàm định giá v n₂( !) n s n₂( ), ta thấy tất cả các số cần tìm là n chẵn, n6 và n không phải là lũy thừa của 2.

Cuối cùng, xin đề cập đến một bài toán có xuất hiện trong đề đề nghị Olympic 30/4 của các tỉnh phía Nam. Đề bài đúng nhưng lời giải trong đáp án bị sai. Bài toán này có liên quan đến số mũ đúng chứ không cần dùng LTE.

Bài 9. (Đề nghị Olympic 30/4) Gọi A là tập hợp các số nguyên dương không vượt quá 100. Hai số ,x yA gọi là liên kết với nhau nếu tồn tại k ^ sao cho xy| (x^k y^k).Hỏi có bao nhiêu cặp số ( , )x y liên kết với nhau trong A?

Lời giải đưa điều kiện của x y, liên kết về điều kiện x y, phải có dạng (p^,p^) với ,  . Lập luận như sau: đặt d gcd( , )x y và xdx y₁, dy₁; vì gcd( ,x y_{1 1}) 1 nên d phải nguyên tố cùng nhau với một trong hai số x y₁, ₁. Khẳng định này là sai, chẳng hạn chọn x20,y50 thì

1 1

10, 2, 5.

d  x  y  Ta đổi tập hợp A lại cho dễ đếm và xét bài toán sau:

Bài 10. Gọi A là tập hợp các ước dương của 30 .¹⁰ Hai số ,x yA gọi là liên kết với nhau nếu tồn tại k ^ sao cho xy| (x^k y^k).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.

Ta sẽ chứng minh điều kiện cần và đủ để có hai số x y, liên kết là x y, có cùng tập ước nguyên tố.

Thật vậy, chiều thuận hiển nhiên vì |a b^k và |b a^k chứng tỏ ,a b 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ủa ab thì

 

( ) ( ) ( ) min ( ), ( ) ( ^{k k})

p p p p p p

v ab v a v b k v a v b v a b . Xét sự có mặt của ước nguyên tố 2 trong hai số ,a b:

Nếu cùng là mũ 0 thì 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ó 10² 1 101 cách.

Do các ước nguyên tố 2,3,5 độc lập nhau nên nguyên lý nhân, ta đếm được có tất cả

2 3 3

(10 1) 101 cặp liên kết nhau.