Ứng dụng của Hàm định giá p adic trong giải toán Số học

MỘT SỐ TÍNH CHẤT VÀ ỨNG DỤNG CỦA HÀM ĐỊNH GIÁ P -ADIC

Dương Thái Bảo

Giáo viên Tổ Toán Tin - Trường THPT Chuyên Nguyễn Quang Diêu Email: kaiba.datviet@gmail.com

Tóm tắt nội dung. Mỗi số tự nhiên luôn được biểu diễn thành tích các số nguyên tố (phân tích tiêu chuẩn). Đây có thể được xem như một ý tưởng trong việc giải quyết các bài toán của số học: xét trên P rồi mới xét trên N. Từ điều này, đôi khi tập số nguyên tố P có thể được xem như “cơ sở” để hình thành nên tập số tự nhiên N. Vì thế công cụ định giá p-adic tỏ ra rất hữu dụng, vì nó là công cụ để “đo” số mũ của một số nguyên tố trong phân tích tiêu chuẩn của một số tự nhiên - thậm chí là một hữu tỉ.

Trong chuyên đề này, chúng ta sẽ nghiên cứu một số tính chất và ứng dụng của hàm định giá p-adic.

Trong suốt chuyên đề này tôi sẽ có một số kí hiệu - P là tập số nguyên tố,

- FLT: định lí Fermat nhỏ.

- CNO: China National Olympiad.

- ARO: All Russia Olympiad.

- AOPS: Art of problem solving.

1 Một số tính chất của hàm định giá p-adic

Định nghĩa 1.1. Cho số nguyên tố p cố định. Khi đó ánh xạ v_p : Q ^→ Z được định nghĩa: nếu n∈N^≥1 thì v_p(n) là số nguyên dương k lớn nhất sao cho p^k |n và v_p(0) =∞, ngược lại n = a

b ∈ Q^\N thì v_p(n) = v_p(a)−v_p(b). Khi đó v_p(n) được gọi là định giá p-adic của n, còn v_p được gọi là hàm định giá p-aidc.

Tiếp theo chúng ta sẽ xét một số tính chất cơ bản của hàm số học này.

Tính chất 1.2. (i) v_p(n)≥1 khi và chỉ khi p|n. (ii) vp(n)< n với mọi số nguyên tố p.

(iii) Nếu n >1 thì n=p^vp(n).m trong đóng (m, p) = 1. (iv) Với mọi số tự nhiên n > 1 thì

n =Y

p|n

p^vp(n).

(v) a là số chính phương khi và chỉ khi v_p(a) là số chẵn với mọi số nguyên tố p. (vi) Với mọi số nguyên a, b ta có

vp(ab) =vp(a) +vp(b) và vp(a+b)≥min{vp(a), vp(b)}.

Nếu v_p(a)6=v_p(b) thì dấu “=” xảy ra.

Chứng minh. Nếu n = p^α₁¹p^α₂². . . p^α_k^k trong đó pi ∈ P và αi ≥ 1. Khi đó vpi(n) = αi, từ cách thay đổi định nghĩa này ta dễ dàng chứng minh được các ý trên.

Với (i), chúng ta có ý tưởng: để chứng minh p| n thì chúng ta chỉ cần chứng minh v_p(n)≥1. Tổng quát lên chúng ta có tính chất sau

Tính chất 1.3. (i) Nếu a, b là hai số nguyên thì a|b nếu và chỉ nếu v_p(a)≤v_p(b) với mọi số nguyên tố p.

(ii) Cho a, n là hai số nguyên dương. Khi đó a là lũy thừa bậc n của một số nguyên nếu và chỉ nếu v_p(a)≡0 (mod n) với mọi số nguyên tố p.

Chứng minh. (i) Ta có a | b khi và chỉ khi với mọi số nguyên tố p thì lũy thừa của p trong a phải bé hơn hoặc bằng lũy thừa của p trong b.

(ii) Giả sử a = bⁿ với b là số nguyên dương. Khi đó với mọi số nguyên tố p thì v_p(a) = v_p(bⁿ) = nv_p(b) ≡ 0 (mod n). Ngược lại với mỗi số nguyên tố p, nếu v_p(a) ≡ 0 (mod n)thì tồn tại số nguyên dương q_p sao cho v_p(a) =q_pn. Lúc này ta đặt b=Q

