gcd of power plus one

Let's first deal with the cases $a = 0$ and $a = 1$ separately.

For $a = 0$ we have $a^m + 1 = 1$ if $m > 0$ and $a^0 + 1 = 2$, so $\gcd(0^b+1, 0^c+1) = 1$ if $b > 0$ or $c > 0$, and $\gcd(0^0+1, 0^0+1) = 0^0+1$. So $\gcd(0^b+1, 0^c+1) = 0^{\gcd(b,c)} + 1$. For $a = 1$ we have $a^m + 1 = 2$ for all $m \in \mathbb{N}$ and hence $\gcd(1^b+1, 1^c+1) = \gcd(2,2) = 2 = 1^{\gcd(b,c)} + 1$.

Next we consider $a \geqslant 2$. We know

$$\gcd(a^{2b}-1, a^{2c}-1) = a^{\gcd(2b,2c)}-1 = a^{2\gcd(b,c)}-1 = (a^{\gcd(b,c)}-1)(a^{\gcd(b,c)}+1)$$

and $\gcd(a^b-1,a^c-1) = a^{gcd(b,c)}-1$, hence

$$\gcd(a^b+1,a^c+1) \mid \gcd\biggl((a^b+1)\frac{a^b-1}{a^{\gcd(b,c)}-1}, (a^c+1)\frac{a^c-1}{a^{\gcd(b,c)}-1}\biggr) = a^{\gcd(b,c)}+1.$$

If $\nu_2(b) = \nu_2(c)$, then

$$a^{\gcd(b,c)}+1 \mid \gcd(a^b+1,a^c+1),$$

so in this case we have $\gcd(a^b+1,a^c+1) = a^{\gcd(b,c)}+1$.

If $p$ is an odd prime dividing $a^m+1$, then $\operatorname{ord}_p(a) \mid 2m$ but $\operatorname{ord}_p(a) \nmid m$, hence it follows that $\nu_2\bigl(\operatorname{ord}_p(a)\bigr) = \nu_2(m) + 1$. Thus, if $\nu_2(b) \neq \nu_2(c)$, no odd prime divides $\gcd(a^b+1,a^c+1)$, i.e.

$$\gcd(a^b+1,a^c+1) = 2^k$$

for some $k$. If $a$ is even, then $k = 0$ since $a^{\max \{b,c\}}+1$ is odd. The square of an odd number is $\equiv 1 \pmod{4}$, so $\nu_2(a^m+1) = 1$ if $a$ is odd and $\nu_2(m) \geqslant 1$.

We thus have

$$\gcd(a^b+1,a^c+1) = \begin{cases} a^{\gcd(b,c)}+1 &\text{if } \nu_2(b) = \nu_2(c) \\ \qquad 2 &\text{if } \nu_2(b) \neq \nu_2(c)\text{ and } a \equiv 1 \pmod{2} \\ \qquad 1 &\text{if } \nu_2(b) \neq \nu_2(c) \text{ and } a \equiv 0 \pmod{2}\end{cases} \tag{$\ast$}$$

for $a \geqslant 2$. Though $\gcd(a^b+1,a^c+1) = a^{\gcd(b,c)}+1$ for $a\in \{0,1\}$ and arbitary $b,c \in \mathbb{N}$, this also matches $(\ast)$.

For $a < 0$, we have $\gcd(a^b+1,a^c+1) = \gcd(\lvert a\rvert^b - 1, \lvert a\rvert^c-1) = \lvert a\rvert^{\gcd(b,c)}-1$ if $b$ and $c$ are both odd and $\gcd(a^b+1,a^c+1) = \gcd(\lvert a\rvert^b+1, \lvert a\rvert^c+1)$ if both are even. These give nothing new. If one exponent is even and the other odd, say $b$ is even, then, using $d = -a$, we have $\gcd(a^b+1,a^c+1) = \gcd(d^b + 1, d^c - 1)$ and

$$\gcd(d^b+1,d^c-1) \mid \gcd(d^{2b}-1,d^c-1) = d^{\gcd(2b,c)}-1 = d^{\gcd(b,c)}-1 = \gcd(d^b-1,d^c-1).$$

Since $\gcd(d^b+1,d^b-1) = \gcd(d^b+1,2) \mid 2$, it follows that $\gcd(d^b+1,d^c-1) = 1$ if $d$ is even, and $\gcd(d^b+1,d^c-1) = 2$ if $d$ is odd. Noting that $\lvert a\rvert^m - 1 = -(a^m+1)$ for $a < 0$ and odd $m$, we see that $(\ast)$ holds for all $a \in \mathbb{Z}$ if we don't insist on a non-negative $\gcd$. If we do,

$$\gcd(a^b+1,a^c+1) = \begin{cases}\lvert a^{\gcd(b,c)}+1\rvert &\text{if } \nu_2(b) = \nu_2(c) \\ \qquad 2 &\text{if } \nu_2(b) \neq \nu_2(c)\text{ and } a \equiv 1 \pmod{2} \\ \qquad 1 &\text{if } \nu_2(b) \neq \nu_2(c) \text{ and } a \equiv 0 \pmod{2}\end{cases} \tag{$\ast\ast$}$$

holds for all $a\in \mathbb{Z}$ and $b,c \in \mathbb{N}$.