Tuyển tập Số học211 bài

Bài toán :

Tìm tất cả các bộ số tự nhiên $(m,p,q,x,y)$ với $p,q$ là các số nguyên tố thoả mãn 

$$2^{4m+2}+1=p^x{q}^y$$

Lời giải :

Dễ thấy $p,q$ đều lẻ.

Xét theo modulo 5 :

$$p^x.q^y=2^{4m+2}+1\equiv 0(\mathrm{mod}5)$$

Từ đây suy ra hoặc $p=5$ hoặc $q=5$. Không giảm tổng quát ta có thể giả sử $p=5$. Ta có :

$$2^{4m+2}+1=5^x{q}^y\iff (2^{2m+1}+1+2^{m+1})(2^{2m+1}+1-2^{m+1})=5^x.q^y$$

Rõ ràng ta có :

$$\gcd (2^{2m+1}+1+2^{m+1},2^{2m+1}+1-2^{m+1})\mid 2^{m+2}$$

Nhưng $\gcd (2^{2m+1}+1+2^{m+1},2^{2m+1}+1-2^{m+1})\mid 5^x.q^y$. Suy ra $\gcd (2^{2m+1}+1+2^{m+1},2^{2m+1}+1-2^{m+1})=1$.

Từ đây xét ba khả năng :

• Khả năng 1 :

