Large sum of 1/GCD's

Question

The problem is related to cryptography, it involves finding the sum of inverse of $GCD$...

Say I have an integer $N \leq10^7$, Find sum of all $N/GCD(K,N)...$upto $N$ where $1\leq K\leq N$

Please help

Answer 1

We have the following closed form for your sum. It requires knowing the prime factorisation of $n$, so it may not be useful for large $n$:

If $n=\prod_rp_r^{k_r}$, then $$\sum_{k\leq n}\frac n{\gcd(n,k)}=\prod_r\frac{p_r^{2k_r+1}+1}{p_r+1}.$$

Proof. Each summand $\frac nd$ occurs as many times as there are $k\leq n$ s.t. $\gcd(k,n)=d$, that is, $\phi(\frac nd)$ times. So by rearranging we have

$$\sum_{k\leq n}\frac n{\gcd(n,k)}=\sum_{d\mid n}\frac nd\phi(\frac nd)=\sum_{d\mid n}d\phi(d).$$

We can apply some properties of Dirichlet convolution to write this in terms of the prime factorisation of $n$: for $n=p^k$ a prime power, we have $$\sum_{d\mid p^k}d\phi(d)=1+\sum_{m=1}^kp^m\cdot p^{m-1}(p-1)=\frac{p^{2k+1}+1}{p+1}.$$

So for general $n=\prod_r p_r^{k_r}$: $$\sum_{d\mid n}d\phi(d)=\prod_r\frac{p_r^{2k_r+1}+1}{p_r+1}.\qquad\square$$