qp>0p^qp,

khi đó hiển nhiên a=bⁿ.

Việc lấy số mũ của một thừa số nguyên tố trong số nguyênn làm chúng ta liên tưởng đến việc tìm ước chung lớn nhất và bội chung nhỏ nhất của hai số nguyêna, b. Dưới đây là tính chất của hàm định giá p-adic và (a, b),[a, b].

Tính chất 1.4. Với hai số nguyên a, b thì

v_p(a, b) = min{v_p(a), v_p(b)} và v_p([a, b]) = max{v_p(a), v_p(b)}.

Việc chứng minh tính chất này khá dễ dàng. Từ tính chất này chúng ta có kết quả sau: với hai số nguyên a, b nguyên tố cùng nhau, nếu ab là lũy thừa bậc n của một số nguyên khi và chỉ khi a và b cũng là lũy thừa bậc n của hai số nguyên.Thật vậy, do (a, b) = 1 nên 0 = v_p(a, b) = min{v_p(a), v_p(b)} hay v_p(a) = 0 hoặc v_p(b) = 0. Sử dụng tính chất 1.3, ab là lũy thừa bậc n của một số nguyên khi và chỉ khi v_p(ab)≡0 (mod n), suy ra v_p(a) +v_p(b)≡0 (mod n). Do đó v_p(a)≡0 (mod n) hoặc v_p≡0 (mod n).

Tiếp theo chúng xét đến hai định lí của Legendre và Kummer về giá trị p-adic của n!.

Định lí 1.5. Với mọi số tự nhiên n và số nguyên tố p thì

v_p(n!) = n

p

+ n

p²

+. . . (1.1)

=n−sp(n)

p−1 . (1.2)

trong đó s_p(n) là tổng các chữ số của n theo cơ số p. Chứng minh. Ta có

vp(n!) =vp(1.2. . . n) =vp(1) +vp(2) +· · ·+vp(n).

Trong các số tự nhiên từ 1 đếnn có đúngh

n p

isố là bội của p, h

n p²

isố là bội củap²,. . . Khi đó số các số tự nhiên từ 1 đến n chỉ chia hết cho p là . Do đó

v_p(n!) = n

p

− n

p²

+ 2 n

p²

− n

p³

+ 3 n

p³

− n

p⁴

+. . .

Thu gọn thì được (1.1).

Giả sử n=a_ta_t−1. . . a₁a_0p với a_i∈ {0,1, . . . , p−1} và a_t6= 0. Khi đó n

p

=

a_tp^t−1+· · ·+a₁+a₀ p

=a_tp^t−1+· · ·+a₁ n

p²

=

atp^t−2+· · ·+a2+a₁ p +a₀

p²

=atp^t−2+· · ·+a2

. . . n

p^t

=

a_t+ a_t−1

p +· · ·+ a₁ p^t−1 + a₀

p^t

=a_t

vì

0≤ a_i

p +· · ·+a₁ pⁱ + a₀

pⁱ⁺¹ ≤ p−1

p +p−1

p² +· · ·+p−1

pⁱ⁺¹ = pⁱ⁺¹−1

pⁱ⁺¹ <1. (1.3) Cộng các đẳng thức trên theo vế ta được

v_p(n!) =a_t(p^t−1+· · ·+ 1) +a_t−1(p^t−2+· · ·+ 1) +· · ·+a₂(p+ 1) +a₁

=a_tp^t−1

p−1 +a_t−1p^t−1−1

p−1 +· · ·+a₂p²−1

p−1 +a₁p−1 p−1

=a_tp^t−a_t+a_t−1p^t−1−a_t−1+· · ·+a₂p²−a₂+a₁p−a₁ p−1

=n−s_p(n) p−1

Vậy ta có điều phải chứng minh.

Tính chất 1.6. Cho số tự nhiên n và số nguyên tố p. Nếu n = a_ta_t−1. . . a₁a_0p với a_i ∈ {0,1, . . . , p−1} và a_t 6= 0 thì

t =

log_pn

(1.4) Chứng minh. Ta có

p^t ≤n=a_tp^t+· · ·+a₁p+a₀

≤(p−1)p^t+· · ·+ (p−1)p+p−1

=p^t+1−1

<p^t+1

suy ra t≤logn < t+ 1. Vì thế t=

