Chủ đề này có 2 trả lời

[dactai10a1]

Có tồn tại hay không số nguyên dương n thỏa n có đúng 2000 ước nguyên tố phân biệt và ${2^n} + 1 \vdots n$

[nguyenta98]

Có tồn tại hay không số nguyên dương n thỏa n có đúng 2000 ước nguyên tố phân biệt và ${2^n} + 1 \vdots n$

Giải như sau:
Dễ cm $n$ là số lẻ
Giả sử $p$ là ước nguyên tố nhỏ nhất của $n$ suy ra $p$ lẻ
$$2^n+1 \vdots n \Leftrightarrow 2^{2n}-1 \vdots n \Leftrightarrow 2^{2n}-1 \vdots p$$
Giả sử $2^k-1 \vdots p$ với $k$ nhỏ nhất suy ra $2n \vdots k$
Mặt khác theo Fermat nhỏ $2^{p-1}-1 \vdots p$ nên $p-1 \vdots k \Rightarrow p>k$
Lại có $2n \vdots k$ suy ra $gcd(n,k)=1$ vì nếu $n,k \vdots r$ với $r$ nguyên tố suy ra $k \vdots r \Rightarrow r<p$ (do $k<p$) suy ra $r$ là ước nguyên tố của $n$ mà $r<p$ vô lý vì $p$ đã nhỏ nhất
Suy ra $gcd(n,k)=1 \rightarrow 2 \vdots k \Rightarrow k=1,2$
TH1: $k=1 \Rightarrow 2^1-1=1 \vdots p$ vô lý
TH2: $k=2 \Rightarrow 2^2-1=3 \Rightarrow p=3$
Suy ra $n=3^t.x$ với $gcd(x,t)=1$
Như vậy $2^n+1=2^{3^t.x}+1$
Ta sẽ chứng minh $2^{3^t}+1 \vdots 3^t$
Thấy $t=1$ đúng
Giả sử $t=u$ đúng hay $2^{3^u}+1 \vdots 3^u$
Ta sẽ cm $t=u+1$ đúng hay $2^{3^{u+1}}+1 \vdots 3^{u+1}$
Thật vậy $2^{3^{u+1}}+1=(2^{3^u}+1)\left(\left(2^{3^u}\right)^2-2^{3^u}+1\right)$
Theo GTQN suy ra $2^{3^u}+1 \vdots 3^u$ suy ra $2^{3^u} \equiv -1 \pmod{3} \Rightarrow \left(2^{3^u}\right)^2-2^{3^u}+1 \vdots 3$
Suy ra $2^{3^{u+1}}+1 \vdots 3^{u+1}$ hoàn tất cm
Cho nên từ trên ta có $2^n+1 \vdots n \Rightarrow 2^{3^t.x}+1 \vdots 3^t.x$
Ta thấy $2^{3^t.x}+1 \vdots 3^t$ (theo cm quy nạp trên)
Giờ việc ta cần là $2^{3^t.x}+1 \vdots x$ với $gcd(x,3)=1$
Hay $\left(2^{3^t}\right)^x+1 \vdots x$
Mệnh đề: Ta thấy xét số $2^{3^t}+1$ hoàn toàn có thể chọn $t$ đủ lớn để có trên $1999$ ước số nguyên tố khác $3$ phân biệt, gọi các ước là $p_1,p_2,...,p_{1999}$
Khi đó $x=p_1.p_2...p_{1999}$ thì $2^{3^t.x}+1 \vdots (2^{3^t}+1) \vdots p_1.p_2...p_{1999}$ nên thỏa đề
Do đó $n=3^t.p_1.p_2...p_{1999}$ với $p_i \neq 3$ có $2000$ ước nguyên tố nên câu trả lời là tồn tại
$$**********$$
Ta chứng minh mệnh đề phụ trợ ở trên: Tồn tại $t$ đủ lớn để $2^{3^t}+1$ có từ $g$ ước nguyên tố phân biệt khác $3$ trở lên
Ta xét số $2^{3^t}+1=(2^{3^{t-1}}+1)\left(\left(2^{3^{t-1}}\right)^2-2^{3^{t-1}}+1\right)$
Thấy $(2^{3^{t-1}}+1)$ cũng phân tích tương tự được như trên
Cho nên đến đoạn cuối cùng thì $2^{3^{t}}+1=3.(...).(...)...(...)$ với $(...)$ là số có dạng $a^2-a+1$ và $a=2^{3^{t-k}}$
Giờ ta chứng minh các $(...)$ nếu có ước chung thì chỉ có ước chung là $3$
Thật vậy xét hai $(...)$ và $(...)$ bất kì là $a^2-a+1$ và $b^2-b+1$ với $a=2^{3^m}$ và $b=2^{3^n}$
WLOG $n>m$
Do đó $n-m=d$ nên $b=2^{3^{m+d}}=(2^{3^m})^{3^d}=a^{3^d}$
Suy ra
$b^2-b+1=a^{2.3^d}-a^{3^d}+1$
$=a^{2.3^d}+2-(a^{3^d}+1)=a^{2.3^d}-1-(a^{3^d}+1)+3$
$=(a^{3^d}-1)(a^{3^d}+1)-(a^{3^d}+1)+3$
Ta thấy $(a^{3^d}-1)(a^{3^d}+1)-(a^{3^d}+1) \vdots a^{3^d}+1$ mà dễ cm $a^{3^d}+1 \vdots a^2-a+1$ (ta cứ phân tích dần dần theo hằng đẳng thức $u^3-v^3$)
Do đó nếu $gcd(a^2-a+1,b^2-b+1)=l \Rightarrow 3 \vdots l$ suy ra $l=3,1$
Như vậy ta hoàn tất chứng minh do đó nếu chọn $t$ đủ lớn hay càng nhiều ngoặc thì các ước nguyên tố $\neq 3$ và đôi một khác nhau càng tăng (vì mỗi cặp hai ngoặc bất kì chỉ có ước chung là $1,3$) và ngoài ra mỗi ngoặc $(...)$ có dạng $a^2-a+1=a(a-1)+1$ là số lẻ do đó nó có ít nhất một ước lẻ nguyên tố, như vậy chọn $t$ càng lớn thì số ước nguyên tố càng lớn và đôi một khác nhau, suy ra mệnh được chứng minh, do vậy bài toán có câu trả lời khẳng định, ta chọn $t$ càng lớn khi đó nó sẽ có nhiều hơn hoặc bằng $1999$ ước nguyên tố và chọn như trên thì ta chọn được $n$ thỏa đề bài
Vậy tồn tại $\boxed{n=3^x.p_1.p_2...p_{1999}}$ với $p_i\neq 3$ và $p_i|2^{3^x}+1$

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 17-08-2012 - 13:23

