Toán [Chuyên đề HSGQG] Định lý LTE, cấp của số nguyên và phương trình nghiệm nguyên chứa lũy thừa

7 1 2 5

TMod Toán
Cu li diễn đàn
19 Tháng một 2019
6,651
11,119
1,116
16
Hà Tĩnh
THPT Chuyên Hà Tĩnh
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Xin chào các bạn. Topic này mình sẽ giới thiệu cho các bạn 2 công cụ mới để giải quyết phương trình nghiệm nguyên, đó chính là Định lý LTE (tiếng Anh: Lifting The Exponent lemma) và cấp của một số nguyên. Về cơ bản, tên tiếng Anh của định lý LTE là "bổ đề nâng lũy thừa" cho nên định lý này thường dùng để xử lý các dạng chứa ẩn ở số mũ. Còn cấp của một số nguyên cũng là một định nghĩa liên quan tới sự đồng dư của lũy thừa. Bây giờ chúng ta sẽ đi vào nội dung của chủ đề này nhé!

I. Giới thiệu về hàm [imath]p[/imath]-adic.

Hàm [imath]p[/imath]-adic của một số nguyên được định nghĩa như sau:
"Cho số nguyên [imath]n[/imath] và một số nguyên tố [imath]p[/imath], số tự nhiên [imath]\alpha[/imath]. Ta gọi [imath]p^{\alpha}[/imath] là lũy thừa đúng của [imath]a[/imath] nếu như [imath]\begin{cases} p^{\alpha} \mid n \\ p^{\alpha + 1} \nmid n \end{cases}[/imath]. Khi đó [imath]\alpha[/imath] được gọi là số mũ đúng của [imath]p[/imath] trong khai triển của [imath]a[/imath], và hàm [imath]p[/imath]-adic được định nghĩa là [imath]v_p(n)=\alpha[/imath]"
Nói theo ngôn ngữ thông thường, hàm [imath]p[/imath]-adic của một số tự nhiên [imath]n[/imath] là số mũ của [imath]p[/imath] trong dạng phân tích thành thừa số nguyên tố của [imath]n[/imath].

Sau khi định nghĩa xong hàm, ta có một số tính chất như sau:

Với [imath]a,b[/imath] là các số nguyên và [imath]n[/imath] là số tự nhiên, ta có:
1. [imath]v_p(ab)=v_p(a)+v_p(b)[/imath]
2. Nếu [imath]\dfrac{a}{b} \in \mathbb{Z}[/imath] thì [imath]v_2(\dfrac{a}{b})=v_2(a)-v_2(b)[/imath]
3. [imath]v_p(a^n)=n\cdot v_p(a)[/imath]
4. [imath]v_p(a+b) \geq \min \lbrace{ v_p(a), v_p(b) \rbrace}[/imath]. Dấu "=" xảy ra khi [imath]v_p(a) \neq v_p(b)[/imath]
5. [imath]v_p(\text{gcd}(|a|,|b|))=\min \lbrace{ v_p(a),v_p(b) \rbrace}[/imath]
6. [imath]v_p(\text{lcm}(|a|,|b|))= \max \lbrace{ v_p(a),v_p(b) \rbrace}[/imath]
7. (Công thức Legendre) [imath]v_p(n!)= \sum _{i=1}^{\infty} [ \dfrac{n}{p^i} ][/imath]

(Lưu ý: [imath]v_p(n)=0[/imath] nếu [imath]p \nmid n[/imath] và [imath]v_p(0)=\infty[/imath])


Các công thức từ [imath]1[/imath] đến [imath]6[/imath] các bạn có thể tự chứng minh bằng định nghĩa, còn công thức thứ [imath]7[/imath] thì các bạn có thể tham khảo trên mạng nhé.
Các bạn chỉ cần để ý vế phải là công thức tính số bội của [imath]p[/imath], [imath]p^2[/imath],... trong tất cả các số từ [imath]1[/imath] đến [imath]n[/imath], và khi đó suy luận một xíu thì ta thấy đó cũng chính là [imath]v_p(n!)[/imath].

II. Giới thiệu về cấp của một số nguyên