log_pn

.

Áp dụng kĩ thuật (1.3), chúng ta chứng minh được tính chất sau Tính chất 1.7. Với mọi số nguyên dương n >1 và số nguyên tố p, ta có

n

p −1< vp(n!)< n

p−1. (1.5)

Tiếp theo chúng ta bàn về giá trị p-adic của ⁿ_k .

Tính chất 1.8. Cho các số nguyên n≥k ≥0 và p là số nguyên tố. Khi đó

p^vp(ⁿ_k)≤n. (1.6)

Chứng minh. Áp dụng công thức Legendre (1.3) ta có v_p

n k

=v_p(n!)−v_p(k!)−v_p((n−k)!) (1.7)

=X

j≥1

n p^j

− k

p^j

−

n−k p^j

. (1.8)

Ta có bổ đề sau: với mọi số thực x, y thì

[x+y]−[x]−[y]∈ {0,1}.

Thật vậy, đặt r =x−[x], s=y−[y], r, s∈[0; 1), suy ra [x+y]−[x]−[y] = [r+s].

Trở lại bài toán, mỗi số hạng của tổng trên hoặc bằng 1 hoặc bằng 0 và nếu p^j > n

thì

n p^j

= k

p^j

=

n−k p^j

= 0.

Mặt khác sử dụng (1.4), tổng trên có đúng [log_pn] số hạng, vậy v_p

n k

≤

log_pn .

Ở đẳng thức (1.7), nếu ta sử dụng định lí Kummer (1.2) thì ta được

v_p n

k

= s_p(k) +s_p(n−k)−s_p(n)

p−1 . (1.9)

Tương tự ở đẳng thức (1.8) thì khi n =p và 1≤k ≤p−1thì tổng này chỉ có một số hạng ứng với j = 1 và

p p

− k

p

−

p−k p

= 1. Do đó v_p

p k

= 1. (1.10)

Khi nhắc đến hàm định giá p-adic không thể không nhắc đến bổ đề về số mũ đúng (Lifting the exponent lemma - LTE). Đây là một trong những bổ đề được sử dụng nhiều trong số học.

Định lí 1.9. Cho a, blà hai số nguyên, n là số nguyên dương và p là ước nguyên tố của a−b. Khi đó

v_p(aⁿ−bⁿ)≥v_p(a−b) +v_p(n) hay v_p

aⁿ−bⁿ a−b

≥v_p(n). (1.11)

Chứng minh. Đặt t = vp(a−b), s = vp(n). Ta sẽ chứng minh rằng p^t+s | aⁿ −bⁿ. Thật vậy, do p^t |a−b và

a^p = (a−b+b)^p= (a−b)^p+ p

1

(a−b)^p−1b+· · ·+ p

p−1

(a−b)b^p−1+b^p nên

a^p−b^p = (a−b)

(a−b)^p−1+p(a−b)^p−2b+

· · ·+ p

p−2

(a−b)b^p−2+pb^p−1

. (1.12) Nhận thấy rằng mọi số hạng trong tổng còn lại của vế phải đều chia hết cho p, kéo theo p^t+1 | a^p−b^p. Tiếp tục quá trình lập luận này thì dẫn đến p^t+2 | (a^p)^p −(b^p)^p = a^p2 −b^p2, . . . , p^t+s |a^ps−b^ps. Mặt khác thì p^s |n nên ta có p^t+s |aⁿ−bⁿ. Tiếp theo chúng ta sẽ bàn về một số kết quả của định lí trên trong trường hợp dấu

“=” xảy ra.

Định lí 1.10 (Lifting the exponent lemma). Cho p là số nguyên tố lẻ và a, b không chia hết cho p nhưng p|a−b. Khi đó với mọi số tự n≥1 thì

v_p(aⁿ−bⁿ) =v_p(a−b) +v_p(n) (1.13) Chứng minh. Ở đây chúng ta sẽ sử dụng ý tưởng nếu (1.13) đúng với hai số tự nhiên m, n thì nó cũng đúng với mn. Thật vậy, ta có

v_p(a^mn−b^mn) =v_p((aⁿ)^m−(bⁿ)^m) = v_p(aⁿ−bⁿ) +v_p(m)

=v_p(a−b) +v_p(n) +v_p(m) =v_p(a−b) +v_p(mn). (1.14) Do đó ta chỉ cần chứng minh (1.13) đúng với n =q (q là số nguyên tố) là được.

