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

[Zaraki]

(Bài toán cũ) Tim số nguyên dương $n$ sao cho $$\gcd (n,1)+ \gcd (n,2)+ \cdots + \gcd (n,n) = 3n-3.$$

[Visitor]

(Bài toán cũ) Tim số nguyên dương $n$ sao cho $$\gcd (n,1)+ \gcd (n,2)+ \cdots + \gcd (n,n) = 3n-3.$$

Gọi $d=(k,n)$ thì $(\frac{k}{d},\frac{n}{d})=1$ nên ta có thể viết lại vế trái dưới dạng $\sum_{d|n}d\phi (\frac{n}{d})$

Ta áp dụng công thức siêu kinh điển : Với $f,g$ là hai hàm nhân tính thì $\sum_{d|n}f(d)g(\frac{n}{d})= \prod _{p|n}(\sum_{k=0}^{v_p(n)}f(p^k)g(p^{v_p(n)-k}))$

Ở đây ta chọn $f(x)=x,g(x)=\phi (x)$ thì $\sum_{d|n}d\phi (\frac{n}{d})= \prod _{p|n}(\sum_{k=0}^{v_p(n)}p^k\phi (p^{v_p(n)-k}))=\prod _{p|n}(\sum_{k=0}^{v_p(n)-1}p^k.p^{v_p(n)-k-1}(p-1)+p^{v_p(n)})$

$ = \prod _{p|n}(\sum_{k=0}^{v_p(n)-1}p^{v_p(n)-1}(p-1)+p^{v_p(n)})= \prod _{p|n}(p^{v_p(n)-1}(v_p(n)(p-1)+1))$                                            

Do đó, nếu tồn tại $p|n$ mà $v_p(n)\geq 2$ thì $p^{v_p(n)-1}|3\Rightarrow p=3$ và  $v_3(n)= 2$ 

suy ra mọi ước nguyên tố $p$ khác $3$ thì $v_p(n)=1$

Vậy ra rút gọn được tiếp vế trái bằng $  \prod _{p|n}(p^{v_p(n)-1}(p+1(p-1)))= 3(3+2.2)\prod _{p|n,p\neq 3}p^{v_p(n)-1}(2p-1)=3n-3$

Nếu $n$ lẻ thì vô lí vì vế trái lẻ còn vế phải chẵn, suy ra $n$ chẵn. Lại rút gọn tiếp:

$3n-3= (2.2-1).3.(3+2.2)\prod_{p|n,p\neq 2,3} p^{v_p(n)-1}(2p-1)\vdots 9$ vô lí

$\Rightarrow v_p(n)=1$ với mọi $p|n$

Tóm lại $3n-3=\prod _{p|n}p^{v_p(n)-1}(2p-1)$                                                         $(1)$

 

Giả sử $n=2p_1p_2...p_k$ , $p_i$ lẻ thì từ  $(1)$ suy ra $3(2p_1-1)(2p_2-1)...(2p_k-1)=6p_1p_2...p_k-3$.

Đánh giá bđt đơn giản ta được $k=1$ , dẫn đến $3(2p_1-1)=6p_1-3$

Thỏa mãn với mọi $p$

Vậy $n=2p$

Bài viết đã được chỉnh sửa nội dung bởi Visitor: 27-02-2016 - 21:26

[Ego]

Gọi $d=(k,n)$ thì $(\frac{k}{d},\frac{n}{d})=1$ nên ta có thể viết lại vế trái dưới dạng $\sum_{d|n}d\phi (\frac{n}{d})$

Ta áp dụng công thức siêu kinh điển : Với $f,g$ là hai hàm nhân tính thì $\sum_{d|n}f(d)g(\frac{n}{d})= \prod _{p|n}(\sum_{k=0}^{v_p(n)}f(p^k)g(p^{v_p(n)-k}))$

