$F(n)=\sum_{i=1}^{n}\sum_{d|i}\mathrm{gcd}(d,\frac{i}{d})$
令
\[
F(n)=\sum_{i=1}^{n}\sum_{d|i}\mathrm{gcd}(d,\frac{i}{d})
\]
若记
\[
f(i)=\sum_{d|i}\mathrm{gcd}(d,\frac{i}{d}),
\]
则 $F(n)=\sum_{i=1}^{n}f(i)$. 证明
\[
f(p_{i_1}^{s_1}p_{i_2}^{s_2}\cdots p_{i_k}^{s_k})=f(p_{i_1}^{s_1})\cdot f(p_{i_2}^{s_2})\cdots f(p_{i_k}^{s_k}).
\]
用例子进行分析:
显然, $f(1)=1$, 且对于素数 $p$, $f(p)=2$.
\[
f(2^n)=\begin{cases}
2(1+2^1+2^2+\cdots+2^{[\frac{n-1}{2}]}), & \text{当}\ n\ \text{是奇数},\\
2(1+2^1+2^2+\cdots+2^{[\frac{n-1}{2}]})+2^{\frac{n}{2}}, & \text{当}\ n\ \text{是偶数}.\\
\end{cases}
\]
对于一般的素数 $p$
\[
f(p^n)=\begin{cases}
2(1+p^1+p^2+\cdots+p^{[\frac{n-1}{2}]}), & \text{当}\ n\ \text{是奇数},\\
2(1+p^1+p^2+\cdots+p^{[\frac{n-1}{2}]})+p^{\frac{n}{2}}, & \text{当}\ n\ \text{是偶数}.\\
\end{cases}
\]
对于任两个素数 $p,q$, 有
\[
f(pq)=2+\mathrm{gcd}(p,\frac{pq}{p})+\mathrm{gcd}(q,\frac{pq}{q})=4.
\]
对于三个素数 $p,q,r$, 有
\[
\begin{split}
f(pqr)&=2+\mathrm{gcd}(p,\frac{pqr}{p})+\mathrm{gcd}(q,\frac{pqr}{q})+\mathrm{gcd}(q,\frac{pqr}{r})\\
&\quad+\mathrm{gcd}(pq,\frac{pqr}{pq})+\mathrm{gcd}(pr,\frac{pqr}{pr})+\mathrm{gcd}(qr,\frac{pqr}{qr})\\
&=8.
\end{split}
\]
因此, 不难证明
\[
f(p_{i_1}p_{i_2}\cdots p_{i_k})=C_k^0+C_k^1+C_k^2+\cdots+C_k^k=2^k.
\]
设 $n=p^2 q^3$,
\[
\begin{split}
f(p^2 q^3)&=\mathrm{gcd}(1,p^2 q^3)+\mathrm{gcd}(q,p^2 q^2)+\mathrm{gcd}(q^2,p^2 q)+\mathrm{gcd}(q^3,p^2)\\
&\quad+\mathrm{gcd}(p,p q^3)+\mathrm{gcd}(pq,p q^2)+\mathrm{gcd}(pq^2,pq)+\mathrm{gcd}(pq^3,p)\\
&\quad+\mathrm{gcd}(p^2,q^3)+\mathrm{gcd}(p^2 q,q^2)+\mathrm{gcd}(p^2 q^2,q)+\mathrm{gcd}(p^2 q^3,1)\\
&=4+2p+4q+2pq\\
&=(2+p)(2+2q).
\end{split}
\]
注意到, 应用上面的公式, 有 $f(p^2)=2+p$, $f(q^3)=2(1+q)$. 因此我们有
\[
f(p^2 q^3)=f(p^2)f(q^3).
\]
于是我们就猜测
\[
f(p_{i_1}^{s_1}p_{i_2}^{s_2}\cdots p_{i_k}^{s_k})=f(p_{i_1}^{s_1})\cdot f(p_{i_2}^{s_2})\cdots f(p_{i_k}^{s_k}).
\]
这个证明实际上就隐藏在上面计算 $f(p^2 q^3)$ 的过程中, 你会发现
\[
\begin{matrix}
1 & q & q & 1\\
p & pq & pq & p\\
1 & q & q & 1\\
\end{matrix}
\]
关于中间竖直直线(未画出)的对称性, 这是由 $q$ 的指数是奇数带来的. 然后其他的行只不过是考虑到了 $p$.