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]: https://mathoverflow.net/questions/85013/alternating-sum-of-square-roots-of-binomial-coefficients [2]: http://oeis.org/A166257