Ở đây ta chọn $f(x)=x,g(x)=\phi (x)$ thì $\sum_{d|n}d\phi (\frac{n}{d})= \prod _{p|n}(\sum_{k=0}^{v_p(n)}p^k\phi (p^{v_p(n)-k}))= \prod _{p|n}(\sum_{k=0}^{v_p(n)}p^k.p^{v_p(n)-k-1}(p-1))$

$= \prod _{p|n}(\sum_{k=0}^{v_p(n)}p^{v_p(n)-1}(p-1))= \prod _{p|n}((v_p(n)+1)p^{v_p(n)-1}(p-1))=3n-3$                                            $(1)$

Do đó, nếu tồn tại $p|n$ mà $v_p(n)\geq 2$ thì $p^{v_p(n)-1}|3\Rightarrow p=3$ và  $v_3(n)= 2$ , khi đó $(v_3(n)+1)3^{v_3(n)-1}(3-1)=3.3.2$ chia hết cho $9$ nên vô lí

Suy ra $v_p(n)=1$ với mọi $p|n$

Giả sử $n=p_1p_2...p_k$ thì từ  $(1)$ suy ra $2^k(p_1-1)(p_2-1)...(p_k-1)=3p_1p_2...p_k-3$.

Đánh giá bđt đơn giản ta được $k=2$ , dẫn đến $4(p_1-1)(p_2-1)=3p_1p_2-3$

Phương trình cơ bản , kết quả là $p_1=5$, $p_2=13$ và $n=65$

 

p/s: $jinbe$ cho xin cái lời giải cái ._. làm thế này trâu quá ._.

Hình như không đúng. Mình chứng minh được số cần tìm là chẵn và square-free, bị đứng một chỗ. Và bạn thử lại xem. $n = 2p$ luôn thỏa mãn với $p$ là số nguyên tố lẻ :-) ($n = 10, n = 14$ vẫn thỏa mãn)

Bài viết đã được chỉnh sửa nội dung bởi Ego: 27-02-2016 - 20:22

[Visitor]

Hình như không đúng. Mình chứng minh được số cần tìm là chẵn và square-free, bị đứng một chỗ. Và bạn thử lại xem. $n = 2p$ luôn thỏa mãn với $p$ là số nguyên tố lẻ :-) ($n = 10, n = 14$ vẫn thỏa mãn)

thank Ego, nãy mình tính sai tổng xích ma ,đã edit 

Bài viết đã được chỉnh sửa nội dung bởi Visitor: 27-02-2016 - 21:38

[Ego]

To @Visitor: Mình lần đầu đọc qua tính chất này của hàm nhân tính @@. Bạn giới thiệu cho mình vài tài liệu được không?
:-P Cách của mình thủ công hơn nhiều, biện luận và có được $n = 2p_{1}^{\alpha}p_{2}\cdots$ và biện luận trường hợp cho $\alpha = 1$ khá dài dòng 

[Zaraki]

Lời giải của mình chắc dài hơn của Visitor . Mình phát hiện ra một công thức trong lúc giải bài này $$\sum_{i=1}^n \gcd (n,i) = \sum_{i=1}^{\tau (n)} d_i \varphi \left( \frac{n}{d_i} \right)$$ rồi kết hợp với công thức đã biết $$\sum_{i=1}^{\tau (n)} \varphi(d)=n.$$ để đưa bài toán về $$\sum_{i=1}^{\tau (n)} \varphi \left( \frac{n}{d_i} \right) (d_i-3) +3=0.$$

Đến đây là đánh chặn số các ước nguyên tố của $n$.

 

Nói chung là nhìn nó không mạnh bằng việc Visitor trực tiếp phân tích ra $\sum_{i=1}^{\tau (n)} d_i \varphi \left( \frac{n}{d_i} \right)$. 

 

@Ego: Mình đọc tài liệu của hàm nhân tính qua cuốn Number theory: Structures, Examples and Problems của Titu Andreescu và Dorin Andrica.

Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 28-02-2016 - 03:02