The exciting question on alternating sums of binomial coefficients 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), 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.