The exciting question on [alternating sums of binomial coefficients](https://mathoverflow.net/questions/85013/alternating-sum-of-square-roots-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](http://oeis.org/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.



Alternating sums of GCDs
One can compute this sum explicitly. Let $n+1=2^a \prod\_i p\_i^{\alpha\_i}$ with $a\geq 1$, then we have:
$$\sum\_{i=1}^n (-1)^{i-1}\mbox{gcd}(n+1,i)=(-1)^{n-1}(n+1)-a2^{a-1}\prod\_i\left((\alpha\_i+1)p\_i^{\alpha\_i}-\alpha\_ip\_i^{\alpha\_i-1}\right)$$
as was proved in 



> 
> Laszlo Toth, ["Weighted Gcd-Sum Functions"](http://www.emis.ams.org/journals/JIS/VOL14/Toth/toth9.pdf), Journal of Integer Sequences, Vol. 14 (2011)
> 
> 
> 


So $s \_n = (n+1) \left( (-1)^{n-1} -\frac{a}{2}\prod \_i (1+\frac{\alpha \_i(p \_i-1)}{p \_i})\right)$. It is easy to see from here that if $n$ is odd, then $s\_n$ is positive only if $n=2p-1$.


