Phan Đình Trung: Số nguyên tố và hợp số

Bài toán 1 (CĐT VMO trường PTNK ĐHQG Tp HCM 2013-2014)

Cho dãy $\left \{ u_n \right \}$ thỏa mãn $\left\{\begin{matrix} u_1=2013\\ u_{n+1}=u_n^3-4u_n^2+5u_n \end{matrix}\right.\forall n\in \mathbb{N}^{*}$ . Tìm số nguyên tố $p$ thỏa mãn $p\equiv 3\;(mod\;4)$ và $p\mid u_{2014}+2009$

Lời giải :

Bổ đề quen thuộc : Với các số nguyên dương $x,y$ nguyên tố cùng nhau thì $x^2+y^2$ không có ước nguyên tố nào dạng $4k+3$

Bài toán :

Ta có $u_{n+1}=u_n^3-4u_n^2+5u_n-2=(u_n-1)^2(u_n-2)$

Do đó

$u_{2014}-2=(u_{2013}-1)^2(u_{2013}-2)=(u_{2013}-1)^2(u_{2012}-1)^2(u_{2012}-2)= (u_{2013}-1)^2(u_{2012}-1)^2...(u_1-1)^2 (u_1-2)=2011(u_1-1)^2(u_2-1)^2...(u_{2012}-1)^2(u_{2013}-1)^2$

Từ đó suy ra

$u_{2014}+2009=2011[(u_1-1)^2(u_2-1)^2...(u_{2012}-1)^2(u_{2013}-1)^2+1]$

Theo giả thiết ta có $p\equiv 3\;(mod\;4)$ và $p\mid u_{2014}+2009$ mà theo bổ đề thì $(u_1-1)^2(u_2-1)^2...(u_{2012}-1)^2(u_{2013}-1)^2+1$ không có ước nguyên tố nào dạng $4k+3$ .

Suy ra $p\mid 2011\Rightarrow p=2011$ .

Kết luận : Có duy nhất số nguyên tố $p$ thỏa mãn bài ra là $\boxed{p=2011}$

*Nhận xét : Các bài toán tương tự :

1) Cho dãy $\left \{ u_n \right \}$ xác định bởi $\left\{\begin{matrix} u_1=5\\ u_{n+1}=u_n^3-2u_n+2 \end{matrix}\right.$ . Tìm số nguyên tố $p$ thỏa mãn $p\equiv 3\;(mod\;4)$ và $p\mid u_{2011}+1$

2) (THTT số 437) Cho dãy số $(a_n)$ xác định bởi $a_1=34$ và $a_{n+1}=4a_n^3-104a_n^2-107a_n$ với mọi số nguyên dương $n$ . Tìm tất cả các số nguyên tố $p$ thỏa mãn $p\equiv 3\;(mod\;4)$ và $a_{2013}+1$ chia hết cho $p$

Bài toán 2 (Đề nghị Olympic 30-4 toán 10 năm 2011 THPT Hùng Vương, TpHCM) : Tìm các số tự nhiên $a,b$ sao cho $A=3^{9a^2+3b-86}+10$ là số nguyên tố.

Lời giải :

Nhận xét rằng phải có $9a^{2}+3b-86\geq 0$ . Ta luôn có $9a^{2}+3b-86\equiv 1\;\;(mod\;3)$

Đặt $9a^{2}+3b-86=3k+1\;\;(k\in \mathbb{N})$

Nếu $k$ chẵn thì $k=2t\;\;(t\in \mathbb{N})$ , khi đó $3^{9a^2+3b-86}=3^{3k+1}=3^{6k+1}\equiv 3\;\;(mod\;13)\Rightarrow A\equiv 0\;(mod\;13)$

Nhưng do $A\in \mathbb{P}$ nên $A=13$ , suy ra $9a^2+3b-86=1\Leftrightarrow 9a^2+3b=87$ .

Nhận xét rằng nếu $a\geq 4$ thì $9a^2+3b\geq 9a^{2}\geq 144>87$ , suy ra $a<4$ , tức là $a\in \left \{ 0,1,2,3\right \}$

Thử trực tiếp ta thu được $\left ( a,b \right )=(0,29),(1,26),(2,17),(3,2)$ .

Nếu $k$ lẻ thì $k=2t+1\;\;(t\in \mathbb{N})$ , khi đó $3^{9a^2+3b-86}=3^{3k+1}=3^{6t+7}\equiv 3\;\;(mod\;13)$ , lí luận hoàn toàn như trường hợp trên.

Kết luận : $\boxed{(a,b)=(0,29),(1,26),(2,17),(3,2)}$

Bài toán 3 : Tìm tất cả các số nguyên dương $n$ sao cho luôn tồn tại số nguyên $m$ thỏa mãn $2^n-1\mid m^2+9$ .

Lời giải :

Bổ đề 1 : Một số nguyên có dạng $4k+3$ thì luôn tồn tại một ước số nguyên tố $p\equiv 3\;(mod\;4)$

Chứng minh bổ đề 1 :

Số nguyên $a$ dạng $4k+3$ là một số lẻ nên nó không có ước nguyên tố $2$ .

Gỉa sử $a=p_{1}^{\alpha _1}p_{2}^{\alpha _{2}}...p_{n}^{\alpha _n}\;\;\;(p_i\in \mathbb{P},\alpha _i\in \mathbb{N}^*,i=\overline{1,n})$

Nếu $p_i\equiv 4\;(mod\;4)\;\forall i=1,2,...,n\Rightarrow a\equiv 1\;(mod\;4)$ , mâu thuẫn với giả thiết.

Do đó $a$ có ít nhất một ước nguyên tố $p\equiv 3\;(mod\;4)$

Bổ đề 2 : Nếu các số nguyên $x,y$ và số nguyên tố $p\equiv 3\;(mod\;4)$ thỏa mãn $p\mid x^2+y^2$ thì $p\mid x,p\mid y$ .

Chứng minh bổ đề 2 :

Nếu $p|x$ hoặc $p|y$ thì hiển nhiên ta có điều phải chứng minh. Xét $p\nmid x,p\nmid y$

Đặt $p=4k+3\qquad(k\in \mathbb{N})$

Theo định lí $Fermat$ nhỏ : $x^{4k+2}+y^{4k+2}\equiv x^{p-1}+y^{p-1}\equiv 2\;(mod\;p)\qquad(1)$

Mặt khác $x^{2}+y^2\equiv 0\;(mod\;p)\Rightarrow x^{4k+2}+y^{4k+2}\equiv 0\;(mod\;p)\qquad(2)$

Từ $(1)(2)$ suy ra $p=2$ , mâu thuẫn.

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

Nếu $n=1$ thì hiển nhiên với mọi $m$ nguyên, bài toán đều được thỏa mãn.

Xét $n>1$ . Gọi $q$ là một ước nguyên tố lẻ của $n$ , khi đó $2^{q}-1\equiv 3\;(mod\;4)$ nên $2^q-1$ có ít nhất một ước nguyên tố $p\equiv 3\;(mod\;4)$ . Khi đó dễ dàng thấy rằng :

$m^2+9\;\vdots \;2^{n}-1\;\vdots \;2^q-1\;\vdots\; p$

Khi đó theo bổ đề 2 ta có $p|3$ , $p=3$ . Suy ra $3\mid 2^{q}-1\Rightarrow 2\mid q$ , điều này mâu thuẫn vì $q$ lẻ.

Như vậy $n$ không có ước nguyên tố lẻ, do đó $n=2^k\;(t\in \mathbb{N}^{*})$ .

Ta sẽ chứng minh rằng với mọi $t\in \mathbb{N}^{*}$ thì $n=2^t$ luôn thỏa mãn đề bài.

Thật vậy,

Ta có $2^n-1=2^{2^{k}}-1=(2^{2^0}+1)(2^{2^1}+1)(2^{2^2}+1)...(2^{2^{t-1}}+1)$

Xét hệ đồng dư tuyến tính :