Định nghĩa cấp của một số nguyên như sau:
"Cho số nguyên [imath]a[/imath] và số tự nhiên [imath]n[/imath] thỏa mãn [imath]\text{gcd}(a,n)=1[/imath]. Khi đó số nguyên dương [imath]d[/imath] nhỏ nhất thỏa mãn [imath]a^d \equiv 1(\mod n)[/imath] được gọi là cấp của số nguyên [imath]a[/imath] theo modulo [imath]n[/imath], ký hiệu [imath]d=\text{ord}_n(a)[/imath]".

Một số tính chất của cấp số nguyên như sau:

Với số nguyên [imath]a[/imath] và số tự nhiên [imath]n[/imath] thỏa mãn [imath]\text{gcd}(a,n)=1[/imath], [imath]d=\text{ord}_n(a)[/imath] ta có:
1. Nếu [imath]k[/imath] là một số nguyên dương thỏa mãn [imath]a^k \equiv 1(\mod n)[/imath] thì [imath]d \mid k[/imath].
Hệ quả: [imath]\lbrace{ 1,a,a^2,...,a^{d-1} \rbrace}[/imath] là các số có số dư đôi một khác nhau khi chia cho [imath]n[/imath].
2. Nếu [imath]a[/imath] có cấp là [imath]h[/imath] theo modulo [imath]n[/imath] thì cấp của [imath]a^k[/imath] theo modulo [imath]n[/imath] là [imath]\dfrac{d}{\text{gcd}(k,d)}[/imath]

Đặc biệt, tính chất 1 gần như là tính chất quan trọng nhất của cấp số nguyên.

III. [imath]2[/imath] bổ đề cơ bản trước khi đến với Định lý LTE

Hai bổ đề này được xem như là phần dễ của định lý LTE, và có thể dùng để chứng minh định lý LTE luôn nhé.

Bổ đề 1: Cho [imath]x,y \in \mathbb{Z}[/imath], [imath]n \in \mathbb{N}^*[/imath]. Xét số nguyên tố [imath]p[/imath] bất kỳ thỏa mãn [imath]p \mid x-y, p \nmid x, p \nmid y, p \nmid n[/imath]. Khi đó:
[math]v_p(x^n-y^n)=v_p(x-y)[/math]
Ta phân tích [imath]x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})[/imath]
Nhận thấy vì [imath]x \equiv y (\mod p)[/imath] nên [imath]x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1} \equiv nx^{n-1} (\mod p)[/imath]. Mà do [imath]p \nmid n, p \nmid x[/imath] nên [imath]p \nmid nx^{n-1}[/imath] hay [imath]v_p(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})=0[/imath].
Từ đó theo công thức 1 ta được [imath]v_p(x^n-y^n)=v_p(x-y)+v_p(x^{n-1}+x^{n-2}y+...+xy^{n-2}+y^{n-1})=v_p(x-y)[/imath]

Bổ đề 2: Cho [imath]x,y \in \mathbb{Z}[/imath]. Xét số nguyên tố lẻ [imath]p[/imath] bất kỳ thỏa mãn [imath]p \mid x-y, p \nmid x, p \nmid y[/imath]. Khi đó:
[math]v_p(x^p-y^p)=v_p(x-y)+1[/math]
Tiếp tục phân tích [imath]x^p-y^p=(x-y)(x^{p-1}+x^{p-2}y+...+xy^{p-2}+y^{p-1})[/imath]
Từ công thức 1 ta chỉ cần chứng minh [imath]v_p(x^{p-1}+x^{p-2}y+...+xy^{p-2}+y^{p-1})=1[/imath].
Thật vậy, vì [imath]x \equiv y(\mod p)[/imath] nên [imath]x^{p-1}+x^{p-2}y+...+xy^{p-2}+y^{p-1} \equiv px^{p-1} \equiv 0 (\mod p)[/imath]
[imath]\Rightarrow p \mid x^{p-1}+x^{p-2}y+...+xy^{p-2}+y^{p-1}[/imath]
Mặt khác, nếu ta đặt [imath]y=x+kp[/imath] với [imath]k \in \mathbb{N}, p \nmid k[/imath] thì ta có:
[imath]y^i=(x+kp)^i=x^i+C_i^1 kp\cdot x^{i-1}+C_i^2(kp)^2x^{i-2}+...+C_i^{i-1}(kp)^{i-1}x+(kp)^i \equiv x^i+ikp\cdot x^{i-1}(\mod p)[/imath] [imath]\forall 1 \leq i \leq p-1[/imath]
Từ đó [imath]x^{p-1-i}y^i \equiv x^{p-1}+ikp\cdot x^{p-2}(\mod p^2) \forall 1 \leq i \leq p-1[/imath]
Suy ra [imath]x^{p-1}+x^{p-2}y+...+xy^{p-2}+y^{p-1} \equiv px^{p-1}+kp\cdot x^{p-2}(1+2+...+p-1)(\mod p^2)[/imath]
[imath]\equiv px^{p-1}+\dfrac{kp^2(p-1)}{2}x^{p-2}(\mod p^2)[/imath]
Vì [imath]p^2 \mid \dfrac{kp^2(p-1)}{2}x^{p-2}, p^2 \nmid px^{p-1}[/imath] nên [imath]p^2 \nmid x^{p-1}+x^{p-2}y+...+xy^{p-2}+y^{p-1}[/imath]
Từ đó [imath]v_p(x^{p-1}+x^{p-2}y+...+xy^{p-2}+y^{p-1})=1[/imath]. Bổ đề được chứng minh.

