I didn't know there was a formula

We know that if $d \mid k$ and $\gcd\left(q,\dfrac{k}{d}\right)=1$ where $1 \leq q \leq \dfrac{k}{d}$ , then $\gcd(dq,k)=d$ . From the restriction we clearly see that $1 \leq dq \leq k$ .

For example, if $k=30$ and $d=3$ , all the possible values for $q$ are $1,3,7,9$ , so $\gcd(3,30)=\gcd(9,30)=\gcd(21,30)=\gcd(27,30)=3$ . What does it tell us? That there will be exactly four values of $i$ for which $\gcd(i,30)=3$ and $1 \leq i \leq 30$ .

Note that we need $q$ to be coprime with $\dfrac{k}{d}$ , and since $q \leq \dfrac{k}{d}$ , the number of values of $q$ will be $\varphi\left(\dfrac{k}{d}\right)$ . So, there will be exactly $\varphi\left(\dfrac{k}{d}\right)$ values of $i$ for which $\gcd(i,k)=d$ and $1 \leq i \leq k$ .

And since $\gcd(i,k)$ is always a divisor of $k$ , the sum we want is $\displaystyle f(k)=\sum_{d \mid k} \varphi\left(\dfrac{k}{d}\right) d$ , i.e., we run over all positive divisors $d$ of $k$ to find how many times $d$ will be the result of $\gcd(i,k)$ ; and we sum this for all $d$ .

So, $f(k)=\varphi * I$ . Since $I$ and $\varphi$ are multiplicative functions, $f(k)$ is also multiplicative. That means that we only need to find what is $f$ evaluated at some prime power, i.e., $f(p^a)$ . We have: $\begin{aligned} f(p^a) &= \sum_{d \mid p^a} \varphi(d) \dfrac{p^a}{d}\\ &= \sum_{j=0}^{a} \varphi(p^j) \dfrac{p^a}{p^j}\\ &= p^a \sum_{j=0}^{a} \dfrac{\varphi(p^j)}{p^j}\\ &= p^a \left(1+\sum_{j=1}^{a} \dfrac{\varphi(p^j)}{p^j}\right)\\ &= p^a \left(1+\sum_{j=1}^{a} \left(1-\dfrac{1}{p}\right)\right)\\ &= p^a \left(1+a\left(1-\dfrac{1}{p}\right)\right)\\ &= p^{a-1} \left(p+a(p-1)\right)\\ &= p^{a-1} \left(1+p-1+a(p-1)\right)\\ &= p^{a-1} \left(1+(a+1)(p-1)\right) \end{aligned}$ Finally, $\displaystyle f(k)=f\left(\prod_{i=1}^{n} {p_i}^{a_i}\right)=\prod_{i=1}^{n} f({p_i}^{a_i})=\boxed{\prod_{i=1}^{n} {p_i}^{a_i-1} \left(1+(a_i+1)(p_i-1)\right)}$ .

Let $f(k) = \displaystyle \sum_{i=1}^k \gcd(i,k)$ for any $k$ positive integer.

We are going to prove the two statements below, from which the answer clearly follows:

Claim 1.: If $p$ is a positive prime and $a$ is an arbitrary positive integer, $f(p^a) = p^{a-1}(1+(a+1)(p-1))$ .

Claim 2.: $f(k)$ is a multiplicative arithmetic function, which means that if $\gcd(a,b) = 1$ for $a, b$ positive integers, then $f(ab) = f(a)f(b)$ .

Proof of Claim 1.:

We are using induction on $a$ . The base case $a=1$ is clear, since $f(p) = (\displaystyle \sum_{i=1}^{p-1} \gcd(i,p)) + \gcd(p,p) = p-1 + p = 2p-1$ and $p^{a-1}(1+(a+1)(p-1)) = 2p-1$ .

Assume that the claim is proven for $a-1$ . In order to verify it for $a$ , recall the following well known facts:

1. $\gcd(a+kb,b) = \gcd(a,b)$ for any $a$ , $b$ $,k$ integers.

2. If $0<i<p^a$ , $\gcd(i,p^a) = \gcd(i,p^{a-1})$ for a $p$ prime and an $a$ positive integer.

Using this we can now establish the induction step for $a$ :

$f(p^a) = \displaystyle \sum_{i=1}^{p^a} \gcd(i,p^a) = \displaystyle \sum_{i=1}^{p^{a-1}-1} \gcd(i,p^a) + \gcd(p^{a-1}, p^a) + \displaystyle \sum_{i=1}^{p^{a-1}-1} \gcd(i+p^{a-1},p^a) + \gcd(2p^{a-1}, p^a) + \ldots + \displaystyle \sum_{i=1}^{p^{a-1}-1} \gcd(i+(p-1)p^{a-1},p^a) + \gcd(p^a, p^a) = \displaystyle \sum_{i=1}^{p^{a-1}-1} (\displaystyle \sum_{j=0}^{p-1} \gcd(i+jp^{a-1},p^a)) + \displaystyle \sum_{l=1}^{p} \gcd(lp^{a-1},p^a) = \displaystyle \sum_{i=1}^{p^{a-1}-1} (\displaystyle \sum_{j=0}^{p-1} \gcd(i+jp^{a-1},p^{a-1})) + (p-1)p^{a-1}+p^a = \displaystyle \sum_{i=1}^{p^{a-1}-1} (\displaystyle \sum_{j=0}^{p-1} \gcd(i,p^{a-1})) + (2p-1)p^{a-1} = \displaystyle \sum_{i=1}^{p^{a-1}-1} p \cdot \gcd(i,p^{a-1}) + (2p-1)p^{a-1} = p \cdot (f(p^{a-1}) - p^{a-1}) + (2p-1)p^{a-1} = p^{a-1}(1+a(p-1)) - p^a + (2p-1)p^{a-1} = p^{a-1}(1+ap-a-p+2p-1) = p^{a-1}(1+(a+1)(p-1))$ ,

so our induction is complete.

Proof of Claim 2.:

The greatest common divisor function is known to be multiplicative, so for every $a$ , $b$ , $i$ integers we have $\gcd(i,ab) = (\gcd(i,a))(\gcd(i,b))$ .

Furthermore, according to the Chinese Remainder theorem for every $0 \leq i \leq a-1$ and $0 \leq j \leq b-1$ pair of integers there is exactly one number $u(i,j)$ in the interval $(1,ab)$ which has a remainder of $i$ and $j$ when divided by $a$ and $b$ respectively.

Using the former observations we obtain the following:

$f(ab) = \displaystyle \sum_{i=1}^{ab} \gcd(i,ab) = \displaystyle \sum_{i=0}^{a-1} \displaystyle \sum_{j=0}^{b-1} \gcd(u(i,j),ab) = \displaystyle \sum_{i=0}^{a-1} \displaystyle \sum_{j=0}^{b-1} (\gcd(u(i,j),a))(\gcd(u(i,j),b)) = \displaystyle \sum_{i=0}^{a-1} \displaystyle \sum_{j=0}^{b-1} (\gcd(i,a))(\gcd(j,b)) = \displaystyle \sum_{i=1}^{a} \displaystyle \sum_{j=1}^{b} (\gcd(i,a))(\gcd(j,b)) = (\displaystyle \sum_{i=1}^{a} \gcd(i,a))(\displaystyle \sum_{j=1}^{b} \gcd(j,b)) = f(a)f(b)$

Q.E.D.