Question Number 211415 by AlagaIbile last updated on 08/Sep/24
Commented by loredcs2357 last updated on 11/Oct/24
![Let S(n)=Σ_(k≤n) lcm(k,n). It′s easy to see that S(n)=(n/2)[Σ_(d∣n) ϕ(d^2 )+1]. Moreover we have: f(n)=Σ_(d∣n) ϕ(d^2 )=Π_(p∣n) ((p^(2α_p +1) +1)/(p+1)) where α_p is the highest power of p in n. If n=1080 we have: f(1080)=f(2^3 ∙3^3 ∙5)=((2^7 +1)/3)∙((3^7 +1)/4)∙((5^3 +1)/6)=493491 S(1080)=((1080∙493492)/2)=266728680](https://www.tinkutara.com/question/Q212357.png)
$$\mathrm{Let}\:{S}\left({n}\right)=\underset{{k}\leqslant{n}} {\sum}\mathrm{lcm}\left({k},{n}\right). \\ $$$$\mathrm{It}'\mathrm{s}\:\mathrm{easy}\:\mathrm{to}\:\mathrm{see}\:\mathrm{that}\:{S}\left({n}\right)=\frac{{n}}{\mathrm{2}}\left[\underset{{d}\mid{n}} {\sum}\varphi\left({d}^{\mathrm{2}} \right)+\mathrm{1}\right].\:\mathrm{Moreover}\:\mathrm{we}\:\mathrm{have}: \\ $$$${f}\left({n}\right)=\underset{{d}\mid{n}} {\sum}\varphi\left({d}^{\mathrm{2}} \right)=\underset{{p}\mid{n}} {\prod}\:\frac{{p}^{\mathrm{2}\alpha_{{p}} +\mathrm{1}} +\mathrm{1}}{{p}+\mathrm{1}} \\ $$$$ \\ $$$$\mathrm{where}\:\alpha_{{p}} \:\mathrm{is}\:\mathrm{the}\:\mathrm{highest}\:\mathrm{power}\:\mathrm{of}\:{p}\:\mathrm{in}\:{n}.\:\mathrm{If}\:{n}=\mathrm{1080}\:\mathrm{we}\:\mathrm{have}: \\ $$$$ \\ $$$${f}\left(\mathrm{1080}\right)={f}\left(\mathrm{2}^{\mathrm{3}} \centerdot\mathrm{3}^{\mathrm{3}} \centerdot\mathrm{5}\right)=\frac{\mathrm{2}^{\mathrm{7}} +\mathrm{1}}{\mathrm{3}}\centerdot\frac{\mathrm{3}^{\mathrm{7}} +\mathrm{1}}{\mathrm{4}}\centerdot\frac{\mathrm{5}^{\mathrm{3}} +\mathrm{1}}{\mathrm{6}}=\mathrm{493491} \\ $$$${S}\left(\mathrm{1080}\right)=\frac{\mathrm{1080}\centerdot\mathrm{493492}}{\mathrm{2}}=\mathrm{266728680} \\ $$