IV. Định lý LTE

Định lý 1:
Cho [imath]x,y \in \mathbb{Z},n \in \mathbb{N}^*[/imath]. Xét số nguyên tố lẻ [imath]p[/imath] thỏa mãn [imath]p \mid x-y, p \nmid x, p \nmid y[/imath]. Khi đó
[math]v_p(x^n-y^n)=v_p(x-y)+v_p(n)[/math]
Đặt [imath]n=p^k\cdot q (k,q \in \mathbb{N}^*, p \nmid q)[/imath]
Khi đó ta có: [imath]v_p(a^n-b^n)=v_p((a^{p^k})^q-(b^{p^k})^q)[/imath]
[imath]=v_p(a^{p^k}-b^{p^k}) \text{( áp dụng bổ đề 1)}[/imath]
[imath]=v_p((a^{p^{k-1}})^p-(b^{p^{k-1}})^p)[/imath]
[imath]=v_p(a^{p^{k-1}}-b^{p^{k-1}})+1 \text{( áp dụng bổ đề 2)}[/imath]
[imath]=...[/imath]
[imath]=v_p(a-b)+k=v_p(a-b)+v_p(n)[/imath]
Định lý được chứng minh.

Định lý 2: Cho [imath]x,y \in \mathbb{Z},n \in \mathbb{N}^*, 2 \nmid n[/imath]. Xét số nguyên tố lẻ [imath]p[/imath] thỏa mãn [imath]p \mid x+y, p \nmid x, p \nmid y[/imath]. Khi đó
[math]v_p(x^n+y^n)=v_p(x+y)+v_p(n)[/math]
Chứng minh: Áp dụng định lý 1 với cặp số [imath](x,-y)[/imath] ta có điều phải chứng minh.

Định lý 3: Cho [imath]x,y \in \mathbb{Z},n \in \mathbb{N}^*[/imath], [imath]x,y[/imath] lẻ. Giả sử [imath]2 \mid n[/imath]. Khi đó
[math]v_2(x^n-y^n)=v_2(x^2-y^2)+v_2(\dfrac{n}{2})[/math]
Đặt [imath]n=2^k \cdot s(k,s \in \mathbb{N}; 2 \nmid s)[/imath]
Khi đó áp dụng bổ đề [imath]1[/imath] ta được [imath]v_2(x^n-y^n)=v_2(x^{2^k}-y^{2^k})[/imath]
Ta phân tích [imath]x^{2^k}-y^{2^k}=(x^{2^{k-1}}+y^{2^{k-1}})(x^{2^{k-1}}-y^{2^{k-1}})[/imath]
[imath]=(x^{2^{k-1}}+y^{2^{k-1}})(x^{2^{k-2}}+y^{2^{k-2}})(x^{2^{k-2}}-y^{2^{k-2}})[/imath]
[imath]=...[/imath]
[imath]=(x^{2^{k-1}}+y^{2^{k-1}})(x^{2^{k-2}}+y^{2^{k-2}})...(x^2+y^2)(x^2-y^2)[/imath]
Nhận thấy vì [imath]x,y[/imath] lẻ nên [imath]x^{2m},y^{2m} \equiv 1(\mod 4)[/imath] nên [imath]4 \nmid x^{2m}+y^{2m}[/imath].
Từ đó [imath]v_2(x^{2^{k-1}}+y^{2^{k-1}})=v_2(x^{2^{k-2}}+y^{2^{k-2}})=...=v_2(x^2+y^2)=1[/imath]
[imath]\Rightarrow v_2(x^{2^k}-y^{2^k})=k-1+v_2(x^2-y^2)=v_2(x^2-y^2)+v_2(n)-1=v_2(x^2-y^2)+v_2(\dfrac{n}{2})[/imath]

