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

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

$$\{\begin{array}{c}{a}_1=1964,a_2=96\\ a_{n+2}=30a_{n+1}^2-75a_{n+1}{a}_n-1944a_n(n\ge 1)\end{array}$$

Chứng minh rằng không có một số hạng nào của dãy biểu diễn được dưới dạng tổng của ba lũy thừa bậc bảy của ba số nguyên.

Lời giải :

Từ đề bài :

$$a_{n+2}\equiv a_{n+1}^2-17a_n{a}_{n+1}-a_n(mod29)$$

Ta thấy :

$$a_1=1964\equiv -8(mod29)$$

$$a_2=96\equiv 9(mod29)$$

$$a_3\equiv 9^2-\mathrm{17.9.}(-8)+8\equiv 8(mod29)$$

$$a_4\equiv 8^2-\mathrm{17.8.9}-9\equiv -9(mod29)$$

$$a_5\equiv (-9{)}^2-17.(-9).8-8\equiv -8(mod29)$$

$$a_6\equiv (-8{)}^2-17.(-8).(-9)+9\equiv 9(mod29)$$

$$...$$

Bằng quy nạp ta được $a_n\equiv \pm 8,\pm 9(mod29)$.

Với số nguyên $a$ bất kì, cho $a$ chạy trên hệ thặng dư đầy đủ modulo $29$, ta được

$$a^7\equiv 0,\pm 1,\pm 12(mod29)$$

Do đó với các số nguyên $A,B,C$ thì :

$$A^7+B^7+C^7\equiv 0,\pm 1,\pm 2,\pm 3,\pm 4,\pm 5,\pm 10,\pm 11,\pm 12,\pm 13,\pm 14(mod29)$$

Từ hai kết quả trên ta có điều phải chứng minh.

Bài toán (Vietnam Team Selection Test 2004)

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

$$\{\begin{array}{c}{x}_1=630,x_2=102\\ x_{n+2}=x_{n+1}+x_n+2\sqrt{x_n{x}_{n+1}-2},\forall n\ge 1\end{array}$$

a) Chứng minh rằng mọi số hạng của dãy đều là số nguyên dương.

b) Chứng minh có vô số số nguyên dương $n$ sao cho $x_n$ có bốn chữ số tận cùng là $2003$.

b) Chứng minh rằng không tồn tại số nguyên dương $n$ sao cho $x_n$ có bốn chữ số tận cùng là $2004$.

Lời giải :

a) Biến đổi công thức ban đầu :

$(x_{n+2}-x_{n+1}-x_n{)}^2$$=4(x_n{x}_{n+1}-2)$$\iff x_{n+2}^2+x_{n+1}^2+x_n^2-2x_{n+2}{x}_{n+1}-2x_{n+1}{x}_n-2x_n{x}_{n+2}$$=-8(\ast )$

Thay $n$ bởi $n+1$ ta được :

$$x_{n+3}^2+x_{n+2}^2+x_{n+1}^2-2x_{n+3}{x}_{n+2}-2x_{n+2}{x}_{n+1}-2x_{n+1}{x}_{n+3}=-8(\ast \ast )$$

Trừ $(\ast \ast )$ cho $(\ast )$ vế theo vế :

$x_{n+3}^2-x_n^2-2x_{n+3}{x}_{n+2}+2x_{n+1}{x}_n-2x_{n+1}{x}_{n+3}+2x_n{x}_{n+2}$$=0$$\iff (x_{n+3}-x_n)(x_{n+3}+x_n-2x_{n+2}-2x_{n+1})$$=0$

Dễ thấy $(x_n)$ là một dãy tăng nên phải có :

$$x_{n+3}=2x_{n+2}+2x_{n+1}-x_n$$

Từ đây bằng quy nạp ta được mọi số hạng của dãy đều nguyên dương.

b) Ta gọi $r_n$ là số dư khi chia $x_n$ cho $10^4$ ứng với mỗi số nguyên dương $n$. Ta sẽ chứng minh dãy $(r_n)$ là dãy tuần hoàn.

Ta có :

$$r_{n+3}\equiv 2r_{n+2}+2r_{n+1}-r_n(mod10^4)$$

Xét dãy các bộ số :

$$(r_1,r_2,r_3),(r_2,r_3,r_4),...,(r_n,r_{n+1},r_{n+2}),...$$