Trước tiên ta nhận thấy q =p thì theo (1.12), các số hạng trong tổng còn lại của vế phải đều chia hết p² (do p≥3) trừ pb^p−1. Suy ra

v_p

(a−b)^p−1+p(a−b)^p−2b+· · ·+ p

p−2

(a−b)b^p−2

≥26= 1 =v_p(pb^p−1).

Theo ý (vi) của tính chất 1.2 thì v_p

(a−b)^p−1+p(a−b)^p−2b+· · ·+ p

p−2

(a−b)b^p−2+pb^p−1

= 1

Nếu n là số nguyên dương lẻ, áp dụng định lí trên cho a và −b thì ta được hệ quả sau

Hệ quả 1.11. Cho p là số nguyên tố lẻ và a, b là hai số nguyên không chia hết cho p nhưng p|a+b. Khi đó với mọi số nguyên dương lẻ n thì

v_p(aⁿ+bⁿ) = v_p(a+b) +v_p(n). (1.15)

Hệ quả 1.12. Cho p là số nguyên tố lẻ và a, b là hai số nguyên không chia hết cho p nhưng p|a+b. Khi đó với mọi số nguyên dương lẻ n và p|n thì

v_p(aⁿ+bⁿ) = v_p(a^np +b^np) +v_p(n). (1.16) Chứng minh. Vì p | n nên tồn tại d sao cho n = pd. Lưu ý rằng (p, a) = (b, p) = 1 nên theo định lí Ferma thì

aⁿ = (a^d)^p ≡a^d (mod p), bⁿ = (b^d)^p ≡b^d (mod p) suy ra

a^d+b^d ≡0 (mod p).

Theo (1.15) thì ta có

v_p(aⁿ+bⁿ) = v_p((a^d)^p+ (b^d)^p) =v_p(a^d+b^d) +v_p(n).

Trong các kết quả trên, chúng ta chỉ mới xét đến p là số nguyên tố lẻ. Ở trường hợp p= 2 thì chúng ta có định lí sau

Định lí 1.13. Cho a, b là hai số nguyên lẻ và n là số nguyên dương chẵn. Khi đó

v2(aⁿ−bⁿ) = v2

a²−b² 2

+v2(n). (1.17)

Chứng minh. Đặt n= 2^tm với m là số lẻ. Khi đó

aⁿ−bⁿ = (a^m−b^m)(a^m+b^m)(a^2m+b^2m). . .(a^2t−1m+b^2t−1m).

Chú ý rằng với a, b lẻ thì a²ⁱ+b²ⁱ ≡2 (mod 4) trong đó i≥1. Điều này dẫn đến v2(a^2im−b^2im) = v2(a²ⁱ+b²ⁱ) +v2(Mi) =v2(a²ⁱ +b²ⁱ) = 1,

trong đó M_i là tổng của m số lẻ nên M_i lẻ với mọi i≥1. Từ đây ta có v₂(aⁿ−bⁿ) = v₂(a^2m−b^2m) +t−1.

Mặt khác thì v₂(a^2m−b^2m) = v₂(a²−b²) +v₂(M) = v₂(a²−b²), kéo theo v₂(aⁿ−bⁿ) =v₂(a²−b²) +t−1

=v₂

a²−b² 2

+v₂(n).

Xét n là số lẻ thì bằng kĩ thuật giống như trên chúng ta có

v₂(aⁿ−bⁿ) = v₂(a−b). (1.18) Để có một kết quả cho n bất kì trong trường hợp p= 2 này, chúng ta đòi hỏi phải tăng giả thiết cho a, b. Đó là 4|a−b.

Hệ quả 1.14. Cho a, blà hai số nguyên lẻ bất kì thỏa 4|a−b. Khi đó với mọi số nguyên dương n thì

v₂(aⁿ−bⁿ) =v₂(a−b) +v₂(n). (1.19) Chứng minh. Nếu n lẻ thì sử dụng (1.18) ta có ngay điều phải chứng minh.

Nếu n chẵn thì sử dụng định lí 1.13, ta có v₂(aⁿ−bⁿ) =v₂

a²−b² 2

+v₂(n)

=v₂(a−b)−v₂

a+b 2

+v₂(n).

