MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Hint for (1): $gcd(2p,i)$ is (for $i$ in your range) either 1, 2 or $p$, and it's easy to say which. – Kevin Buzzard Jan 6 '12 at 21:57
And "not of the form prime(k)+phi(prime(k))" is quite an obfuscated way to say "not of the form $2p−1$ for $p$ prime"! – Kevin Buzzard Jan 6 '12 at 21:59
I don't think you should delete it. Instead, consider modifying it. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.01.06 – Gerhard Paseman Jan 6 '12 at 22:09
@Gerhard: incorporated your suggestion. But could you make the connection to Jacobsthal's function explicit? thanks. – Suvrit Jan 6 '12 at 22:18
One possible variation would be to keep a running total, changing sign only when the value 1 is encountered. The longest monotonic consecutive subsequence would then be of length j(n+1), for example. I could motivate such a change for myself, but I don't know if it would move others. Gerhard "Ask Me About System Design" Paseman, 2012.01.06 – Gerhard Paseman Jan 6 '12 at 22:38
up vote 9 down vote accepted

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", 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$.

share|cite|improve this answer
Wow, that's a rather recent reference! – Suvrit Jan 7 '12 at 14:25

Actually both (2) and (3) are true, and there is a relatively short proof:

First of all we have that $$s_n=\sum_{d|n+1, d< n+1}d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{id-1}.$$

Sorry for the bad typesetting, the compiler here doesn't seem to like \substack. Ok to be sure this is clear, the inner sum is over $i$ running from $1$ to $(n+1)/d-1,$ which are coprime to $(n+1)/d$.

First notice for later reference that when $d$ is even the inner sum over $i$ is negative. On the other hand if $d$ is odd then the inner sum is equal to $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}.$$ Furthermore if $(n+1)/d$ is odd then the map $i\mapsto (n+1)/d-i$ is a bijection between integers coprime to $(n+1)/d$, and it reverses parity. Therefore when both $d$ and $(n+1)/d$ are odd we have that $$\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}=0.$$ Plugging this in above proves (3) right away.

To prove (2) we write $n+1=2^km$ with $m$ odd. Suppose that $d|(n+1),~d<(n+1)/2,$ and $d$ is odd. Then $2^k d|(n+1)$ and $2^k d < n+1,$ and pairing the contribution in the above sum from $d$ with that from $2^kd$ gives $$d\sum_{i=1, (i, (n+1)/d)=1}^{(n+1)/d-1}(-1)^{i-1}-2^kd\sum_{i=1, (i, (n+1)/2^kd)=1}^{(n+1)/2^kd-1}1$$ $$\le d\varphi \left( 2^k\cdot\frac{n+1}{2^kd}\right)-2^kd\varphi \left(\frac{n+1}{2^kd}\right)$$ $$=-2^{k-1}d\varphi \left(\frac{n+1}{2^kd}\right)<0.$$ As we mentioned before, all of the even divisors $d$ contribute a negative amount to $s_n$, so everything is accounted for except for the case when $d=(n+1)/2$ is odd. In this case we have that $k=1$, and the term in the top sum corresponding to $d=(n+1)/2$ is $$ \frac{n+1}{2}\sum_{i=1, (i,2)=1}^1 (-1)^{i-1} = \frac{n+1}{2} . $$

However using our previous calculation the sum of contributions from all of the other odd divisors $e<(n+1)/2$, paired with the divisors $2e$, is $$\le -\sum_{e|(n+1)/2,e<(n+2)/2}e\varphi\left(\frac{n+1}{2e}\right)$$ $$=-\frac{n+1}{2}\cdot\sum_{e|(n+1)/2,e>1}\frac{\varphi (e)}{e}$$ $$=-\frac{n+1}{2}\left(\prod_{p^a||(n+1)/2}\left(1+a(1-1/p)\right)-1\right).$$ Now if $(n+1)/2$ is composite then either $a>1$ for one of the primes above, or there is more than one prime in the product above (also if you are trying to follow this calculation then note that all primes in the product above must be odd). In either case it is trivial to check that the quantity above is strictly less than $-(n+1)/2$, therefore $s_n<0$.

So to summarize, the even divisors contribute a negative amount to the overall sum, we pair every odd divisor $d$ with the contribution from $2^kd$ to get a negative quantity, and we combine these quantities with the divisor $(n+1)/2$ if it is odd. That finishes the proof.

share|cite|improve this answer
Thanks for your nice answer. I'd have liked to accept this answer too if I could. – Suvrit Jan 7 '12 at 14:26
@Suvrit Thanks, actually I had to add a little in the end but I think it is now correct. – Alan Haynes Jan 7 '12 at 20:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.