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

[hovutenha]

Cho $n$ là số nguyên dương. Chứng minh rằng

$$\sum_{n\vdots d,d=2k+1}\varphi (d)2^{\frac{n}{d}} \hspace{0.2cm} \vdots \hspace{0.2cm} n$$

Với $\varphi (x)$ là số các số nguyên dương nhỏ hơn hoặc bằng $x$ và nguyên tố cùng nhau với $x$.

[nhungvienkimcuong]

Cho $n$ là số nguyên dương. Chứng minh rằng

$$\sum_{n\vdots d,d=2k+1}\varphi (d)2^{\frac{n}{d}} \hspace{0.2cm} \vdots \hspace{0.2cm} n$$

Với $\varphi (x)$ là số các số nguyên dương nhỏ hơn hoặc bằng $x$ và nguyên tố cùng nhau với $x$.

Ta sẽ đếm số tập hợp $A$ là tập hợp con của $\{1,2,\dots,n\}$ sao cho tổng các phần tử của $A$ là bội của $n$.

 

Đặt $\epsilon=e^{2i\pi/n}$ là căn nguyên thủy bậc $n$ của đơn vị, khi đó ta có tính chất

\[\sum_{k=1}^{n}\epsilon^{km}=n\big[m\equiv 0\pmod{n}\big],\]

với $[P]$ là kí hiệu Iverson. Từ kết quả này suy ra ngay số tập hợp cần tính chính là

\[\mathcal{K}=\sum_{A\subset\{1,\dots,n\}}\frac{\sum_{k=1}^{n}\epsilon^{k\cdot s(A)}}{n}=\frac{1}{n}\sum_{A\subset\{1,\dots,n\}}\sum_{k=1}^{n}\epsilon^{k\cdot s(A)},\]

trong đó $s(A)$ tổng các phần tử của $A$. Tiếp theo biến đổi

\[\sum_{A\subset\{1,\dots,n\}}\sum_{k=1}^{n}\epsilon^{k\cdot s(A)}=\sum_{k=1}^{n}\sum_{A\subset\{1,\dots,n\}}\prod_{a\in A}\epsilon^{ka}=\sum_{k=1}^{n}\prod_{a=1}^n(1+\epsilon^{ka}).\]

Chú ý rằng với $d=\frac{n}{\text{UCLN}(k,n)}$ thì $\epsilon^k$ là căn nguyên thủy bậc $d$ của đơn vị, dẫn đến

\[x^d-1=(x-\epsilon^{k})(x-\epsilon^{2k})\dots(x-\epsilon^{dk})\implies (1+\epsilon^k)(1+\epsilon^{2k})\dots(1+\epsilon^{dk})=2\big[d\equiv 1\pmod{2}\big].\] 

Suy ra $\prod_{a=1}^n(1+\epsilon^{ka})=2^{n/d}\big[d\equiv 1\pmod{2}\big].$

Như vậy $\prod_{a=1}^n(1+\epsilon^{ka})=2^{\text{UCLN}(k,n)}\left[\frac{n}{\text{UCLN}(k,n)}\equiv 1\pmod{2}\right]$ nên ta có 

\[\mathcal{K}=\frac{1}{n}\sum_{k=1}^n2^{\text{UCLN}(k,n)}\left[\frac{n}{\text{UCLN}(k,n)}\equiv 1\pmod{2}\right].\]

Phần còn lại chỉ cần chứng minh đẳng thức (của bạn đọc)

\[\sum_{k=1}^n2^{\text{UCLN}(k,n)}\left[\frac{n}{\text{UCLN}(k,n)}\equiv 1\pmod{2}\right]=\sum_{d\mid n}\varphi (d)2^{\frac{n}{d}}\big[d\equiv 1\pmod{2}\big].\]

 

 

Ghi chú. Đẳng thức này khá liên quan với đếm Necklace (lời giải sơ cấp đã có ở diễn đàn).