Sums + number theory

Relevant wiki: Lowest Common Divisor - Problem Solving

There is a formula for this sum, $\frac{n}{2}\left(1+\Sigma_{d|n}d\times\phi(d)\right)$ , which we can use for $n=77$ : We find $\frac{77}{2}(1+1*1+7*6+11*10+77*60)=\boxed{183799}$ .

Let me outline a proof of the formula $\frac{n}{2}\left(1+\Sigma_{d|n}d\times\phi(d)\right)$ . The sum we seek is $n\Sigma_{k=1}^{n}\frac{k}{\gcd(k,n)}.$ Now add up the terms such that $\gcd(k,n)$ is a given divisor $d$ of $n$ . There are $\phi(n/d)$ such terms and the average value of $k$ is $\frac{n}{2}$ by symmetry (except when $d=n)$ . Thus the sum is $\frac{n}{2}\left(1+\sum_{d|n}\frac{n}{d}\phi(n/d)\right)$ , where the added 1 accounts for the special case $d=n$ . We obtain our formula by substituting $d$ for $\frac{n}{d}$ .

Solution: $\ A = lcm[7,77] +lcm[14,77]+...+lcm[70,77] = 77(1+2+...+10] = 77 \times\ 55 = 4235$ $\ B = lcm[11,77] +lcm[22,77]+...+lcm[66,77] = 77(1+2+...+6) = 77 \times\ 21 = 1617$ Now let x be a positive integer such that: $\ gcd(x,77) = 1$ then $\ C = \sum_{}^{} lcm[x,77] = 77(( \displaystyle\sum_{k=1}^{k=76} k )-7(1+2+...+10) - 11(1+2+...+6) ) = 77(2926 -231-385)$ $\ = 77 \times\ 2310 = 177870$ $\therefore\displaystyle\sum_{k=1}^{k=77} lcm[k,77] = A+B+C+lcm[77,77] = 4235 +1617 +177870 +77 = \boxed{183 799}$

I don't know how I did it but I got it right