V. Ứng dụng của định lý LTE

Trong phương trình nghiệm nguyên chứa ẩn ở mũ, người ta thường kết hợp [imath]2[/imath] công cụ là định lý LTE và cấp của số nguyên để xử lý. Nhưng phần ứng dụng dưới đây mình sẽ nghiêng về sử dụng định lý LTE hơn, tức hướng đi gốc là sử dụng định lý LTE để giải, sau đó cấp của số nguyên là công cụ hỗ trợ thêm.

Bài 1: (Italy TST 2003) Tìm bộ số [imath](a,b,p)[/imath] thỏa mãn [imath]a,b \in \mathbb{Z}^+,p[/imath] là số nguyên tố thỏa mãn [imath]2^a+p^b=19^a[/imath].

Lời giải: Ta viết lại phương trình trên thành [imath]p^b=19^a-2^a[/imath]
Vì [imath]17 \mid 19^a-2^a[/imath] nên [imath]p=17[/imath].
Áp dụng định lý LTE ta có: [imath]v_{17}(19^a-2^a)=v_{17}(17)+v_{17}(a)=1+v_{17}(a)[/imath]
[imath]\Rightarrow b=1+v_{17}(a) \leq 1+a[/imath]
Xét các trường hợp:
+ [imath]b=1+a[/imath]. Khi đó ta có [imath]17^{1+a}=19^a-2^a[/imath]. Bằng quy nạp ta chứng minh được [imath]19^a-2^a<17^{a+1}[/imath] nên không tồn tại [imath]a,b[/imath] thỏa mãn.
+ [imath]b<1+a[/imath]. Ta suy ra [imath]1 \leq b \leq a[/imath]. Bằng quy nạp ta chứng minh được [imath]19^a-2^a \geq 17^a \geq 17^b[/imath] nên dấu "=" phải xảy ra, tức [imath]a=b=1[/imath],
Vậy [imath](a,b,p)=(1,1,17)[/imath] là nghiệm duy nhất của bài toán.

Bài 2: (Romania TST 2005) Giải phương trình nghiệm nguyên dương [imath]3^x=2^x \cdot y+1[/imath]

Lời giải: Viết lại phương trình như sau: [imath]2^x\cdot y=3^x-1[/imath]
Xét các trường hợp:
+ [imath]x[/imath] lẻ. Khi đó theo định lý LTE ta có [imath]v_2(3^x-1)=v_2(3-1)=1[/imath] hay [imath]v_2(2^x\cdot y)=1[/imath] nên [imath]x=1[/imath]. Từ đó [imath]y=1[/imath].
+ [imath]x[/imath] chẵn.
Áp dụng định lý LTE ta có: [imath]v_2(3^x-1)=v_2(9-1)+v_2(x)-1=2+v_2(x)[/imath].
[imath]\Rightarrow v_2(y)+x=2+v_2(x)[/imath]
Đặt [imath]x=2^m \cdot k[/imath] với [imath]m,k \in \mathbb{N}^*[/imath], [imath]2 \nmid k[/imath]. Khi đó dễ dàng chứng minh [imath]2^m >m+2[/imath] với [imath]m \geq 3[/imath].
Từ đó với [imath]x \geq 2^3=8[/imath] thì [imath]x > v_2(x)+2[/imath] nên không tồn tại [imath]y[/imath] thỏa mãn.
Vậy [imath]x \leq 7[/imath]. Mà [imath]2 \mid x[/imath] nên [imath]x \in \lbrace{ 2,4,6 \rbrace}[/imath].
Xét từng trường hợp ta được [imath]2[/imath] cặp [imath](x,y)[/imath] thỏa mãn là [imath](2,2),(4,5)[/imath].
Vậy phương trình trên có các nghiệm nguyên dương là [imath](1,1),(2,2),(4,5)[/imath]

Bài 3: (IMO 1999) Tìm tất cả các cặp [imath](n,p)[/imath] nguyên dương và [imath]p[/imath] nguyên tố sao cho [imath]n^{p-1} \mid (p-1)^n+1[/imath].