[The Gunner]

Bài toán tổng quát: Tồn tại $n_k \in \mathbb{N}^*$ $n$ có đúng $k$ ước nguyên tố thỏa mãn $n_k|2^n_k+1$
Ta thấy $n_k$ lẻ nên suy ra $3|n_k$
Với $k=1,n_1=3$ ta có đpcm
Giả sử đúng đến $k$ ta chứng minh đúng đến $k+1$. Thật vậy, giả sử $n_k=3^am$ với $m$ ko chia hết cho 3
ta có $2^{3n_k}+1=(2^n_k+1)(2^{2n_k}-2^n_k+1)$ dễ thấy $2^{2n_k}-2^n_k+1 \vdots 3$ nên kết hợp với giả thuyết quy nạp suy ra $3n_k|2^{3n_k}+1$ do đó ta cần tìm $p$ nguyên tố thỏa mãn $n_{k+1}=3pn_k$ với $n_k \not \vdots p$ suy ra $2^n_k+1 \not \vdots p$
Đặt $2^n_k=b$ ta có $p|b^3+1=(b+1)(b^2-b+1)$ Ta có $gcd(b+1,b^2-b+1)=gcd(b+1,3)=3$ vì $b+1 \vdots 3$
ta có $b=3h-1$ suy ra $b^2-b+1=9h^2-9h+3$ chia hết cho 3 nhưng ko chia hết cho $3^2$. Nên ta chỉ cần một ước nguyên tố $p$ của $\frac{b^2-b+1}{3}$
Khi đó $n_{k+1}=3pn_k|2^{3n_k}+1|2^{n_k+1}+1$ và $n_{k+1}$ có đúng $k+1$ ước nguyên tố