$\left\{\begin{matrix} x\equiv 0\;(mod\;2^{2^0}+1)\\ x\equiv 3.2^{2^{0}}\;(mod\;2^{2^1}+1)\\ x\equiv 3.2^{2^{1}}\;(mod\;2^{2^{2}}+1)\\ ...\\ x\equiv 3.2^{2^{k-2}}\;(mod\;2^{2^{k-1}}+1) \end{matrix}\right.$

Dễ thấy rằng $gcd(2^{2^i}+1,2^{2^j}+1)=1\;\forall i\neq ,j,i,j\in \left \{ 0,1,2,...,k-1 \right \}$ vì chúng là các số $Fermat$ .

Theo định lí phần dư Trung Hoa thì hệ này chắc chắn có nghiệm $x_0$ .

Ta suy ra

$\left\{\begin{matrix} x_{0}^{2}\equiv 0\equiv -9\;(mod\;2^{2^0}+1)\\ x_0^2\equiv 9.2^{2^{1}}\equiv -9\;(mod\;2^{2^1}+1)\\ x_0^2\equiv 9.2^{2^2}\equiv -9\;(mod\;2^{2^2}+1)\\ ...\\ x_0^2\equiv 9.2^{2^{k-1}}\equiv -9\;(mod\;2^{2^{k-1}}+1) \end{matrix}\right.\Rightarrow x_0^2+9\equiv 0\;(mod\;2^n-1)$

Khi đó với mọi $n=2^k$ thì luôn tồn tại số nguyên $m=x_0$ là nghiệm của hệ trên thỏa mãn đề bài.

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

Bài toán 3 (Đề thi chọn HSG lớp 12 tỉnh Đồng Nai 2013-2014) : Cho các số nguyên $a,b$ và số nguyên tố $p$ thỏa mãn $\dfrac{a^{2}+b^{2}}{p}\in \mathbb{Z}$ . Cho biết $p$ là tổng của hai số chính phương. Chứng minh rằng $\dfrac{a^{2}+b^{2}}{p}$ cũng là tổng của hai số chính phương.

Lời giải :

Đặt $p=c^2+d^2$ với $c,d\in \mathbb{Z}$

Ta có $\dfrac{a^2+b^2}{p}=\dfrac{(a^2+b^2)(c^2+d^2)}{p^2}=\dfrac{(ad+bc)^2+(ac-bd)^2}{p^2}=\left ( \dfrac{ad+bc}{p} \right )^2+\left ( \dfrac{ac-bd}{p} \right )^2=\left ( \dfrac{ad-bc}{p} \right )^2+\left ( \dfrac{ac+bd}{p} \right )^2$

Mặt khác :

$(ac+bd)(ac-bd)=a^2c^2-b^2d^2=a^2(c^2+d^2)-d^2(a^2+b^2)=a^2.p+d^2(a+b^2)\vdots p$

Nên hoặc $p|ac+bd$ hoặc $p|ac-bd$

Nếu $p|ac+bd$ thì $\dfrac{a^2+b^2}{p}=\left ( \dfrac{ac+bd}{p} \right )^2+\left ( \dfrac{ad-bc}{p} \right )^2$

Do $\dfrac{a^2+b^2}{p},\dfrac{ac+bd}{p}\in \mathbb{Z}\Rightarrow \dfrac{ad-bc}{p}\in \mathbb{Z}$

Suy ra $\dfrac{a^2+b^2}{p}$ là tổng của hai số chính phương.

Trường hợp $p|ac-bd$ tương tự.

Ta có điều phải chứng minh.

Bài toán 4 : Cho các số nguyên tố $a,b,c$ . Đặt $x = a+b-c,y=a+c-b,z=b+c-a$ . Biết rằng $x^2=y$ và hiệu $\sqrt{z}-\sqrt{y}$ là bình phương của một số nguyên tố. Tìm $a,b,c$

Lời giải :

Đặt

$\sqrt{z}-\sqrt{y}=p^{2}\qquad(p\in \mathbb{P})\Leftrightarrow (z+y)-2\sqrt{zy}=p^{4}\Leftrightarrow (a+c-b)+(b+c-a)-2\sqrt{(a+c-b)(b+c-a)}=p^{4}\Leftrightarrow 2c-2\sqrt{(a+c-b)(b+c-a)}=p^{4}\Rightarrow 2|p\Rightarrow p=2$

Như vậy ta sẽ giải hệ phương trình sau trên tập nghiệm nguyên tố :

$\left\{\begin{matrix} c-\sqrt{(a+c-b)(b+c-a)}=8 & (1)& \\ (a+b-c)^{2}=a+c-b&(2) & \end{matrix}\right.$

Từ $(1)$ :

$(c-8)^{2}=(a+c-b)(b+c-a)=c^{2}-(a-b)^{2}\Leftrightarrow (c-8)^{2}+(a-b)^{2}=c^{2}$

Đây là phương trình $Pytagore$ , hiển nhiên $gcd(c-8,a-b,c)=1$ do đó nghiệm tổng quát của nó là :

$\left\{\begin{matrix} x=2mn & \\ y=m^{2}-n^{2} & \\ z=m^{2}+n^{2} & \end{matrix}\right.$

Trong đó $m,n\in \mathbb{Z}$ , $gcd(m,n)=1$ , $m,n$ khác tính chẵn lẻ.

$\blacktriangledown$ Trường hợp 1 : $\left\{\begin{matrix} x=c-8=2mn & & \\ y=a-b=m^{2}-n^{2}& & \end{matrix}\right.$

Từ hệ dễ dàng suy ra $c=2$ , khi đó từ $(2)$ : $(a+b-2)^{2}=a-b+2\qquad(*)$ .

Mặt khác dễ dàng thấy hai số $a,b$ khác tính chẵn lẻ. Do đó $a=2$ hoặc $b=2$ , thay vào $(*)$ đều không thỏa mãn.

$\blacktriangledown$ Trường hợp 2 : $\left\{\begin{matrix} x=a-b=2mn & & \\ y=c-8=m^{2}-n^{2} & & \end{matrix}\right.$

Mặt khác, $c=m^2+n^2$ suy ra $m^{2}+n^{2}-8=m^{2}-n^{2}\Rightarrow n=\pm 2$ .

$a)$ Nếu $n=2$ : $\left\{\begin{matrix} c=m^{2}+4 & & \\ a-b=4m& & \end{matrix}\right.$

Thay vào $(2)$ : $\left ( a+b-m^{2}-4 \right )^{2}=m^{2}+4+4m=(m+2)^{2}\Leftrightarrow a+b-m^{2}-4=m+2\vee a+b-m^{2}-4=-m-2$

Trường hợp $a+b-m^{2}-4=m+2$ , ta có $a-b=4m$ . Từ đó suy ra $\left\{\begin{matrix} a=\dfrac{(m+2)(m+3)}{2} & & \\ b=\dfrac{m^{2}-3m+6}{2}& & \end{matrix}\right.$

Vì $gcd(m,n)=gcd(m,2)=1$ nên $m$ lẻ. Đặt $m=2k+1\qquad(k\in \mathbb{Z})$ . Ta có $a=\dfrac{(m+2)(m+3)}{2}=\dfrac{(2k+3)(2k+4)}{2}=(2k+3)(k+2)$ .

Vì $a$ nguyên tố nên $2k+3=\pm 1$ hoặc $k+2=\pm 1$ . Ta thấy $k=-3$ thỏa mãn vì khi đó $a=3$ . Từ đó $m=-5,b=23,c=29$

Trường hợp $a+b-m^{2}-4=-m-2$ , ta có $a-b=4m$ . Từ đó $\left\{\begin{matrix} a=\dfrac{(m+1)(m+2)}{2} & & \\ b=\dfrac{m^{2}-5m+2}{2} & & \end{matrix}\right.$

Tương tự trên ta thấy $m$ lẻ, đặt $m=2k+1\qquad(k\in \mathbb{Z})$ . Khi đó $a=\dfrac{(m+1)(m+2)}{2}=\dfrac{(2k+2)(2k+3)}{2}=(k+1)(2k+3)$ .

Vì $a$ nguyên tố nên $2k+3=\pm 1$ hoặc $k+1=\pm 1$ . Mọi giá trị của $k$ tìm được đều không thỏa mãn

$b)$ Nếu $n=-2$ . Giải tương tự trường hợp $a$ .

Kết luận : $\boxed{(a;b;c)=(3;23;29)}$

Bài toán 5 (Đề nghị Olympic 30-4 toán 10 2010 THPT Chuyên Vị Thanh tỉnh Hậu Giang)

Tìm tất cả các số nguyên dương $n$ sao cho phần nguyên của biểu thức $A=\dfrac{n^{3}+8n^{2}+1}{3n}$ là một số nguyên tố

Lời giải :

Ta có $A=\dfrac{n^{3}+8n^{2}+1}{3n}=\dfrac{n^{2}}{3}+2n+\dfrac{2n}{3}+\dfrac{1}{3n}$

Trường hợp 1 : Xét $n = 3k$ ( $k\in \mathbb{Z}^{+}$ ) :

$A=\dfrac{(3k)^{2}}{3}+2.(3k)+\dfrac{2.(3k)}{3}+\dfrac{1}{3.(3k)}=3k^{2}+8k+\dfrac{1}{9k}$

Do đó $\left [ A \right ]=3k^{2}+8k=k(3k+8)$

Để $\left [ A \right ]\in \mathbb{P}$ thì $k = 1$

Trường hợp 2 : Xét $n = 3k+1$ ( $k\in \mathbb{N}$ )

$A=\dfrac{(3k+1)^{2}}{3}+2(3k+1)+\dfrac{2(3k+1)}{3}+\dfrac{1}{3(3k+1)}=3k^{2}+10k+3+\dfrac{1}{9k+3}$

Do đó $\left [ A \right ]=3k^{2}+10+3=(k+3)(3k+1)$

Để $\left [ A \right ]\in \mathbb{P}$ thì $k=0$

Trường hợp 3 : Xét $n = 3k+2$ ( $k\in \mathbb{N}$ )

$A=\dfrac{(3k+2)^{2}}{3}+2(3k+2)+\dfrac{2(3k+2)}{3}+\dfrac{1}{3(3k+2)}=3k^{2}+12k+6+\dfrac{2}{3}+\dfrac{1}{3(3k+2)}$

Hiển nhiên $\dfrac{1}{3(3k+2)}<\dfrac{1}{3}\Rightarrow \dfrac{2}{3}+\dfrac{1}{3(3k+2)}<1\Rightarrow \left [ A \right ]=3k^{2}+12k+6$

Do $3|\left [ A \right ]$ và $\left [ A \right ]>3$ nên $\left [ A \right ]$ là hợp số.

Kết luận : $\boxed{n\in \left \{ 1;3 \right \}}$

Nhận xét : Ta xét số dư của số $n$ khi chia cho $3$ là vì mẫu số là một biểu thức chia hết cho $3$ .

Bài toán 6 (IMO 2001) : Cho bốn số nguyên $a,b,c,d$ thỏa mãn điều kiện :

$\left\{\begin{matrix} a>b>c>d>0 & & \\ ac+bd=(b+d+a-c)(b+d-a+c)& & \end{matrix}\right.$

Chứng minh rằng $ab + cd$ là hợp số.

Lời giải :

Gỉa thiết đã cho tương đương :

$ac+bd=(b+d+a-c)(b+d-a+c)=(b+d)^{2}-(a-c)^{2}=(b^{2}+d^{2}+2bd)-(a^{2}+c^{2}-2ac)\Leftrightarrow a^{2}-ac+c^{2}=b^{2}+bd+d^{2}$

Do đó :

$(ab+cd)(ad+bc)=bd(a^{2}+c^{2})+ac(b^{2}+d^{2})=bd(a^{2}-ac+c^{2})+ac(b^{2}+bd+d^{2})=(ac+bd)(a^{2}-ac+c^{2})\qquad(*)$

Chú ý rằng với điều kiện $a>b>c>d>0$ ta có :

$\left\{\begin{matrix} (ab+cd)-(ac+bd)=(a-d)(b-c) >0& & \\ (ac+bd)-(ad+bc)=(a-b)(c-d)>0& & \end{matrix}\right.$

$\Rightarrow ab+cd>ac+bd>ad+bc$

Gỉa sử $ab + cd$ là một số nguyên tố, vì $ab + cd > ac+bd$ nên $gcd(ab+cd,ac+bd)=1$

Mặt khác, từ $(*)$ ta có :

$(ac+bd)|(ab+cd)(ad+bc)$ vì $gcd(ab+cd,ac+bd)=1$ nên $(ac+bd)|(ad+bc)$ .

Điều này là vô lí vì $ac + bd > ad + bc > 0$

Vậy : Gỉa thiết phản chứng sai, $ab + cd$ phải là hợp số

Bài toán 7 : Tìm bảy số nguyên tố sao cho tổng các lũy thừa bậc 6 của chúng bằng tích của chúng.

Lời giải :

Gọi bảy số nguyên tố cần tìm là $p_{1},p_{2},...,p_{7}$ .

Theo đề bài ta có $p_{1}^{6}+p_{2}^{6}+...+p_{7}^{6}=p_{1}p_{2}...p_{7}$

Gỉa sử tất cả các số nguyên tố $p_{1},p_{2},...,p_{7}$ đều không chia hết cho $7$ .

Theo định lí $Fermat$ nhỏ ta có $p_{i}^{6}\equiv 1(mod7)\Rightarrow \sum_{i=1}^{7}p_{i}^{6}\equiv 0(mod7)\Rightarrow p_{1}p_{2}...p_{7}\equiv 0(mod7)$

Điều này là vô lí vì $7\nmid p_{i}$

Do đó ít nhất một trong các số nguyên tố $p_{1},p_{2},...,p_{7}$ chia hết cho $7$ , giả sử $7|p_{7}\Rightarrow p_{7}=7$

Khi đó ta lại có $p_{1}^{6}+...+p_{6}^{6}+7^{6}=7p_{1}p_{2}...p_{6}$

Lại giả sử $p_{1},p_{2},...,p_{6}$ đều không chia hết cho $7$ .

$\Rightarrow p_{i}^{6}\equiv 1(mod7)\Rightarrow \sum_{i=1}^{6}p_{i}^{6}\equiv 6(mod7)$

Điều này là vô lí vì $\sum_{i=1}^{6}p_{i}^{6}=7p_{1}p_{2}...p_{6}-7^{6}\equiv 0(mod7)$

Suy ra ít nhất một trong các số $p_{1},p_{2},...,p_{6}$ phải chia hết cho $7$ . Gỉa sử $7|p_{6}\Rightarrow p_{6}=7$

Tiếp tục như vậy, cuối cùng ta có $p_{i}=7$

Kết luận : $\boxed{p_{1}=p_{2}=...=p_{7}=7}$

Bài toán 8 : Cho $a,b,c$ là ba số nguyên khác $0$ và $a\neq c$ sao cho $\dfrac{a}{c}=\dfrac{a^{2}+b^{2}}{c^{2}+b^{2}}$ . Chứng minh rằng $a^{2}+b^{2}+c^{2}$ không phải là một số nguyên tố.

Lời giải :

Từ giả thiết $\dfrac{a}{c}=\dfrac{a^{2}+b^{2}}{c^{2}+a^{2}}\Rightarrow ac^{2}+ab^{2}=a^{2}c+b^{2}c\Rightarrow (ac-b^{2})(c-a)=0$

Vì $a\neq c$ nên phải có $ac=b^{2}$

$\blacktriangledown$ Trường hợp 1 : Nếu $gcd(a,c)=d>1\qquad(d\in \mathbb{N})$

Đặt $\left\{\begin{matrix} a=dx & & \\ c=dy& & \end{matrix}\right.\qquad(x,y\in \mathbb{Z},gcd(x,y)=1)$

Do đó $a^{2}+b^{2}+c^{2}=a^{2}+ac+c^{2}=d^{2}(x^{2}+xy+y^{2})$

Dễ thấy $d^{2}>1$ và $d^{2}$ không thể là một số nguyên tố.

Do đó trường hợp này ta có $a^{2}+b^{2}+c^{2}$ là hợp số

$\blacktriangledown$ Trường hợp 2 : Nếu $gcd(a,c)=1$ thì vì $ac=b^{2}\Rightarrow \left\{\begin{matrix} a=m^{2} & & \\ c=n^{2}& & \end{matrix}\right.\vee \left\{\begin{matrix} a=-m^{2} & & \\ c=-n^{2}& & \end{matrix}\right.\left ( m,n\in \mathbb{Z} \right )$