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

[Secrets In Inequalities VP]

Cho $n$ là số tự nhiên lớn hơn 1 . Chứng minh rằng : $\sum _{0\leq k\leq n;(k,n)=1}k= \frac{1}{2}n\phi (n)$

Bài viết đã được chỉnh sửa nội dung bởi Secrets In Inequalities VP: 04-11-2012 - 22:11

[nguyenta98]

Cho $n$ là số tự nhiên lớn hơn 1 . Chứng minh rằng : $\sum _{0\leq k\leq n;(k,n)=1}k= \frac{1}{2}n\phi (n)$

Một bài toán mẫu mực kết hợp tổ hợp - số học
Giải như sau:
Ta có $|A_1\cup A_2\cup A_3\cup...\cup A_k|=|A_1|+|A_2|+...+|A_k|-|A_1\cap A_2|-...-|A_k\cap A_1|+|A_1\cap A_2\cap A_3|+...+|A_k\cap A_1\cap A_2|-...\pm |A_1\cap A_2\cap ...\cap A_k|$ với dấu $+$ và $-$ đan dấu
Trở lại bài toán của ta, gọi $p_1,p_2,...,p_t$ là tất cả các ước nguyên tố của $n$, ta sẽ tính tổng các số hạng mà không nguyên tố cùng nhau với $n$ hay gọi $x$ là một số $1\le x\le n$ mà $gcd(x,n)\neq 1$ khi ấy $x,n$ sẽ phải cùng chia hết cho ít nhất một ước nguyên tố thuộc $p_1,p_2,..,p_t$ và gọi $n=p_1^{a_1}.p_2^{a_2}...p_t^{a_t}$
Ta chỉ xét $t$ chẵn, $t$ lẻ tương tự
Như theo công thức ở trên số số mà $\le n$ và không nguyên tố cùng nhau với $n$ là
$\left(\dfrac{n}{p_1}+\dfrac{n}{p_2}+...+\dfrac{n}{p_t}\right)-\left(\dfrac{n}{p_1p_2}+...+\dfrac{n}{p_tp_1}\right)+\left(\dfrac{n}{p_1p_2p_3}+...+\dfrac{n}{p_tp_1p_2}\right)-...-\left(\dfrac{n}{p_1p_2...p_t}\right)$ (với $t$ lẻ thì đoạn $-\left(\dfrac{n}{p_1p_2...p_t}\right)$ sẽ thành $+\left(\dfrac{n}{p_1p_2...p_t}\right)$) và vẫn cm tương tự)
Giờ ta tính tổng từng cặp, thấy gọi $f(a)$ là tổng các phần tử của tập có $a$ phần tử suy ra $f\left(\dfrac{n}{p_{k_1}.p_{k_2}...p_{k_r}}\right)$ với $k_i \in (1,2,3,...,t)$ và $r\le t$ sẽ là $(p_{k_1}.p_{k_2}...p_{k_r})+(p_{k_1}.p_{k_2}...p_{k_r}).2+...+n=\dfrac{n+p_{k_1}.p_{k_2}...p_{k_r}}{2}.\dfrac{n}{p_{k_1}.p_{k_2}...p_{k_r}}$
Như vậy $\left(\dfrac{n}{p_1}+\dfrac{n}{p_2}+...+\dfrac{n}{p_t}\right)-\left(\dfrac{n}{p_1p_2}+...+\dfrac{n}{p_tp_1}\right)+\left(\dfrac{n}{p_1p_2p_3}+...+\dfrac{n}{p_tp_1p_2}\right)-...-\left(\dfrac{n}{p_1p_2...p_t}\right)=\dfrac{n}{2}\left(\left(\dfrac{n+p_1}{p_1}+\dfrac{n+p_2}{p_2}+...+\dfrac{n+p_t}{p_t}\right)-\left(\dfrac{n+p_1p_2}{p_1p_2}+...+\dfrac{n+p_tp_1}{p_tp_1}\right)+\left(\dfrac{n+p_1p_2p_3}{p_1p_2p_3}+...+\dfrac{n+p_tp_1p_2}{p_tp_1p_2}\right)-...-\left(\dfrac{n+p_1p_2...p_t}{p_1p_2...p_t}\right)\right)=\dfrac{n}{2}.p_1^{a_1-1}....p_t^{a_t-1}\left(p_2.p_3...p_t+...+p_1p_2...p_{t-1}-p_3p_4...p_t-...p_2p_3...p_{t-1}+...-1\right).\dfrac{n}{2}\left(C_t^1-C_t^2-...-C_t^{t-2}+C_t^{t-1}-1\right)$ (do mỗi phần tử của từng cụm $()$ là $C_t^i$ theo công thức tổ hợp)
Thấy $C_t^1-C_t^2-...-C_t^{t-2}+C_t^{t-1}-1=-(1-1)^t+1=1$
Do đó tổng các số mà không nguyên tố cùng nhau với $n$ là
$M=\dfrac{n}{2}.p_1^{a_1-1}....p_t^{a_t-1}\left(p_2.p_3...p_t+...+p_1p_2...p_{t-1}-p_3p_4...p_t-...p_2p_3...p_{t-1}+...+p_1+p_2+...+p_t-1\right)+\dfrac{n}{2}$
Đặt $\left(p_2.p_3...p_t+...+p_1p_2...p_{t-1}-p_3p_4...p_t-...p_2p_3...p_{t-1}+...+p_1+p_2+...+p_t-1\right)=C$
Như vậy $\sum _{0\leq k\leq n;(k,n)=1}k=(1+2+3+...+n)-M$
$=\dfrac{n(n+1)}{2}-\dfrac{n}{2}.p_1^{a_1-1}....p_t^{a_t-1}C-\dfrac{n}{2}$
$=\dfrac{n}{2}\left(n+1-p_1^{a_1-1}....p_t^{a_t-1}C-1\right)$
$=\dfrac{n}{2}\left(n-p_1^{a_1-1}....p_t^{a_t-1}C\right)$
Thay $n=p_1^{a_1}...p_t^{a_t}$ và đặt thừa số chung $p_1^{a_1-1}...p_t^{a_t-1}$
Khi ấy
$=\dfrac{n}{2}.p_1^{a_1-1}...p_t^{a_t-1}.\left(p_1p_2...p_t-C\right)$
Theo khai triển $(p_1-1)(p_2-1)...(p_t-1)$ đúng bằng $\left(p_1p_2...p_t-\left(p_2.p_3...p_t+...+p_1p_2...p_{t-1}-p_3p_4...p_t-...p_2p_3...p_{t-1}+...+p_1+p_2+...+p_t-1\right)\right)=p_1p_2...p_t-C$
Do đó $=\dfrac{n}{2}.p_1^{a_1-1}...p_t^{a_t-1}.(p_1-1)(p_2-1)...(p_t-1)=n.\dfrac{1}{2}.\phi(n)$ đây chính là $đpcm$ hoàn toàn tương tự với $t$ lẻ ta cũng thu kết quả như trên

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 07-11-2012 - 19:34

[Secrets In Inequalities VP]

Cho $n$ là số tự nhiên lớn hơn 1 . Chứng minh rằng : $\sum _{0\leq k\leq n;(k,n)=1}k= \frac{1}{2}n\phi (n)$

Bài này chỉ cần một nhận xét nhỏ là solved problem :
Dễ thấy nếu $gcd(k,n)= 1$ thì $gcd(n,n-k)= 1$
$\Rightarrow \sum _{0\leq k\leq n;(k,n)=1}k= \sum _{0\leq k\leq n;(k,n)=1}(n-k)$$\Rightarrow \sum _{0\leq k\leq n;(k,n)=1}k= \frac{1}{2}( \sum _{0\leq k\leq n;(k,n)=1}k+ \sum _{0\leq k\leq n;(k,n)=1}(n-k))= \frac{1}{2}\phi (n)n$
( vì số các số k mà $gcd(k,n)=1$ bằng $\phi (n)$ )

Bài viết đã được chỉnh sửa nội dung bởi Secrets In Inequalities VP: 15-11-2012 - 22:28

[nguyenta98]

Bài này chỉ cần một nhận xét nhỏ là solved problem :
Dễ thấy nếu $gcd(k,n)= 1$ thì $gcd(n,n-k)= 1$
$\Rightarrow \sum _{0\leq k\leq n;(k,n)=1}k= \sum _{0\leq k\leq n;(k,n)=1}(n-k)$$\Rightarrow \sum _{0\leq k\leq n;(k,n)=1}k= \frac{1}{2}( \sum _{0\leq k\leq n;(k,n)=1}k+ \sum _{0\leq k\leq n;(k,n)=1}(n-k))= \frac{1}{2}\phi (n)n$
( vì số các số k mà $gcd(k,n)=1$ bằng $\phi (n)$ )

Hì hì, cách của em dùng tổ hợp số học, cách của anh cũng vậy thôi, kiểu của anh là lấy phần bù rồi cộng phần còn lại ra $n$ cách giải rất hay , càng ngày thấy thầy Khánh ĐHSP nói đúng, học sinh Vĩnh Phúc và Phú Thọ giỏi số học