The exciting question on [alternating sums of binomial coefficients][1] triggered me to ask the following much simpler question (sorry if it is too simple, but I'm not a number theorist, so I must be overlooking something obvious).

Consider the sum:
$$s_n := \sum_{i=1}^n (-1)^{i-1}\gcd(n+1,i).$$

Simple numerical experiments suggest the following:

1. If $n=2p-1$ for a prime $p$, then $s_n = 1$  [*Edit*] as Kevin observed, this one follows immediately, because the gcd is either $1$, $2$, or $p$, and it is easy to see which term contributes which part (even, odd, etc.))

2. If $n$ is an odd number [edit: not of the form $2p-1$, prime $p$] (see [A166257][2]), then $s_n < 0$

3. otherwise, of course, $s_n=0$.

How should I prove this? Observe that the $\alpha$-generalization of $s_n$ (i.e., summing $\mbox{gcd}^\alpha$ terms instead) does not satisfy the above observations.


  [1]: http://mathoverflow.net/questions/85013/alternating-sum-of-square-roots-of-binomial-coefficients
  [2]: http://oeis.org/A166257