(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.$$
$\gcd (n,1)+ \gcd (n,2)+ \cdots + \gcd (n,n) = 3n-3.$
#1
Đã gửi 08-02-2016 - 03:20
- Chris yang, I Love MC, O0NgocDuy0O và 4 người khác yêu thích
Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.
Grothendieck, Récoltes et Semailles (“Crops and Seeds”).
#2
Đã gửi 27-02-2016 - 19:57
(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
- Zaraki, lahantaithe99, nhungvienkimcuong và 2 người khác yêu thích
__________
Bruno Mars
#3
Đã gửi 27-02-2016 - 20:21
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 yêu thích
#4
Đã gửi 27-02-2016 - 21:28
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
__________
Bruno Mars
#5
Đã gửi 27-02-2016 - 23:24
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
#6
Đã gửi 28-02-2016 - 02:43
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
Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.
Grothendieck, Récoltes et Semailles (“Crops and Seeds”).
Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: number theory, số học, gcd
|
Toán Trung học Cơ sở →
Số học →
Chứng minh rằng $(a_{1}^{2}+1)(a_{2}^{2}+1)...(a_{2024}^{2}+1)$ không chia hết cho $(a_{1}.a_{2}...a_{2024})^2$Bắt đầu bởi Nguyentrongkhoi, 26-03-2024 số học |
|
||
Toán thi Học sinh giỏi và Olympic →
Số học →
Chứng minh rằng $x^2 + y^2 + z^2 - 2(xy + yz + zx)$ là số chính phươngBắt đầu bởi Chuongn1312, 13-03-2024 toán olympic, số học |
|
|||
Toán thi Học sinh giỏi và Olympic →
Số học →
$\sum_{n\vdots d,d=2k+1}\varphi (d)2^{\frac{n}{d}} \hspace{0.2cm} \vdots \hspace{0.2cm} n$Bắt đầu bởi hovutenha, 08-03-2024 tổ hợp, số học |
|
|||
Solved
Toán Trung học Cơ sở →
Đại số →
$f(a)-f(b) \vdots a-b$Bắt đầu bởi Sa is very stupid and lazy, 17-01-2024 số học |
|
|||
Toán thi Học sinh giỏi và Olympic →
Số học →
$x^n+n \vdots p^m$Bắt đầu bởi trinhgiahuy2008, 15-01-2024 số học |
|
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh