Ứ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 được$3^{\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 được$3^{\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