Dãy trên có vô số bộ nhưng chỉ có hữu hạn bộ khác nhau đôi một vì $r_i\in \left\{0,1,2,...,10^4-1\right\}$

Vì thế theo nguyên lí Dirichlet, chắc chắn sẽ có hai bộ trùng nhau. Tức là tồn tại các số nguyên dương $m,k$ sao cho :

$$(r_m,r_{m+1},r_{m+2})=\left(r_{m+k},r_{m+k+1},r_{m+k+2}\right)$$

Ta có :

$r_{m-1}$$\equiv 2r_m+2r_{m+1}-r_{m+2}$$=2r_{m+k}+2r_{m+k+1}-r_{m+k+2}$$\equiv r_{m+k-1}(mod10^4)$

$$...$$

$$r_1\equiv 2r_2+2r_3-r_4\equiv 2r_{k+2}+2r_{k+3}-r_{k+4}\equiv r_{k+1}(mod10^4)$$

Tức là ta đã chứng minh được :

$$(r_1,r_2,r_3)=(r_{k+1},r_{k+2},r_{k+3})$$

Vậy dãy $(r_n)$ là dãy tuần hoàn chu kỳ $k$. Hơn nữa vì $x_4=2003$ nên $r_4=2003$. Do dãy $(r_n)$ tuần hoàn nên tồn tại vô hạn số hạng của dãy $(r_n)$ bằng $2003$. Điều này đồng nghĩa với việc tồn tại vô hạn số hạng của dãy $(x_n)$ tận cùng bằng $2003$.

c) Ta thấy $x_1=603\equiv 3(mod4)$ và $x_2=102\equiv 2(mod4),x_3=1201\equiv 1(mod4)$

Nên :

$$x_4=2x_3+2x_2-x_1\equiv 3(mod4)$$

$$x_5=2x_4+2x_3-x_2\equiv 2(mod4)$$

$$x_6=2x_5+2x_4-x_3\equiv 1(mod4)$$

Từ đó bằng quy nạp ta chứng minh được :

$$4\nmid x_n,\forall n\ge 1$$

Như vậy $x_n$ không thể tận cùng bằng $2004$. Bài toán hoàn tất.

Bài toán (Middle European Mathematical Olympiad 2009)

Tìm bộ ba số nguyên không âm $(x,y,z)$ thỏa mãn phương trình :

$$2^x+2009=3^y{5}^z$$

Lời giải :

Với $x=0,1,2$ thì không tồn tại $x,y,z$ thỏa đề. Ta chỉ xét $x\ge 3$.

Dễ thấy khi đó :

$$2^x+2009\equiv 1(mod4)$$

Kéo theo $3^y{5}^z\equiv 1(mod4)$, suy ra $y$ chẵn.

Cũng dễ thấy $2^x+2009\equiv 1(mod8)$. Suy ra $3^y{5}^z\equiv 1(mod8)$. Do $y$ chẵn nên $3^y\equiv 1(mod8)$. Suy ra $5^z\equiv 1(mod8)$. Vậy $z$ cũng chẵn.

Tiếp theo xét theo modulo $3$ :

Nếu $y=0$ thì được $2^x+2009=5^z$. Từ đây suy ra $2^x\equiv 1(mod5)\Rightarrow 4\mid x$.

Ta đưa được về dạng tích :

$$\left(5^{z/2}-2^{x/2}\right)(5^{z/2}+2^{x/2})=2009$$

Phương trình này không cho nghiệm nguyên không âm.

Ta chỉ xét $y\ge 1$. Từ đó mà :

$$2^x+2009=3^y{5}^z\equiv 0(mod3)\Rightarrow 2^x\equiv 1(mod3)\Rightarrow 2\mid x$$

Ta có $x,y,z$ đều chẵn nên đặt $x=2a,y=2b,z=2c$ với $a,b,c\in \mathbb{N}$.

Ta đưa phương trình về dạng :

$$(3^b{5}^c-2^a)(3^b{5}^c+2^a)=2009$$

Nếu gọi $d=\gcd (3^b{5}^c-2^a,3^b{5}^c+2^a)$ thì có $d\mid 2^{a+1}$. Dễ lập luận được $d=1$. Do vậy :

$$\{\begin{array}{c}{3}^b{5}^c-2^a=1\\ 3^b{5}^c+2^a=2009\end{array}\Rightarrow 2^{a+1}=2008$$

Không tìm được số tự nhiên $a$ thỏa mãn điều này.

Kết luận là không tồn tại bộ ba số nguyên không âm nào thỏa mãn phương trình đề bài.

Bài toán (Iran National Mathematical Olympiad 3rd Round 2005)

Tìm các số nguyên dương $n,p,q$ thỏa mãn :

$$2^n+n^2=3^p{7}^q$$

Lời giải :

Dễ thấy $n$ lẻ. Nếu $n=1$ thì $3^p{7}^q=3$, vô lí. Do đó $n\ge 3$. Như vậy thì $8\mid 2^n$.

Ta có :

$$3^p{7}^q=2^n+n^2\equiv 1(mod8)$$.

Nếu $p,q$ cùng lẻ thì $3^p{7}^q\equiv 5(mod8)$. Nếu $p$ lẻ và $q$ chẵn thì $3^p{7}^q\equiv 3(mod8)$. Nếu $p$ chẵn và $q$ lẻ thì $3^p{7}^q\equiv 7(mod8)$. Tất cả đều mâu thuẫn. Do vậy $p,q$ cùng chẵn.

Đặt $p=2a,q=2b$ với $a,b$ nguyên dương. Ta được phương trình tích :

$$(3^a{7}^b-n)(3^a{7}^b+n)=2^n$$

Nếu gọi $d=\gcd (3^a{7}^b-n,3^a{7}^b+n)$ thì có $d\mid 2.3^a.7^b$.

Hiển nhiên $21\mid d$ vì nếu vậy ta suy ra $21\mid 2^n$, mâu thuẫn. Do đó $d=2$.

Ta được :

$$\{\begin{array}{c}{3}^a{7}^b-n=2\\ 3^a{7}^b+n=2^{n-1}\end{array}$$

Ta được phương trình :

$$2^{n-2}=1+n$$

Rõ ràng với $n\ge 5$, ta hoàn toàn chứng minh được bằng quy nạp rằng $2^{n-2}>n+1$. Suy ra $n=4$, mâu thuẫn vì $n$ lẻ.

Do vậy không tồn tại bộ số thỏa mãn bài ra.

Bài toán : Cho số nguyên tố $p\equiv 2(mod3)$ và dãy $a_k=k^2+k+1$ với $k=1,2,...,p-1$. Chứng minh rằng :

$$a_1{a}_2...a_{p-1}\equiv 3(modp)$$

Lời giải :

Bổ đề 1 : Cho số nguyên tố $p\equiv 2(mod3)$. Khi đó ta có $a\equiv b(modp)\iff a^3\equiv b^3(modp)$

Chứng minh bổ đề 1 :

Nếu $a\equiv b(modp)$ thì hiển nhiên là $a^3\equiv b^3(modp)$. Gỉa sử $a^3\equiv b^3(modp)\Rightarrow p\mid (a-b)(a^2+ab+b^2)$

Nếu $p\mid a-b$ thì ta hoàn tất bổ đề.

Nếu $p\mid a^2+ab+b^2\Rightarrow p\mid 4(a^2+ab+b^2)\Rightarrow (a+2b{)}^2+3a^2\equiv 0(modp)\Rightarrow \left(\frac{-3}{p}\right)=1$.

Suy ra $p\equiv 1(mod3)$. Mâu thuẫn.

Bổ đề 2 : Cho số nguyên tố $p\equiv 2(mod3)$. Khi đó ta có $\left\{2^3-1,3^3-1,...,p^3-1\right\}$ là hệ thặng dư thu gọn modulo $p$.

Chứng minh bổ đề 2 :

Nếu tồn tại $i,j$ với $i,j\in \left\{2,3,..,p\right\}$ sao cho :

$$i^3-1\equiv j^3-1(modp)\Rightarrow i^3\equiv j^3(modp)$$

Theo bổ đề 1 ta có $i\equiv j(modp)$ và điều này vô lí. Bổ đề 2 chứng minh hoàn tất.

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

Theo bổ đề 2 ta có :

$(2^3-1)(3^3-1)...(p^3-1)$$\equiv \mathrm{1.2.3...}(p-1)(modp)$$\iff (2^2+2+1)(3^2+3+1)...(p^2+p+1)$$\equiv 1(modp)$$\iff a_2{a}_3...a_p$$\equiv 1(modp)$

Lại chú ý rằng $a_1=1^2+1+1\equiv 3(modp),a_p=p^2+p+1\equiv 1(modp)$ nên :

$$a_1{a}_2...a_{p-1}\equiv 3(modp)$$

Bài toán : Chứng minh rằng với mọi số nguyên $k$, $k<m$ thì luôn tồn tại số nguyên $h$ sao cho $h{p}^m+p^k⋮k!$

Lời giải :

Đặt $k!=p^a.t(gcd(t,a)=1)$

Để ý rằng tập $\left\{0,p^{m-k},2p^{m-k},...,(t-1)p^{m-k}\right\}$ chính là hệ thặng dư đầy đủ modulo $t$ nên tồn tại số nguyên $h$ sao cho $h.p^{m-k}\equiv -1(modt)\iff h.p^{m-k}+1⋮t\iff h.p^m+p^k⋮p^{k}t$

Lại theo định lí $Legendre$ thì $a=\underset{i=1}{\sum ^{+\infty }}\lfloor \frac{k}{p^i}\rfloor \le \underset{i=1}{\sum ^{+\infty }}\frac{k}{p^i}<k$

Tức là $p^k⋮p^a$

Từ đó suy ra $h.p^m+p^k⋮p^{a}t\iff h.p^m+p^k⋮k!$. Đây là điều phải chứng minh.

 

Bài toán : Cho các số nguyên dương nguyên tố cùng nhau $m,n$. Chứng minh rằng :  $m^{\phi (n)}+n^{\phi (m)}\equiv 1(modmn)$

Lời giải :

Áp dụng định lí $Euler$ :

$m^{\phi (n)}$$\equiv 1(modn)$$\Rightarrow m^{\phi (n)}+n^{\phi (m)}$$\equiv 1(modn)$$\Rightarrow m^{\phi (n)}+n^{\phi (m)}$$=np+1(p\in \mathbb{N})$

Hoàn toàn tương tự thì :

$m^{\phi (n)}+n^{\phi (m)}$$\equiv 1(modm)$$\Rightarrow np+1$$\equiv 1(modm)$$\Rightarrow np$$\equiv 0(modm)$.

Mà $gcd(m,n)=1\Rightarrow m|p\Rightarrow p=mq(q\in \mathbb{N})\Rightarrow m^{\phi (n)}+n^{\phi (m)}=mnq+1$

Hay $m^{\phi (n)}+n^{\phi (m)}\equiv 1(modmn)$. Đây là điều phải chứng minh

 

Bài toán : Tìm số nguyên dương $n$ sao cho :

$$a)$$ $$\phi (n)=\frac{n}{2}$$       $$b)$$ $$\phi (n)=\frac{n}{3}$$

