GCD sum using Euler's Totient The problem is to find:
$$f(N)=\sum_{k=2}^N \gcd(K-1,N)\ where \gcd(N,K)=1 $$
For example:
$$N=50\\ f(N)=70$$
 $$N=100\\ f(N)=260$$
 $$N=524288 \\ f(N)=4718592$$
I am not very experienced with advanced math, however I understand coprime integers, Euler's Totient function and lemma.
Any tips on calculating this function using Euler's Totient function?
Edit: To clarify, The value of $gcd(k−1,N)$ should only be included in the sum for $f(N)$ when $gcd(k,N)=1$. Restricting the sum this way agrees with the example $f(N)$ values given.
 A: So you want to find $f(N)=\sum\limits_{k=1}^{N-1} \gcd(k,N)$.
Sure, there is a faster way, and it goes as follows: instead of traversing all $k$ and counting the gcd's, let's traverse the possible values of gcd and find out how many times each of them occurs in the sum. Really, how many are such $k$ that $\gcd(k,N)=d$?
Well, first of all, $d$ must be a divisor of $N$. Also, $k$ must be a multiple of $d$; how many such multiples do not exceed $N$? Obviously, ${N\over d}$. But wait, some of these multiples may have greater common divisors with $N$, so we just need those where $N\over d$ and $k\over d$ are coprime. Well, this sounds mighty like the definition of the totient function. So in the end, our formula wraps up like this:
$$f(N)=\sum_{\substack d|N\\d<N}d\cdot\varphi\left({N\over d}\right)$$
A cursory glance at OEIS A006579 could have helped you a lot. Then there is a related sequence OEIS A018804, with definition similar to yours, but with summation up to $N$, which makes it a lot more natural and nice (it is multiplicative, to begin with), but that's another story.