=v₂(a−b) +v₂(n).

do x≡y (mod 4), suy ra x+y ≡2y (mod 4), mà 2y≡2 (mod 4) nên v₂ ^a+b₂

= 0.

2 Áp dụng của hàm định giá p-adic vào chứng minh

Ví dụ 2.1 (Định lí Euler). Nếu n là một số nguyên dương thì với mọi số nguyên a nguyên tố với n thì

a^ϕ(n) ≡1 (mod n).

Giải. Điều cần phải chứng minh tương đương với

a^ϕ(n) −1≡0 (mod n)⇔v_p(n)≤v_p(a^ϕ(n)−1) với mọi số nguyên tố p.

Nếu p- ⁿ thì hiển nhiên đúng. Xétp|n, suy ra (a, p) = 1. Theo định lí Ferma nhỏ thì a^p−1−1≡0 (mod p)⇔p|a^p−1−1.

Cần chú ý rằng nếu n=p^α₁¹p^α₂². . . p^α_t^t thì

ϕ(n) =p^α₁¹⁻¹p^α₂²⁻¹. . . p^α_t^t−1

t

Y

i=1

(p_i−1).

Do đó v_p(n) =v_p(ϕ(n)) + 1 và nếu p |n thì p−1| ϕ(n). Kết hợp với bổ đề LTE cho hai số a^p−1,1 ta có

vp

(a^p−1)

ϕ(n) p−1 −1

=vp(a^p−1−1) +vp

ϕ(n) p−1

=v_p(a^p−1−1) +v_p(ϕ(n))−v_p(p−1)

=vp(a^p−1−1) +vp(ϕ(n))

≥v_p(ϕ(n)) + 1

=v_p(n)−1 + 1

=v_p(n).

Ví dụ 2.2 (Erd¨os-Tauran). Cho {an} là dãy tăng vô hạn các số nguyên dương. Chứng minh rằng với mọi N, chúng ta có tìm i 6=j sao cho a_i+a_j có một ước nguyên tố lớn hơn N.

Chứng minh. Từ điều kiện của đề bài ta suy ra a_n ≥n với mọi n ≥1. Chọn trước số tự nhiên N, ta gọi p₁, . . . , p_k là các số nguyên tố không vượt quá N. Giả sử ngược lại, mọi i6=j thì tất cả các ước nguyên tố của a_i+a_j thuộc tập {p₁, . . . , p_k}. Khi đó ta chọn được số tự nhiên d sao cho d > a_i−a_j với mọi 1≤j < i≤k+ 1 và n > (p₁p₂. . . p_k)^d. Điều này dẫn đến a_n+a_i> n >(p₁p₂. . . p_k)^d với mọi 1≤i≤k+ 1. Do các ước nguyên tố củaa_n+a_i đều thuộc {p₁, . . . , p_k} nên với mỗi i thì tồn tạik_i∈ {1, k} sao cho v_pki(a_n+a_i)> d. Theo nguyên lý Dirichlet thì tồn tạiki=kj với i > j. Suy ra vp_ki(an+ai)> d, vp_kj(an+aj)> d, kéo theo

v_pki(a_i−a_j) = v_pki(a_n+a_i)−v_pki(a_n+a_j)> d.

Điều này mâu thuẫn với d > a_i−a_j.

Từ ý tưởng chứng minh cho bài toán này, chúng ta đi đến một bài toán có cách giải tương tự: (IMO shortlist 2011) Gọi d₁, d₂, . . . , d₉ là các nguyên phân biệt, chứng minh rằng tồn tại số nguyên x đủ lớn để (x+d₁)(x+d₂). . .(x+d₉) có ước nguyên tốn lớn hơn 20.

Chúng ta có thể tổng quát bài toán: Cho p₁, p₂, . . . là dãy tăng tất cả các số nguyên tố và n là một số nguyên dương. Gọi d₁, . . . , d_n là các số nguyên. Chứng minh rằng tồn tại số nguyên x đủ lớn để Qn

i=1(x+d_i) có ước nguyên tố lớn hơn p_n.

Ví dụ 2.3 (China TST 2016). Một điểm được gọi là điểm hữu tỉ nếu các tọa độ của nó đều là số hữu tỉ. Với mỗi số nguyên dương n cho trước, tồn tại hay không một cách sử dụng n màu để tổ tất cả các điểm hữu tỉ sao cho