Lời giải: Với [imath]n=1[/imath] thì ta thấy mọi số nguyên tố [imath]p[/imath] đều thỏa mãn đề bài. Xét [imath]n \geq 2[/imath].
Xét các trường hợp:
+ [imath]p=2[/imath] thì [imath]n \mid 2 \Rightarrow n=2[/imath].
+ [imath]p \geq 3[/imath]. Khi đó [imath]p[/imath] lẻ nên [imath]n[/imath] lẻ.
Xét [imath]q[/imath] là ước nguyên tố nhỏ nhất của [imath]n[/imath]. Đặt [imath]d=\text{ord}_q(p-1)[/imath].
Khi đó ta có: [imath]q \mid n \mid (p-1)^n+1 \Rightarrow q \mid (p-1)^{2n}-1[/imath]
[imath]\Rightarrow d \mid 2n[/imath].
Mặt khác, theo định lý Fermat nhỏ thì [imath](p-1)^{q-1} \equiv 1(\mod q) \Rightarrow d \mid q-1[/imath]
Từ đó [imath]d \mid \text{gcd}(2n,q-1)[/imath]
Nếu tồn tại một số nguyên tố [imath]k[/imath] là ước chung của [imath]n[/imath] và [imath]d[/imath] thì từ trên ta có [imath]k \mid q-1[/imath].
Suy ra [imath]k \leq q-1 < q[/imath]. Mà [imath]k \mid n[/imath] nên [imath]k[/imath] là ước nguyên tố nhỏ hơn [imath]q[/imath] của [imath]n[/imath] (mâu thuẫn với cách chọn [imath]q[/imath])
Từ đó [imath]d \mid \text{gcd}(2,q-1)[/imath] hay [imath]d \mid 2[/imath]. Suy ra [imath]q \mid (p-1)^2-1[/imath] hay [imath]q \mid p(p-2)[/imath]
* Nếu [imath]q \mid p[/imath] thì do [imath]q,p[/imath] đều là số nguyên tố nên [imath]q=p[/imath].
Áp dụng định lý LTE ta có [imath]v_p((p-1)^n+1)=v_p(p)+v_p(n)=1+v_p(n)[/imath]
Vì [imath]n^{p-1} \mid (p-1)^n+1[/imath] nên [imath]1+v_p(n) \geq (p-1)v_p(n)[/imath]. Từ đó [imath]p \leq 3[/imath].
Mà [imath]p[/imath] lẻ nên [imath]p=3[/imath] suy ra [imath]v_3(n)=1[/imath].
Đặt [imath]n=3r (r \in \mathbb{N}^*,3 \nmid r)[/imath]. Khi đó ta cần tìm [imath]r[/imath] sao cho [imath]r^2 \mid 8^r+1[/imath]
Với [imath]r=1[/imath] thì ta có [imath]n=3[/imath]. Với [imath]r \geq 2[/imath] xét [imath]m[/imath] là ước nguyên tố nhỏ nhất của [imath]r[/imath].
Lấy [imath]s=\text{ord}_m(8)[/imath] thì chứng minh tương tự trên ta được [imath]s \mid 2[/imath]. Khi đó [imath]m \mid 8^2-1=63[/imath].
Mà [imath]m \neq 3[/imath] nên [imath]m=7[/imath]. Nhưng [imath]7 \nmid 8^r+1[/imath] nên [imath]r \geq 2[/imath] không thỏa mãn.
* Nếu [imath]q \mid p-2[/imath] thì [imath](p-1)^n+1 \equiv 1+1 \equiv 2(\mod q)[/imath] nên [imath]q=2[/imath]. Mà [imath]n[/imath] lẻ nên không thỏa mãn.
Vậy các cặp số [imath](n,p)[/imath] thỏa mãn là [imath](1,p),(2,2),(3,3)[/imath].


Hy vọng qua chủ đề này, các bạn có thêm kinh nghiệm để giải các dạng phương trình nghiệm nguyên tương tự. Chúc các bạn học tốt!

Nguồn tham khảo: 1. Kỹ thuận số mũ đúng và định lý LTE - Lê Phúc Lữ
2. Vận dụng phương pháp LTE vào giải các bài toán số học - Phạm Quang Toàn
 
Last edited:
Top Bottom