ỨNG DỤNG SỐ MŨ LỚN NHẤT CỦA THỪA SỐ NGUYÊN TỐ
TRONG CÁC BÀI TOÁN SỐ HỌC
Lê Trần Nhạc Long - THPT Chuyên Lê Quý Đôn- Đà Nẵng
----------------------------------------
17/1/2012 Tặng diễn đàn VMF nhân dịp sinh nhật 8 năm của diễn đàn
Cho p là một số nguyên tố lẻ ,số tự nhiên n và hai số nguyên dương phân biệt a và b . Gọi \alpha và \beta lần lượt là số mũ lớn nhất của p trong a-b và n. Thì số mũ lớn nhất của p trong a^n-b^n là p^{\alpha+\beta}
Kí hiệu số mũ lớn nhất của p trong m là v_{p}(m) hoặc p^{\alpha}||m (với \alpha là số mũ lớn nhất của p trong m)
(Trong bài viết này ta sẽ sử dụng kí hiệu p^{\alpha}||m)
Chứng minh:
Bài toán đưa về chứng minh rằng nếu a \equiv b \pmod{p} và p^{\beta}||n thì p^{\beta}||\dfrac{a^n-b^n}{a-b}.
Giả sử n=p^{\beta}k. Ta sẽ chứng minh bài toán quy nạp theo \beta
Với trường hợp \beta=0 tức là n\;\not \vdots\;p.
Khi đó ta có: a^k \equiv b^k \pmod{p}
a^kb^{n-k-1}\equiv b^{n-1} \pmod{p} \Rightarrow \sum_{k=0}^{n-1}a^kb^{n-k-1}\equiv \sum_{k=0}^{n-1}b^{n-1} \pmod{p} \equiv nb^{n-1}\not \equiv 0 \pmod{p}
Vì \frac{a^n-b^n}{a-b}=\sum_{k=0}^{n-1}a^{n-k-1}b^k.
Do đó \frac{a^n-b^n}{a-b}\;\not\vdots \;p
Bây giờ giả sử bài toán đúng đến \beta ta sẽ chứng minh đúng đến \beta+1 tức là ta chỉ cần chứng minh p||\dfrac{a^{np}-b^{np}}{a^n-b^n}. Thật vậy:
Vì p|a-b nên a=b+xp suy ra a^k\equiv b^k+kb^{k-1}xp \pmod{p^2}
Ta được
\frac{a^{np}-b^{np}}{a^n-b^n}=\sum_{k=0}^{p-1}a^{n(p-k-1)}b^{nk} \equiv\sum_{k=0}^{p-1}(b^{n(p-k-1)}+n(p-k-1)xpb^{n(p-k-1)-1})b^{nk} \pmod {p^2}
\equiv pb^{n(p-1)}+\sum_{k=0}^{p-1} n(p-k-1)xpb^{n(p-1)-1} \equiv pb^{n(p-1)}\equiv p \pmod{p^2}
Vậy ta được p||\dfrac{a^{np}-b^{np}}{a^n-b^n}. Do đó
p^{\beta+1}||\dfrac{a^n-b^n}{a-b}.\dfrac{a^{np}-b^{np}}{a^n-b^n}=\frac{a^{np}-b^{np}}{a-b}
Vậy bài toán được chứng minh
Chú ý:
Ta có một trường hợp đặc biệt sau đây với p=2
Cho a,b,c \in \mathbb{Z} thỏa mãn 2^{\alpha}||\frac{a^2-b^2}{2} và 2^\beta||n thì 2^{\alpha+\beta}||a^n-b^n
Phần chứng minh kết quả này xin dành cho bạn đọc.
Với trường hợp \beta=0 thì trường hợp đặc biệt này chỉ đúng khi 4|a-b
Và sau đây chúng ta sẽ đến với một số bài toán ứng dụng tính chất này
Bài toán 1:
Tìm số nguyên dương n nhỏ nhất thỏa mãn 2^{2012}|17^n-1
Lời giải:
Ta có:2^4||\frac{17^2-1}{2}. Giả sử 2^\alpha ||n.
Theo trường hợp đặc biệt của bài toán mở đầu ta được
2^{4+\alpha}||17^n-1. Suy ra \alpha+4 \geq 2012 \Rightarrow \alpha \geq 2008.
Điều đó có nghĩa là 2^{2008}|n\Rightarrow n\geq 2^{2008} .
Theo bổ đề mở đầu ta được 2^{2012}|{17^2}^{2008}-1.
Vậy giá trị nhỏ nhất của n là 2^{2008}
Bài toán 2:
Giải phương trình nghiệm nguyên {2^3}^x+1=19.3^y
Lời giải:
Áp dụng bài toán mở đầu ta được 3^{n+1}||{2^3}^n+1 vì 3^n là một số lẻ
Vì 19 \not \vdots 3 nên do đó ta được 3^y||{2^{3}}^x+1. Từ đó suy ra y=x+1
Vậy phương trình trở thành: {2^3}^x+1=57.3^x (*)
Đặt t=3^x. Ta chứng minh 2^t > 57t \forall t \geq 10
Thật vậy ta có: 2^t=2^6.2^{t-6}=64.2^{t-6}
Ta có 64 > 57, ta có 2^4 > 10 suy ra 2^{t-6}>t đúng với t=10
Giả sử đúng đến t ta có 2^{t-5}=2.2^{t-6}> 2t > t+1
Vậy bđt trên đúng nên từ (*) suy ra 3^x <10 \Rightarrow x\leq2
Thay x=0;1;2 chỉ thấy x=2 thỏa mãn (*). Vậy x=2,y=3 là bộ nghiệm duy nhất của phương trình
Bài toán 3:
Cho dãy số được xác định như sau
a_1=\frac{5}{2} và a_{n+1}=a_n^3-3a_n^2+6a_n-3 với mọi n\geq 1
Tìm số nguyên dương n nhỏ nhất sao cho \left\lfloor a_n \right\rfloor+1 chia hết cho 3^{2011}
Kí hiệu số mũ lớn nhất của p trong m là v_{p}(m) hoặc p^{\alpha}||m (với \alpha là số mũ lớn nhất của p trong m)
(Trong bài viết này ta sẽ sử dụng kí hiệu p^{\alpha}||m)
Chứng minh:
Bài toán đưa về chứng minh rằng nếu a \equiv b \pmod{p} và p^{\beta}||n thì p^{\beta}||\dfrac{a^n-b^n}{a-b}.
Giả sử n=p^{\beta}k. Ta sẽ chứng minh bài toán quy nạp theo \beta
Với trường hợp \beta=0 tức là n\;\not \vdots\;p.
Khi đó ta có: a^k \equiv b^k \pmod{p}
a^kb^{n-k-1}\equiv b^{n-1} \pmod{p} \Rightarrow \sum_{k=0}^{n-1}a^kb^{n-k-1}\equiv \sum_{k=0}^{n-1}b^{n-1} \pmod{p} \equiv nb^{n-1}\not \equiv 0 \pmod{p}
Vì \frac{a^n-b^n}{a-b}=\sum_{k=0}^{n-1}a^{n-k-1}b^k.
Do đó \frac{a^n-b^n}{a-b}\;\not\vdots \;p
Bây giờ giả sử bài toán đúng đến \beta ta sẽ chứng minh đúng đến \beta+1 tức là ta chỉ cần chứng minh p||\dfrac{a^{np}-b^{np}}{a^n-b^n}. Thật vậy:
Vì p|a-b nên a=b+xp suy ra a^k\equiv b^k+kb^{k-1}xp \pmod{p^2}
Ta được
\frac{a^{np}-b^{np}}{a^n-b^n}=\sum_{k=0}^{p-1}a^{n(p-k-1)}b^{nk} \equiv\sum_{k=0}^{p-1}(b^{n(p-k-1)}+n(p-k-1)xpb^{n(p-k-1)-1})b^{nk} \pmod {p^2}
\equiv pb^{n(p-1)}+\sum_{k=0}^{p-1} n(p-k-1)xpb^{n(p-1)-1} \equiv pb^{n(p-1)}\equiv p \pmod{p^2}
Vậy ta được p||\dfrac{a^{np}-b^{np}}{a^n-b^n}. Do đó
p^{\beta+1}||\dfrac{a^n-b^n}{a-b}.\dfrac{a^{np}-b^{np}}{a^n-b^n}=\frac{a^{np}-b^{np}}{a-b}
Vậy bài toán được chứng minh
Chú ý:
Ta có một trường hợp đặc biệt sau đây với p=2
Cho a,b,c \in \mathbb{Z} thỏa mãn 2^{\alpha}||\frac{a^2-b^2}{2} và 2^\beta||n thì 2^{\alpha+\beta}||a^n-b^n
Phần chứng minh kết quả này xin dành cho bạn đọc.
Với trường hợp \beta=0 thì trường hợp đặc biệt này chỉ đúng khi 4|a-b
Và sau đây chúng ta sẽ đến với một số bài toán ứng dụng tính chất này
Bài toán 1:
Tìm số nguyên dương n nhỏ nhất thỏa mãn 2^{2012}|17^n-1
Lời giải:
Ta có:2^4||\frac{17^2-1}{2}. Giả sử 2^\alpha ||n.
Theo trường hợp đặc biệt của bài toán mở đầu ta được
2^{4+\alpha}||17^n-1. Suy ra \alpha+4 \geq 2012 \Rightarrow \alpha \geq 2008.
Điều đó có nghĩa là 2^{2008}|n\Rightarrow n\geq 2^{2008} .
Theo bổ đề mở đầu ta được 2^{2012}|{17^2}^{2008}-1.
Vậy giá trị nhỏ nhất của n là 2^{2008}
Bài toán 2:
Giải phương trình nghiệm nguyên {2^3}^x+1=19.3^y
Lời giải:
Áp dụng bài toán mở đầu ta được 3^{n+1}||{2^3}^n+1 vì 3^n là một số lẻ
Vì 19 \not \vdots 3 nên do đó ta được 3^y||{2^{3}}^x+1. Từ đó suy ra y=x+1
Vậy phương trình trở thành: {2^3}^x+1=57.3^x (*)
Đặt t=3^x. Ta chứng minh 2^t > 57t \forall t \geq 10
Thật vậy ta có: 2^t=2^6.2^{t-6}=64.2^{t-6}
Ta có 64 > 57, ta có 2^4 > 10 suy ra 2^{t-6}>t đúng với t=10
Giả sử đúng đến t ta có 2^{t-5}=2.2^{t-6}> 2t > t+1
Vậy bđt trên đúng nên từ (*) suy ra 3^x <10 \Rightarrow x\leq2
Thay x=0;1;2 chỉ thấy x=2 thỏa mãn (*). Vậy x=2,y=3 là bộ nghiệm duy nhất của phương trình
Bài toán 3:
Cho dãy số được xác định như sau
a_1=\frac{5}{2} và a_{n+1}=a_n^3-3a_n^2+6a_n-3 với mọi n\geq 1
Tìm số nguyên dương n nhỏ nhất sao cho \left\lfloor a_n \right\rfloor+1 chia hết cho 3^{2011}
(Đề chọn đội tuyển dự thi VMO 2012-KHTNHN vòng 2)
Lời giải:
Đặt a_n=u_n+1\Rightarrow u_n=a_n-1
Đẳng thức đầu bài cho ta :
a_1-1=\dfrac{3}{2}
a_{n+1}-1= (a_n-1)^3+3(a_n-1)
Nên ta suy ra :
u_1=\dfrac{3}{2}
u_{n+1}= u_n^3+3u_n
Ta chứng minh rằng :u_1=2^{3^{n-1}}-\frac{1}{2^{n-1}} \forall n \ge 1 (*)
Thật vậy , với n=1 thì ta thấy thỏa
Nếu đẳng thức trên đúng với n=k tức là :u_k=2^{3^{k-1}}-\frac{1}{2^{k-1}}
Khi đó ta có :u_{k+1} = u_k^3+3u_k= 2^{3^k}-\dfrac{1}{3^{k}}
Do đó theo quy nạp toán học , ta có (*) .
Bởi thế nên :
3^{2011}| \left\lfloor a_n \right\rfloor +1 =\left\lfloor u_n \right\rfloor +2
\Leftrightarrow 3^{2011}| 2^{3^n}+1, (**)
Theo bài toán 1 ta có 3^{n+1}||{2^3}^n+1
Nên suy ra n\geq 2011-1=2010
vậy giá trị n nhỏ nhất cần tìm là n=2010
Bài toán 4: Cho a^n+b^n=p^k với a,b và k là các số nguyên dương, p là một số nguyên tố lẻ và n là một số lẻ lớn hơn 1. Chứng minh rằng n phải là một lũy thừa của p
Lời giải: Vì n lẻ nên ta có
p^k=a^n+b^n =(a+b)(a^{n-1}-a^{n-2}b+...-ab^{n-2}+b^{n-1})
Vì vậy a+b=p^r với r\in \mathbb{N}^*,r\leq k
Vì a và b là các số nguyên dương nên ta có r \geq 1
Giả sử p^\beta||n sử dụng bài toán mở đầu ta được
p^{\beta+r}||a^n-(-b)^n=a^n+b^n=p^k
Suy ra p^{\beta+r}||p^k \Rightarrow+\beta=k-r
Vì các số k và r là xác định nên phải có số nguyên dương n nhỏ nhất
thỏa mãn p^\beta||n để a^n+b^n=p^k,
vì a^m+b^m > a^n+b^n,\forall m > n.
Nên n phải là số nguyên dương nhỏ nhất thỏa mãn p^\beta||n là p^\beta. Điều này suy ra n phải là một lũy thừa của p.
Bài toán được chứng minh
Bài toán 5:Tìm tất cả các số nguyên dương n thỏa mãn n^2|2^n+1
(IMO1990)
Lời giải:
Giả sử n là số nguyên dương sao cho n^2|2^n+1 (1)
Suy ra n phải là một số lẻ, dễ thấy n=1 thỏa mãn
Xét n>1, gọi p_1 là ước nguyên tố nhỏ nhất của n.
Ta có : 2^{2n}\equiv 1 \pmod{p_1}
Gọi d=ord_{p_1}2 thì d< {p_1}, d|2n,
và (n,d)=1. Suy ra d|2
Nếu d=1 thì p_1=1 vô lí. Vậy d=2 và p_1|3 suy ra p_1=3.
Giả sử p^\beta||3 thì theo bài toán mở đầu ta được3^{\beta+1}||2^n+1
Kết hợp với (1) ta được
3^{2\beta}|3^{\beta+1}||2^n+1\Rightarrow 2\beta \leq \beta+1\Rightarrow \beta \leq 1
Từ đó suy ra 3||n\Rightarrow n=3k;(n;k)=1
Gọi p_2 là ước nguyên tố nhỏ nhất của k. Ta có 2^{6k}\equiv 1\pmod{p_2}
Gọi d_2=ord_{p_2}2 \Rightarrow d_2<{p_2} và d_2|6k
Mà (d_2,k)=1 nên d_2|6.
Dễ thấy d_2 không thể bằng 1 hoặc 2
Nếu d_2=3, ta có p_2|7\Rightarrow p_2=7
Nếu d_2=6, ta có p_2|63=7.9\Rightarrow p_2|7\Rightarrow p_2=7
Mà ta có: 2^3\equiv1\pmod{7}\Rightarrow 2^{k+3}\equiv 2^k\pmod{7}
và 2\equiv 2 \pmod{7} và 2^2\equiv 4 \pmod{7}
Nên phương trình 2^k\equiv -1 \pmod{7} không có nghiệm nguyên
Suy ra 2^{7k}+1 không chia hết cho 7 với mọi k và p_2 không tồn tại. Vậy n chỉ có một ước nguyên tố duy nhất là 3, lại có 3||n nên suy ra n=3
Vậy các giá trị của n cần tìm là n=1 và n=3.
Đặt a_n=u_n+1\Rightarrow u_n=a_n-1
Đẳng thức đầu bài cho ta :
a_1-1=\dfrac{3}{2}
a_{n+1}-1= (a_n-1)^3+3(a_n-1)
Nên ta suy ra :
u_1=\dfrac{3}{2}
u_{n+1}= u_n^3+3u_n
Ta chứng minh rằng :u_1=2^{3^{n-1}}-\frac{1}{2^{n-1}} \forall n \ge 1 (*)
Thật vậy , với n=1 thì ta thấy thỏa
Nếu đẳng thức trên đúng với n=k tức là :u_k=2^{3^{k-1}}-\frac{1}{2^{k-1}}
Khi đó ta có :u_{k+1} = u_k^3+3u_k= 2^{3^k}-\dfrac{1}{3^{k}}
Do đó theo quy nạp toán học , ta có (*) .
Bởi thế nên :
3^{2011}| \left\lfloor a_n \right\rfloor +1 =\left\lfloor u_n \right\rfloor +2
\Leftrightarrow 3^{2011}| 2^{3^n}+1, (**)
Theo bài toán 1 ta có 3^{n+1}||{2^3}^n+1
Nên suy ra n\geq 2011-1=2010
vậy giá trị n nhỏ nhất cần tìm là n=2010
Bài toán 4: Cho a^n+b^n=p^k với a,b và k là các số nguyên dương, p là một số nguyên tố lẻ và n là một số lẻ lớn hơn 1. Chứng minh rằng n phải là một lũy thừa của p
Lời giải: Vì n lẻ nên ta có
p^k=a^n+b^n =(a+b)(a^{n-1}-a^{n-2}b+...-ab^{n-2}+b^{n-1})
Vì vậy a+b=p^r với r\in \mathbb{N}^*,r\leq k
Vì a và b là các số nguyên dương nên ta có r \geq 1
Giả sử p^\beta||n sử dụng bài toán mở đầu ta được
p^{\beta+r}||a^n-(-b)^n=a^n+b^n=p^k
Suy ra p^{\beta+r}||p^k \Rightarrow+\beta=k-r
Vì các số k và r là xác định nên phải có số nguyên dương n nhỏ nhất
thỏa mãn p^\beta||n để a^n+b^n=p^k,
vì a^m+b^m > a^n+b^n,\forall m > n.
Nên n phải là số nguyên dương nhỏ nhất thỏa mãn p^\beta||n là p^\beta. Điều này suy ra n phải là một lũy thừa của p.
Bài toán được chứng minh
Bài toán 5:Tìm tất cả các số nguyên dương n thỏa mãn n^2|2^n+1
(IMO1990)
Lời giải:
Giả sử n là số nguyên dương sao cho n^2|2^n+1 (1)
Suy ra n phải là một số lẻ, dễ thấy n=1 thỏa mãn
Xét n>1, gọi p_1 là ước nguyên tố nhỏ nhất của n.
Ta có : 2^{2n}\equiv 1 \pmod{p_1}
Gọi d=ord_{p_1}2 thì d< {p_1}, d|2n,
và (n,d)=1. Suy ra d|2
Nếu d=1 thì p_1=1 vô lí. Vậy d=2 và p_1|3 suy ra p_1=3.
Giả sử p^\beta||3 thì theo bài toán mở đầu ta được3^{\beta+1}||2^n+1
Kết hợp với (1) ta được
3^{2\beta}|3^{\beta+1}||2^n+1\Rightarrow 2\beta \leq \beta+1\Rightarrow \beta \leq 1
Từ đó suy ra 3||n\Rightarrow n=3k;(n;k)=1
Gọi p_2 là ước nguyên tố nhỏ nhất của k. Ta có 2^{6k}\equiv 1\pmod{p_2}
Gọi d_2=ord_{p_2}2 \Rightarrow d_2<{p_2} và d_2|6k
Mà (d_2,k)=1 nên d_2|6.
Dễ thấy d_2 không thể bằng 1 hoặc 2
Nếu d_2=3, ta có p_2|7\Rightarrow p_2=7
Nếu d_2=6, ta có p_2|63=7.9\Rightarrow p_2|7\Rightarrow p_2=7
Mà ta có: 2^3\equiv1\pmod{7}\Rightarrow 2^{k+3}\equiv 2^k\pmod{7}
và 2\equiv 2 \pmod{7} và 2^2\equiv 4 \pmod{7}
Nên phương trình 2^k\equiv -1 \pmod{7} không có nghiệm nguyên
Suy ra 2^{7k}+1 không chia hết cho 7 với mọi k và p_2 không tồn tại. Vậy n chỉ có một ước nguyên tố duy nhất là 3, lại có 3||n nên suy ra n=3
Vậy các giá trị của n cần tìm là n=1 và n=3.
Không có nhận xét nào:
Đăng nhận xét