(i) mỗi điểm tô một màu,

(ii) trên một đoạn thẳng hữu tỉ (có 2 điểm cuối là điểm hữu tỉ), với mỗi màu ita luôn tìm được một điểm hữu tỉ thuộc đoạn thẳng này mà được tô màu i?

Chứng minh. Tá tô màu các điểm hữu tỉ như sau: gốc tọa độ tô màu bất kì, với điểm hữu tỉ P(x, y)6= (0,0) ta sẽ tô màu i sao cho i≡min{v₂(x), v₂(y)} (mod n).

Bây giờ xét đoạn thẳng hữu tỉ P Qbất kì, với P ^x_z¹

1,^y_z¹

1

và Q ^x_z²

2,^y_z²

2

với x₁, x₂, y₁, y₂, z₁, z₂ ∈Z. Tiếp theo, với mỗi màu j (1≤j ≤n) chúng ta sẽ chỉ ra có một điểm R∈P Q sao cho R màu j.

Do P 6=Qnên một trong hai số x₁z₂−x₂z₁, y₁z₂−y₂z₁ khác không. Lúc này ta giả sử v₂(x₁z₂−x₂z₁)≤v₂(y₁z₂−y₂z₁). Đặt r =v₂(x₁z₂−x₂z₁) và s =v₂(z₁z₂). Chọn số nguyên k > r sao cho r−s−k ≡j (mod n). Đặt t= 2^−k và điểm R=tP + (1−t)Q thuộc đoạn P Q. Từ đây giải tọa độ của R ta được

R=

2^kx₂z₁+ (x₁z₂−x₂z₁)

2^kz₁z₂ ,2^ky₂z₁+ (y₁z₂−y₂z₁) 2^kz₁z₂

.

Do k > r=v₂(x₁z₂−x₂z₁) nên v₂(2^kx₂z₁)> v₂(x₁z₂−x₂z₁), suy ra v₂(x_R) = v₂(x₁z₂−x₂z₁)−v₂(2^kz₁z₂) = r−k−s.

Mặt khác thì v2(x1z2−x2z1)≤v2(y1z2−y2z1) nên v₂(y_R) =v₂ 2^ky₂z₁+ (y₁z₂−y₂z₁)

−k−s≥r−k−s.

Vì thế min{v₂(x_R), v₂(y_R)} ≡r−k−s ≡j (mod n). Vậy màu của R là j. Ở lời giải trên ta có thể thay 2 bởi số nguyên tố p bất kì.

Ví dụ 2.4 (APMO 2017). Số hữu tỉ r làsố powerful nếur có thể viết dưới dạng ^x_y^k với x, y là hai số nguyên dương nguyên tố với nhau và k >1 là số nguyên dương. Gọi a, b, c là các số hữu tỉ dương sao cho abc = 1. Giả sử tồn tại các số nguyên dương m, n, t sao cho a^m+bⁿ+c^t là một số nguyên. Chứng minh rằng a, b, c là các số powerful.

Chứng minh. Theo định nghĩa thì thì số hữu tỉ r là powerful khi và chỉ khi gcd

p∈P

(max{0, v_p(r)})≥2.

Mặt khác do vai trò a, b, c như nhau nên ta chỉ cần chứng minh a powerful là đủ.

Xét số nguyên tố p sao cho v_p(a) > 0 (nếu không tồn tại p như vậy thì a = 1

q là một powerful).

Gọi i=v_p(a), j =v_p(b) và k =v_p(c). Từ điều kiện abc= 1 nên ta có i+j+k = 0. Mặt khác vì i >0 nên min{j, k}<0. Không mất tính tổng quát ta có thể giả sử j <0.

Do a^m +bⁿ +c^t là một số nguyên nên v_p(a^m +bⁿ +c^t) ≥ 0. Nếu v_p(c^t) < v_p(bⁿ) thì vp(a^m +bⁿ +c^t) = min{vp(a^m), vp(bⁿ), vp(c^t)} = vp(c^t) < vp(bⁿ) < 0 (mâu thuẫn với nhận xét trên). Tương tự cho trường hợp vp(bⁿ) > vp(c^t), do đó vp(bⁿ) = vp(c^t) hay nj = tk. Dẫn đến k <0 và tồn tại số nguyên dương s sao cho j =−s._(n,k)^k và k=−s._(n,k)ⁿ . Suy ra

