More fun in 2015, Part 36

the formula for the sum of all co-primes less then n is $\dfrac{n\phi(n)}{2}$ plug in 2015 to get $\dfrac{2015}{2}*\phi(5*13*31)=\dfrac{2015}{2}*\phi(5)*\phi(13)*\phi(31)=\dfrac{2015}{2}*4*12*30=1450800.$ .

proof: note that if k is co-prime to n, so is n-k. let S denote the sum. the number of terms will be the numbers less then equal n which is coprime to it. this is $\phi(n)$ . then: $S=k_1+k_2+....+k_{\phi(n)-1}+k_{\phi(n)}$ using the fact stated at the beginning of proof: $S=(n-k_{\phi(n)})+(n-k_{\phi(n)-1})+.....(n-k_2)+(n-k_1)$ add these up. note that each k will cancel out, and the number of terms is $\phi(n)$ . so $2S=n\phi(n)\Longrightarrow\boxed{S=\dfrac{n\phi(n)}{2}}$ hence proved.

For all $k$ and $n$ , $\gcd(k, n) = \gcd(n-k, n)$ . You can see this because any number that divides both $k$ and $n$ obviously divides $n-k$ ; conversely any number that divides both $n-k$ and $n$ obviously divides $k$ .

Therefore, the values of $k$ that satisfy the equation exist in pairs adding to 2015. So we now just need to determine the number of these pairs. This is similar to the way in which Carl Friedrich Gauss is reputed to have discovered the formula for triangular numbers during a school exercise.

To determine the number of these pairs, we look to Euler's totient function. $\phi(n)$ is the number of integers $1 \leq k \leq n$ that are coprime with $n$ . It is what is known as a multiplicative function, meaning that $\gcd(m, n) = 1 \Rightarrow \phi(mn) = \phi(m)\phi(n).$ And of course, if $p$ is prime, then $\phi(p) = p - 1$ . From this we deduce $\phi(2015) = \phi(5 \cdot 13 \cdot 31) \\ = \phi(5) \phi(13) \phi(31)\\ = 4 \cdot 12 \cdot 30\\ = 1440.$ So 2015 has 1440 smaller coprimes, that is 720 pairs. So the sum of them all is $720 \cdot 2015 = \boxed{1450800}$ .

There are $\phi(2015) = \phi(5)\phi(13)\phi(31) = 4\cdot 12\cdot 30 = 1440$ numbers co-prime to 2015. I guessed that they would be evenly distributed, so that on average they are equal to 2015/2. Multiplying gives $1440\cdot \frac{2015}2 = \boxed{1450800}.$

(On second thought, the "guess" is easily justified. The list of $\text{gcd}(n,\bullet)$ from $0\dots n$ is symmetric, since $\text{gcd}(n, k) = \text{gcd}(n, n-k)$ . This justifies taking the average.)

Here is a bit longer (but more elementary) solution by using arithmetic sequences (we use the Sn formula multiple times for integers between 1 and 2015, then integers within this interval divisible by 5, 13, 31, 5×13, 5×31, 13×31 and 5×13×31=2015) and the principle of inclusion-exclusion:

$\frac {1+2015}{2}×2015 - \frac {5+2015}{2}×13×31 - \frac {13+2015}{2}×5×31 - \frac {31+2015}{2}×5×13 + \frac {5×13+2015}{2}×31 + \frac {5×31+2015}{2}×13 + \frac {13×31+2015}{2}×5 - 2015 = \boxed {1450800}$

(This could be a way Gauss could have done (or at least would have understood) ... when he was a 5th grader.)

According to the question, k and 2015 are relatively co-prime to each other and how that could be possible is by factorizing 2015 and eliminate all the numbers from the given range which are multiples of 2015's factors i.e 2015=5 13 31 and we have to get all the numbers which are of the form 1k,5k,13k,31k,65k,155k,403k,2015k and subtract their sum from (2015 2016)/2 so the final answer would be (2015 2016)/2-[Sum of elements of the form 5k+Sum of elements of the form 13k+Sum of elements of the form 31k-Sum of elements of the form 65k-Sum of elements of the form 155k-Sum of elements of the form 403k+Sum of elements of the form 2015k] =(2015*2016)/2-{403(5+2015)/2+155(13+2015)/2+65(31+2015)/2-31(65+2015)/2-13(155+2015)/2-5(403+2015)/2+2015} =1450800.