# Is it always true that $\sum_{i=1}^{a-1}(-1)^i(a,i)\ge-1$?

Following is an experimental math claim.

We denote $$(a,b)=\gcd(a,b)$$.

Let $$G(a)=\sum_{i=1}^{a-1}(-1)^i(a,i).$$

Note:

$$G(a) = \begin{cases} 0, & \text{if a\equiv 1\pmod4} \\ \text{odd}, & \text{if a\equiv 2\pmod4} \\ 0, & \text{if a\equiv 3\pmod4} \\ \text{even}, & \text{if a\equiv 0\pmod4.} \end{cases}$$

Can it be shown that for every $$a\in\mathbb{Z}_{\ge2}$$, $$G(a)\ge-1$$?

Table

$$\begin{array}{|c |c |} \hline a & G(a) \\ \hline 2 & -1 \\ \hline 3 & 0 \\ \hline 4 &0 \\ \hline 5 &0 \\ \hline 6 &-1 \\ \hline 7 &0 \\ \hline 8 &4 \\ \hline 9 &0 \\ \hline \vdots &\vdots \\ \hline \end{array}$$

source code PARI/GP

for(a=1,10000,if(sum(i=1,a-1, (-1)^i*gcd(a, i))<-1,print([a])))

• This is somewhat like oeis.org/A106475 "An alternating sum of greatest common divisors". May 16 at 0:56
• Also, $-(G(a) + (-1)^aa)$ gives oeis.org/A199084 May 16 at 14:23
• Added this sequence as oeis.org/A344373 along with two related sequences. May 16 at 15:06
• This question raises several further questions about iterates (which are probably very hard). For example, is 12 the unique $a$ with $G(G(G(a)))=0$, $G(G(a))\ne0$? Or, there seem to be many $a$ with $G(a)$, $G(G(a))$, $G(G(G(a)))$, ... never stabilizing. Can one actually prove that there is some such? In fact, it seems that $-1$, $0$ and $16$ are the only sinks. Is this so? Are there any periodic orbits of iterates? There also seem to be many $x$ with $G^{-1}(x)$ empty. Can one characterize those? May 16 at 16:02

Yes, it is true. Further we suppose that $$a=2b$$ is even, as for odd $$a$$ the sum $$G(a)$$ equals 0 due to pairing $$\{i,a-i\}$$.

We start with $$(a,i)=\sum_{d|(a,i)}\varphi(d)=\sum_{d|a} \varphi(d)\cdot \mathbf{1}_{d|i}.$$ Therefore $$G(a)=\sum_{i=1}^{a-1}(-1)^i(a,i)=\sum_{d|a}\varphi(d)\sum_{i=1}^{a-1}(-1)^i \mathbf{1}_{d|i}.$$ The inner sum $$\sum_{i=1}^{a-1}(-1)^i \mathbf{1}_{d|i}$$ equals $$a/d-1$$ if $$d$$ is even and equals $$-1$$ if $$d$$ is odd (since it is a sum of $$a/d-1=2b/d-1$$ alternating $$\pm 1$$'s). Thus $$G(a)=\sum_{d|a,d\,\text{is even}} \varphi(d)(a/d-1)-\sum_{d|a,d\,\text{is odd}}\varphi(d).$$ Denote $$b=2^sc$$ for non-negative integer $$s$$ and odd $$c$$. Then odd divisors of $$a$$ are exactly divisors of $$c$$, and we have $$\sum_{d|a,d\,\text{is odd}}\varphi(d)=\sum_{d|c}\varphi(d)=c.$$ If 4 divides $$a$$, then $$a/(2d)-1\geqslant 1$$ for each divisor $$d$$ of $$c$$, and we get $$\sum_{d|a,d\,\text{is even}} \varphi(d)(a/d-1)\geqslant \sum_{d|c} \varphi(2d)(a/(2d)-1)\geqslant \sum_{d|c} \varphi(2d)=\sum_{d|c} \varphi(d)=c,$$ thus $$G(a)\geqslant 0$$. Finally, it remains to consider the case when $$b=c$$ is odd. Then we have $$\sum_{d|a,d\,\text{is even}} \varphi(d)(a/d-1)=\sum_{d|c} \varphi(2d)(a/(2d)-1)= \sum_{d|c}\varphi(d)(c/d-1)=-c+c\sum_{d|c} \varphi(d)/d,$$ and $$G(a)\geqslant -1$$ reads as $$c\sum_{d|c} \varphi(d)/d\geqslant 2c-1.$$ This may be proved by $$\sum_{d|c} \varphi(d)/d=1+\sum_{d|c,d>1} \varphi(d)/d\geqslant 1+ \sum_{d|c,d>1} \varphi(d)/c=1+(c-1)/c=(2c-1)/c.$$

• Thanks for answer. please explain, what this ${\bf 1}_{d|i}$ represent ? May 16 at 4:11
• That is the indicator function: 1 if $d$ divides $i$ and 0 otherwise. May 16 at 4:35

$$G(a)+(-1)^aa=\sum_{i=1}^{a} (-1)^i (a,i)=\sum_{d|a} d \sum_{\substack{ l \\ (l, a/d)=1}} (-1)^{dl}=T(a).$$

When, $$a$$ is odd, $$d, a/d$$ is also odd. Hence, $$\sum_{\substack{l, \\ (l,a/d)=1 \\ d So, $$T(a)=(-1)^aa \rightarrow G(a)=0$$.

Now, for $$a=2^{r_0}m, m=\prod_{i=1}^s p_i^{r_i}$$ odd, $$T(a)=\sum_{\text{d even}} d\phi(a/d) - \sum_{\text{d odd}} d\phi(a/d)$$ (because, for $$d$$ even $$(-1)^d=1$$, and for $$d$$ odd, $$a/d$$ even, so $$l, dl$$ is odd). \begin{align*} & {}=a\sum_{l\mid\frac{a}{2}} \frac{\phi(l)}{l}-\sum_{l \mid m}\frac{\phi(2^rl)}{2^rl} \\ & {}=a(\sum_{l\mid\frac{a}{2}} \frac{\phi(l)}{l}-\frac{1}{2}\sum_{l|m}\frac{\phi(l)}{l}). \end{align*} Now, $$\sum_{d\mid n} \frac{\phi(d)}{d}=\prod_{i} (1+(1-\frac{1}{p_i})r_i)$$, where $$n=\prod_i p_i^{r_i}$$.

Using this to the sum we get, the explicit formula for $$G(a)$$: $$G(a)=\frac{ar_0}{2p_1p_2\dotsm p_s}\prod_{i=1}^{s} (p_i(r_i+1)-r_i) -a.$$

It's easy to see from the formula that $$G(a)$$ is odd when $$r_0=1$$ and even when $$r_0>1$$, because all $$p_i$$ are odd, hence each $$p_i(r_i+1)-r_i$$ is odd, and $$a$$ is even.

More compactly, $$G(a)=a[\frac{r_0}{2}\prod_{i=1}^{s} (r_i+1-\frac{r_i}{p_i})-1]$$.

Surely, $$G(a) \geq -1$$. It's $$-1$$, for $$a=2p$$ types, e.g. $$a=6$$.