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}\mbox{gcd}(n+1,i).$$

Simple numerical experiments suggest the following:

1. If $n=2p-1$ for a prime $p$, then $s_n = 1$
2. If $n$ is an odd number not of the form "prime(k)+phi(prime(k))" (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