Sum of all

We can summarize Mayank's approach in the formula $n\sum_{d|n}\frac{\phi(d)}{d}=2015\left(1+\frac{4}{5}+\frac{12}{13}+\frac{30}{31}+\frac{48}{65}+\frac{120}{155}+\frac{360}{403}+\frac{1440}{2015}\right)$ $=\boxed{13725}$

I have solved this question with the help of Euler's function. Short methods and advises are always welcome. $First\quad of\quad all,\quad note\quad that\quad 2015=13*31*5.\\ All\quad possible\quad factors\quad of\quad 2015\quad are\quad 1,5,13,31,65,155,403\quad and\quad 2015.\\ Therefore\quad all\quad possible\quad GCDs\quad are\quad 1,5,13,31,65,155,403\quad and\quad 2015.\\ The\quad process\quad is\quad explained\quad by\quad the\quad following\quad two\quad factors\quad of\quad 2015\\ and\quad then\quad it\quad is\quad applied\quad to\quad rest\quad factors:\\ \rightarrow \quad GCD\quad =\quad 1\\ \phi (2015)=1440\\ \rightarrow \quad GCD\quad =\quad 5\\ We\quad have\quad to\quad find\quad out\quad all\quad 5*x\quad such\quad that\quad x\quad is\quad relatively\quad \\ prime\quad to\quad 2015\\ since\quad 5*403=2015,\quad \phi (403)\quad is\quad the\quad number\quad of\quad all\quad the\quad \\ numbers\quad x\quad \\ such\quad that:\\ (x,2015)=5.\quad So,\quad sum\quad of\quad all\quad GCD\quad 5s\quad is\quad \phi (403)*5\\ \\ Note\quad that\quad \phi (1)+\phi (5)+\phi (13)+\phi (31)+\phi (65)+\phi (155)\\ +\phi (403)+\phi (2015)=\quad 2015\\ \\ As\quad the\quad process\quad could\quad be\quad understood,\\ \sum _{ x=1 }^{ 2015 }{ (x,2015) } =2015*\phi (1)+403*\phi (5)+155*\phi (13)+\\ 65*\phi (31)+31*\phi (65)+13*\phi (155)+5*\phi (403)+\phi (2015)\\ \\ \sum _{ x=1 }^{ 2015 }{ (x,2015) } =13725$ Suggestions are always WELCOME

Not a proof but just an observation of the general form.

Let $f(n) = \sum _{x=1}^{n}\text{gcd} \left(x,n\right)$

And $g(a,b) = a^{b-1}(b(a-1) + a)$

Then, if $n = p_1^{a_1}p_2^{a_2}...$ ,

$f(n) = g(p_1,a_1)*g(p_2,a_2)*...$

In this problem, $2015 = 5*13*31$ .

And $f(n) = g(5,1) * g(13,1) * g(31,1) = 9 * 25 * 61 = \boxed{13725}$

My Java code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int x,s=0;
for(x=1;x<=2015;x++)
{
    int m=gcd(x,2015);
    s=s+m;
}
        System.out.println(""+s); 

/** The method called upon :

    public int gcd(int a,int b){

int c,gcd;

while(b!=0)
{
    c=b;
    b=a%c;
    a=c;

}
     return a;
    }

a=13725

We want Sum over d|2015 of d phi ( 2015/d) = (5+(5-1))x(13+(13-1))x(31+(31-1)) which can be shown using product expansion and the definition of phi. This product is 9x25x61=13725

For pairwise coprime a, b, and c, $\sum_{x=1}^{abc}gcd(x,abc)=8abc-4(ab+ac+bc)+2(a+b+c)-1$ Plugging in $a=5, b=13, c=31,$ we get $\boxed{13725}$