Alternating sums of GCDs - MathOverflow

Alternating sums of GCDs

2012-01-06T21:39:23Z

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:

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.))
If $n$ is an odd number [edit: not of the form $2p-1$, prime $p$] (see A166257), then $s_n < 0$
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.

Answer by Alan Haynes for Alternating sums of GCDs

2012-01-06T23:42:02Z

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.

Answer by Gjergji Zaimi for Alternating sums of GCDs

2012-01-06T23:44:29Z

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