$$\{\begin{array}{c}{2}^{2m+1}+2^{m+1}+1=5^x\\ 2^{2m+1}-2^{m+1}+1=q^y\end{array}$$

Mặt khác, theo bổ đề LTE :

$$v_5(5^x.q^y)=v_5(2^{4m+2}+1)=v_5(4^{2m+1}+1)=v_5(4+1)+v_5(2m+1)\Rightarrow x=1+v_2(2m+1)$$

Từ đây ta được :

$$5^x=5^{1+v_5(2m+1)}\le 5(2m+1)$$

Như vậy ta có :

$$2^{2m+1}+2^{m+1}+1\le 5(2m+1)\Rightarrow m\in \left\{0,1\right\}$$

Với $m=0$ thì $5^x=5,q^y=1$. Từ đây được $x=1,y=0,q\in \mathbb{P}$.

Với $m=1$ thì $5^x=13$, ta gặp mâu thuẫn.

Tóm lại ta được bộ $(m,x,y,p,q)=(0,1,0,5,q),(0,1,0,q,5)$.

• Khả năng 2 :

$$\{\begin{array}{c}{2}^{2m+1}+2^{m+1}+1=q^y\\ 2^{2m+1}-2^{m+1}+1=5^x\end{array}$$

Cũng tương tự khả năng 1 thì :

$$2^{2m+1}+1\le 5(2m+1)+2^{m+1}\Rightarrow m\in \left\{0,1,2\right\}$$

Với $m=0$ thì $q^y=5$ và $1=5^x$. Suy ra $x=0$ và $q=5,y=1$.

Với $m=1$ thì $13=q^y,5=5^x$. Suy ra $x=1,q=13,y=1$.

Với $m=2$ thì $41=q^y,25=5^x$. Suy ra $x=2,q=41,y=1$.

• Khả năng 3 :

$$\{\begin{array}{c}{2}^{2m+1}+2^{m+1}+1=5^x.q^y\\ 2^{2m+1}-2^{m+1}+1=1\end{array}$$

Dễ dàng thấy $m=0$. Suy ra $5^x.q^y=1$. Từ đó $x=y=0$ và $q\in \mathbb{P}$.

Kết luận :

$(m,x,y,p,q)$$=(0,1,0,5,r),(0,1,0,r,5),(0,0,1,5,5),(1,1,1,5,13),(1,1,1,13,5),(2,2,1,5,41),(2,1,2,41,5),(0,0,0,5,r),(0,0,0,r,5)$

Trong đó $r$ là số nguyên tố lẻ tuỳ ý.

Bài toán (Poland Finals 2002)

Cho $k$ là một số nguyên dương cố định. Xét dãy $(a_n)$ thỏa mãn :

$$\{\begin{array}{c}{a}_1=k+1\\ a_{n+1}=a_n^2-k{a}_n+k,\forall n\ge 1\end{array}$$

Chứng minh rằng với mọi số nguyên dương $m$ khác $n$ thì $a_m,a_n$ nguyên tố cùng nhau.

Lời giải :

Ta có :

$$a_{n+1}-k=a_n(a_n-k)=a_n{a}_{n-1}(a_{n-1}-k)=...=a_n{a}_{n-1}{a}_{n-2}...a_1(a_1-k)=a_n{a}_{n-1}...a_1$$

Không giảm tổng quát, ta giả sử $m>n$. Khi đó gọi $p$ là một ước nguyên tố chung của $\gcd (a_m,a_n)$. Ta có :

$$a_m-k=a_{m-1}{a}_{m-2}...a_n..a_1⋮p\Rightarrow p\mid k$$

Suy ra :

$p\mid a_n-k$$=a_{n-1}(a_{n-1}-k)$$=a_{n-1}^2-k{a}_{n-1}$$\Rightarrow p\mid a_{n-1}^2$$\Rightarrow p\mid a_{n-1}$

Và lại suy ra :

$$p\mid a_{n-1}-k=a_{n-2}^2-k{a}_{n-2}\Rightarrow p\mid a_{n-2}^2\Rightarrow p\mid a_{n-2}$$

Cứ tiếp tục quá trình này ta suy ra $p\mid a_1=k+1$, suy ra $p\mid 1$. Mâu thuẫn.

Như vậy $\gcd (a_m,a_n)$ không có một ước nguyên tố nào, tức là $\gcd (a_m,a_n)=1$. Điều phải chứng minh.

Bài toán (Vietnamses Mathematical Olympiad 1987)

Cho hai dãy số $(x_n)$ và $(y_n)$ xác định bởi :

$$x_1=365,x_{n+1}=x_n(x_n^{1986}+1)+1622$$

và

$$y_1=16,y_{n+1}=y_n(y_n^3+1)-1952$$

Chứng minh rằng $\left|x_n-y_k\right|\ne 0,\forall n,k\in {\mathbb{Z}}^{+}$

Lời giải :

Chú ý $1987$ là số nguyên tố, từ đó theo định lí Fermat, ta có :

$$x_{n+1}=x_n^{1987}+x_n+1622\equiv 2x_n+1622(\mathrm{mod}1987)$$

Từ đó :

$$x_2\equiv 2x_1+1622\equiv 365(\mathrm{mod}1987)$$

Quy nạp ta được $x_n\equiv 365(\mathrm{mod}1987)$

Cũng bằng quy nạp ta được $y_n\equiv 16(\mathrm{mod}1987)$

Từ đó dễ thấy điều phải chứng minh.

Bài toán : (Vietnamese Mathematical Olympiad 1992)

Cho dãy số nguyên $(u_n)$ :

$$\{\begin{array}{c}{u}_1=1990,u_2=1989,u_3=2000\\ u_{n+3}=19u_{n+2}+9u_{n+1}+u_n+1991,\forall n\ge 1\end{array}$$

1) Với mỗi $n$, gọi $r_n$ là số dư khi chia $u_n$ cho $1992$. Chứng minh rằng dãy $(r_n)$ là dãy tuần hoàn.

2) Chứng minh rằng tồn tại vô số số $x$ của dãy $(u_n)$ sao cho :

$$1992\mid 5x^{1992}+4x^{1975}+5x^{1954}+8x^{1945}+2x^{1930}+11x^2+48$$

Lời giải :

1) Điều cần chứng minh hiển nhiên đúng theo định luật tuần hoàn của dãy số dư.

2) Chú ý $1992=\mathrm{3.83.8}$. Đặt $P(x)=5x^{1992}+4x^{1975}+5x^{1954}+8x^{1945}+2x^{1930}+11x^2+48$

Theo câu 1 ta có dãy $(r_n)$ tuần hoàn, gọi $t$ là chu kì tuần hoàn của nó. Ta có :

$$u_{st}=u_{st+3}-19u_{st+2}-9u_{st+1}-1991\equiv u_3-19u_2-9u_1-1991\equiv 84(\mathrm{mod}1992)$$

Từ đây ta suy ra :

$$u_{st}\equiv 0(\mathrm{mod}8)\Rightarrow P(u_{st})\equiv P(0)\equiv 0(\mathrm{mod}3)$$

$$u_{st}\equiv 4(\mathrm{mod}8)\Rightarrow P(u_{st})\equiv P(4)\equiv 0(\mathrm{mod}8)$$

$$u_{st}\equiv 1(\mathrm{mod}83)\Rightarrow P(u_{st})\equiv P(1)\equiv 83(\mathrm{mod}83)$$

Hơn nữa $\gcd (3,8)=\gcd (3,83)=\gcd (8,83)=1$ nên suy ra $P(x_{st})\equiv 0(\mathrm{mod}1992)$.

Điều phải chứng minh.

Bài toán (International Mathematical Olympiad Shortlist 1988)

Cho dãy số nguyên $(a_n)$ xác định bởi :

$$a_0=0,a_1=1,a_{n+2}=2a_{n+1}+a_n$$.

Chứng minh rằng $2^k\mid a_n$ khi và chỉ khi $2^k\mid n$.

Lời giải :

Bổ đề : Cho dãy số $(x_n)$ xác định bởi $x_1=a,x_2=b$ và :

$$x_{n+2}=b{x}_{n+1}+a{x}_n$$.

Khi đó với $m$ nguyên dương bất kỳ, ta có :

$$x_{m+n}=x_n{x}_{m+1}+x_{n-1}{x}_m(\ast )$$

Chứng minh bổ đề :

Ta chứng minh bằng quy nạp theo $m$, với $m=1$ thì hiển nhiên. Gỉa sử $(\ast )$ đúng với $m$ và $m-1$. Xét với $m+1$ :

$x_{m+n+1}$$=b{x}_{m+n}+a{x}_{m+n-1}$$=b\left(x_n{x}_{m+1}+x_{n-1}{x}_m\right)+a\left(x_n{x}_m+x_{n-1}{x}_{m-1}\right)$$=x_n(b{x}_{m+1}+a{x}_m)+x_{n-1}(b{x}_m+a{x}_{m-1})$$=x_n{x}_{m+2}+x_{n-1}{x}_{m+1}$

Quy nạp hoàn tất, như vậy ta có đẳng thức $(\ast )$.

Kết quả này là một kết quả quan trọng được dùng cho nhiều bài toán.

Trở lại bài toán :

Ta chọn $m=n$ trong $(\ast )$ thì ta được :

$$x_{2n}=x_n\left(x_{n-1}+x_{n+1}\right)=2x_n(x_n+x_{n-1})(\ast \ast )$$

Bằng quy nạp ta chứng minh được $a_{2n+1}$ lẻ và $a_{2n}$ chẵn. Như vậy $x_n+x_{n-1}$ lẻ.

Nếu $2^k\mid a_n$. Đặt $n=2^m.t$ với $t$ lẻ. Sử dụng $(\ast )$ ta được :

$$2^k\mid a_n=a_{2^m.t}\Rightarrow 2^{k-1}\mid a_{2^{m-1}.t}\Rightarrow 2^{k-2}\mid a_{2^{m-2}.t}$$

Nếu $k>m$ thì cứ tiếp tục quá trình này, ta được $2^{k-m}\mid a_t$ và điều này vô lí vì $a_t$ lẻ (do $t$ lẻ)

Vậy phải có $k\le m$, suy ra $2^k\mid 2^m.t=n$.

Nếu $2^k\mid n$. Đặt $n=2^k.t$ và cũng sử dụng $(\ast )$ ta có :

$2^0\mid a_t$$\Rightarrow 2^1\mid a_{2t}$$\Rightarrow 2^2\mid a_{2^2.t}$$\Rightarrow ...$$\Rightarrow 2^k\mid a_{2^k.t}$$=a_n$

Bài toán hoàn tất.

 

Bài toán (Putnam 1999)

Cho dãy số $(a_n)$ xác định bởi :

$$a_1=1,a_2=2,a_3=24$$ và $$a_n=\frac{6a_{n-1}^2{a}_{n-3}-8a_{n-1}{a}_{n-2}^2}{a_{n-2}{a}_{n-3}}(n\ge 4)$$

Chứng minh rằng $a_n$ là một số nguyên và $n\mid a_n$ với mọi số tự nhiên $n$.

Lời giải :

Ta viết công thức xác định dãy dưới dạng :

$a_n$$=\frac{6a_{n-1}^2}{a_{n-2}}-\frac{8a_{n-1}{a}_{n-2}}{a_{n-3}}$$\iff \frac{a_n}{a_{n-1}}$$=\frac{6a_{n-1}}{a_{n-2}}-\frac{8a_{n-2}}{a_{n-3}}$$\iff u_{n-1}$$=6u_{n-2}-8u_{n-3}\left(u_n=\frac{a_n}{a_{n-1}}\right)$

Và $u_1=2,u_2=12$. Ta tìm được công thức tổng quát của $(u_n)$ là :

$$u_n=4^n-2^n$$

Suy ra :

$a_n$$=(4^n-2^n)a_{n-1}$$=(4^n-2^n)(4^{n-1}-2^{n-1})a_{n-2}$$=...$$=\underset{k=1}{\prod ^n}(4^k-2^k)$$=2^{\frac{n(n+1)}{2}}.\underset{k=1}{\prod ^n}.\left(2^k-1\right)$

Như vậy $a_n$ nguyên với mọi $n$. Hơn nữa theo định lí Euler :

$$2^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

Do $\phi (n)\in \left\{1,2,3,...,n\right\}$ nên $\underset{k=1}{\prod ^n}.\left(2^k-1\right)\equiv 0(\mathrm{mod}n)$. Suy ra $n\mid a_n$ với mọi $n$. Bài toán hoàn tất.

Bài toán (Đề thi thử sức – Đồng hành cùng gặp gỡ toán học 2014)

Cho dãy số $(a_n)$ được xác định bởi :

$$\{\begin{array}{c}{a}_0=0,a_1=1\\ a_{n+2}=2014a_{n+1}-a_n,\forall n\ge 0\end{array}$$

Chứng minh rằng với mọi $n\ge 2$ thì $a_n$ là hợp số.

Lời giải :

Ta giải bài toán tổng quát hơn sau, cho $k$ là số nguyên dương và dãy $(a_n)$ xác định bởi :

$$\{\begin{array}{c}{a}_0=0,a_1=1\\ a_{n+2}=2k{a}_{n+1}-a_n,\forall n\ge 0\end{array}$$

Ta chứng minh với mọi $n\ge 2$ thì $a_n$ là hợp số.

Ta dễ dàng chứng minh được :

$$a_{2n}\equiv 0(\mathrm{mod}k)$$

$$a_{4n+1}\equiv 1(\mathrm{mod}k),a_{4n+3}\equiv -1(\mathrm{mod}k)$$

Từ đó $a_{2n}$ là hợp số  $(1)$

Tiếp theo :

Ta chứng minh bằng quy nạp :

$$a_{2n+1}=a_{n+1}^2-a_n^2(\ast )$$

$$2k{a}_{2n+2}=a_{n+2}^2-a_n^2(\ast \ast )$$.

Với $n=0$ ta có :

$$a_1=1=1-0=a_1^2-a_0^2$$

$$2k{a}_2=4k^2=4k^2-0=a_2^2-a_0^2$$

Gỉa sử có $(\ast )$ và $(\ast \ast )$. Xét với $n+1$ :

$$a_{2n+3}=2k{a}_{2n+2}-a_{2n+1}=(a_{n+2}^2-a_n^2)-(a_{n+1}^2-a_n^2)=a_{n+2}^2-a_{n+1}^2$$

$2k{a}_{2n+4}$$=4k^2.a_{2n+3}-2k{a}_{2n+2}$$=4k^2(a_{n+2}^2-a_{n+1}^2)-(a_{n+2}^2-a_n^2)$$=(4k^2-1)a_{n+2}^2-4k^2{a}_{n+1}^2+a_n^2$

Lại chú ý vì $a_{n+2}=2k{a}_{n+1}-a_n$ và $a_{n+3}=2k{a}_{n+2}-a_{n+1}$ nên ta được :

$$a_n=2k{a}_{n+1}-a_{n+2}$$ và $$a_{n+2}=\frac{a_{n+3}+a_{n+1}}{2k}$$

Suy ra :

$2k{a}_{2n+4}$$=(4k^2-1)a_{n+2}^2-4k^2{a}_{n+1}^2+a_n^2$$=\left(4k^2-1\right).\frac{(a_{n+3}+a_{n+1}{)}^2}{4k^2}-4k^2.a_{n+1}^2+(2k{a}_{n+1}-a_{n+2}{)}^2$$=\frac{4k^2-1}{4k^2}.(a_{n+3}+a_{n+1}{)}^2-4k{a}_{n+1}{a}_{n+2}+a_{n+2}^2$$=\frac{4k^2-1}{4k^2}(a_{n+3}+a_{n+1}{)}^2-4k.a_{n+1}.\frac{a_{n+3}+a_{n+1}}{2k}+\frac{(a_{n+3}+a_{n+1}{)}^2}{4k^2}$$=a_{n+3}^2-a_{n+1}^2$

Vậy theo nguyên lí quy nạp ta được :

$$a_{2n+1}=a_{n+1}^2-a_n^2(\ast )$$.

$$2k{a}_{2n+2}=a_{n+2}^2-a_n^2$$.

Với mọi số tự nhiên $n$.

Từ $(\ast )$ ta được $a_{2n+1}$ là hợp số   $(2)$

Từ $(1)(2)$ suy ra $a_n$ là hợp số với mọi $n\ge 2$

 

 

Bài này lấy ý tưởng từ tính chất của đa thức Chebyshev loại II :

Đa thức $U_n(x)$ biến $x$ và có bậc $n$ xác định bởi :

$$U_0(x)=1,U_1(x)=2x,U_{n+1}(x)=2x{U}_n(x)-U_{n-1}(x)$$.

Được gọi là đa thức Chebyshev loại II.

Có thể dễ dàng tìm được công thức của $U_n(x)$ là :

$U_n(x)$$=\frac{{\left(x+\sqrt{x^2-1}\right)}^n-{\left(x-\sqrt{x^2-1}\right)}^n}{(x+\sqrt{x^2-1})-(x-\sqrt{x^2-1})}$

Một số đa thức đầu tiên và phân tích ra nhân tử của chúng :

Bài trên đã khai thác tính chất sau của đa thức Chebyshev loại II :

$$U_{2n}(x)=U_n^2-U_{n-1}^2$$

$$2x{U}_{2n+1}(x)=U_{n+1}^2(x)-U_{n-1}^2(x)$$

Bài toán (Balkan Mathematical Olympiad 2009)

Giải phương trình

$$3^x-5^y=z^2$$

trên tập nghiệm nguyên dương.

Lời giải :

Bằng cách xét modulo $4$ ta được $x$ chẵn, đặt $x=2k$ với $t$ nguyên dương. Ta viết phương trình dưới dạng :

$$(3^k-z)(3^k+z)=5^y$$

Ta gọi $d=\gcd (3^k-z,3^k+z)$ ta được $d\mid (3^k-z)+(3^k+z)=2.3^t$. Lại có $d\mid (3^k-z)(3^k+z)=5^y$. Hai điều này mâu thuẫn nhau.

Như vậy phải có $\gcd (3^k-z,3^k+z)=1$. Ta được :

$$3^k-z=1$$ và $$3^k+z=5^y$$

Dẫn đến :

$$2.3^k=5^y+1$$

Dễ thấy $y=k=1$ thỏa. Ta xét $k,x>1$. Đưa về dạng :

$$5(5^{y-1}-1)=2.3(3^{k-1}-1)$$

Ta có :

$$3^{k-1}\equiv 1(\mathrm{mod}5)\Rightarrow 4=or{d}_5(3)\mid k-1$$

Từ đó :

$$5(5^{y-1}-1)=2.3(3^{k-1}-1)⋮2(3^4-1)⋮32$$

Suy ra :

$$5^{y-1}\equiv 1(\mathrm{mod}32)\Rightarrow 8=or{d}_{32}(5)\mid y-1$$

Kéo theo :

$$2.3(3^{k-1}-1)=5(5^{y-1}-1)⋮5^8-1⋮13$$

Như vậy :

$$3^{k-1}\equiv 1(\mathrm{mod}13)\Rightarrow 6=or{d}_{13}(3)\mid k-1$$

Lại suy ra :

$$5(5^{y-1}-1)=2.3(3^{k-1}-1)⋮3^6-1⋮7$$

Từ đó ta được :

$$5^{y-1}\equiv 1(\mathrm{mod}7)\Rightarrow 6=or{d}_7(5)\mid y-1$$

Nhưng lúc này thì :

$$2.3(3^{k-1}-1)=5(5^{y-1}-1)⋮5^6-1⋮9$$

Và đây là điều vô lí. Ta được nghiệm duy nhất của phương trình là $(x,y,z)=(2,1,2)$.