i=−(j+k) = t· n+k gcd(n, k),

mà i > 0 nên _gcd(n,k)^n+k | i= v_p(a) hay _gcd(n,k)^n+k | max{0, v_p(a)}. Bên cạnh đó ta có _gcd(n,k)^n+k ≥ 1 + 1 = 2, nên

gcd

p∈P

(max{0, vp(a)})| n+k

gcd(n, k) ≥2.

Vậy a là số powerful.

Ví dụ 2.5 (CNO 2015). Cho số nguyên dương k ≥ 2, chứng minh rằng có vô hạn số nguyên dương n thỏa

n+k- 2n

n

.

Giải.

Trường hợp 1: k có ước nguyên tố p lẻ. Đặt t=v_p(k)>0, n =p^m với m > t, chúng ta sẽ chứng minh

n+k- 2n

n

.

Thật vậy ta có vp(n+k) =t. Bên cạnh đó thì theo (1.7) và (1.1), ta có vp

2p^m p^m

=vp((2p^m)!)−2vp(p^m!)

=2p^m−1+ 2p^m−2+· · ·+ 2−2 p^m−1+p^m−2+· · ·+ 1

=0

Trường hợp 2: k = 2^t với t ≥ 1. Nếu t = 1 thì chọn n = 2^m −2 với m > t. Khi đó v₂(n+k) =m và

v₂

2^m+1−4 2^m−2

=v₂ (2^m+1−4)!

−2v₂((2^m−2)!)

=(2^m−2) + (2^m−1−1) +· · ·+ 1−2 (2^m−1−1) + (2^m−2−1) +· · ·+ 1

=m−1.

Nếu t≥2 thì chọn n= 2^m với m > t. Khi đó v₂(n+k) =t và v₂

2^m+1 2^m

=v₂ 2^m+1!

−2v₂(2^m!)

=2^m+ 2^m−1+· · ·+ 1−2 2^m−1+ 2^m−2+· · ·+ 1

=1.

Vậy với k≥2 thì tồn tại vô hạn các số n thỏa mãn bài toán.

3 Áp dụng vào tìm số nguyên thỏa điều kiện cho trước

Ví dụ 3.1 (Kvant M 2163). Tìm tất cả các số nguyên dương a, bsao cho (a+b³)(b+a³) là một lũy thừa của 3.

Giải. Giả sử (a, b) là một cặp thỏa yêu cầu bài toán. Khi đó a+b³, b+a³ đều là các lũy thừa của 3. Đặt a+b³ = 3ⁿ, b+a³= 3^m, nếu v₃(a)>0 thì

v₃(a³) = v₃(3^m−b).

Tuy nhiên do b < 3^m nên v₃(b) < v₃(3^m), kéo theo v₃(3^m−b) = v₃(b) hay 3v₃(a) = v₃(b). Tương tự chúng ta có 3v₃(b) =v₃(a), suy ra v₃(a) = 0 (mâu thuẫn với giả thiết). Vậy cả a, b đều không chia hết cho 3.

Xét a≡1 (mod 3), từ a³ ≡ −b (mod 3) nên b ≡ −1 (mod 3). Nếu a >1 thì v₃(a³−1) =v₃(3^m−b−1) =v₃(3^m−(b+ 1)) =v₃(b+ 1) và

v₃(b³+ 1) =v₃(3ⁿ−a+ 1) =v₃(a−1).

Vì thế v₃(a³−1)> v₃(a−1)và v₃(b³+ 1)> v₃(b+ 1), suy ra v₃(a²+a+ 1), v₃(b²−b+ 1)>0. Do đó v₃(a³−1) = v₃(b+ 1) > v₃(a−1) =v₃(b³+ 1)> v₃(b+ 1) hay a = 1. Lúc này ta có hai phương trình b³+ 1 = 3ⁿ, b+ 1 = 3^m. Kéo theo b²−b+ 1 = 3^n−m và n≥m. Nếu b >2 thì 9|b+ 1và n−m ≥2, kéo theo 9|b² hay3|b (mâu thuẫn với chứng minh trên). Vậy b= 2 thỏa.

Do tính đối xứng nên với a≡ −1 (mod 3) thì ta có a= 2, b= 1.