Lời giải :

Gỉa sử $n=p_1^{e_1}{p}_2^{e_2}...p_m^{e_m}$ với $p_i\in \mathbb{P},e_i\in {\mathbb{Z}}^{+},i=\overline{1,m}$

a) Ta có $\phi (n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_m}\right)=\frac{n}{2}\Rightarrow 2{\prod }_{i=1}^m\left(p_i-1\right)={\prod }_{i=1}^m{p}_i$

Gỉa sử trong các số $p_i$ có $t$ số lẻ, khi đó :

$$2^{t+1}\parallel 2\prod _{i=1}^m{p}_i\Rightarrow 2^{t+1}\parallel \prod _{i=1}^m{p}_i$$.

Suy ra có $t+1$ số chẵn trong các số $p_i$ $\Rightarrow t=0,m=1$

Kết luận : $\boxed{n=2^k}(k\in {\mathbb{N}}^{\ast })$

 

b) Ta có $\phi (n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_m}\right)=\frac{n}{3}\Rightarrow 3{\prod }_{i=1}^m\left(p_i-1\right)={\prod }_{i=1}^m{p}_i$

Gỉa sử trong các số $p_i$ có $t$ số lẻ, khi đó :

$$2^t\parallel 3\prod _{i=1}^m(p_i-1)\Rightarrow 2^t\parallel \prod _{i=1}^m{p}_i$$

Suy ra có $t$ số chẵn trong các số $p_i$ $\Rightarrow t=1,m=2$

Ta có phương trình $3(2-1)(p_1-1)=2.p_1\Rightarrow p_1=3$.

Kết luận : $\boxed{n=2^k.3^s}(k,s\in {\mathbb{N}}^{\ast })$