<s>[INST] $\gcd(c^a + 1, c^b + 1)$ for even $a$ and $b$? Following on this question, what is the Greatest Common Denominator of $c^a + 1$ and $c^b + 1$, where $a, b, c \in N$. I know that for odd a and b, we have $\gcd(c^a + 1, c^b + 1) = c^{\gcd(a, b)} + 1$ Thanks, Aleks Vlasev
I also found that for a odd and b even (or vice versa), the result is 1 or 0 depending on odd or even c.
The last case remains: For both $a$ and $b$ even: How can $gcd(c^a +1, c^b+1)$ be simplified such that it can be computed more quickly?
I tried to adapt this answer to my case but got nowhere*. Or maybe I should be using Fermat's little theorem?
Edit:
I did use the last linked answer to simplify this. Let a > b, $(c^b + 1, c^a + 1) = (c^b + 1, -c^{a-b} + 1)$.
 [/INST] Let $2^r$ be the highest power of 2 dividing $a$ and $2^s$ the highest power of 2 dividing $b$. Then if $r\ne s$, $\gcd(c^a+1,c^b+1)=2$ if $c$ is odd and 1 if $c$ is even. On the other hand, if $r=s$, $\gcd(c^a+1, c^b+1)=c^{\gcd(a,b)}+1$.
Proof: Suppose $n>2$ is a factor of $c^a+1$ and $c^b+1$. Then let $k$ be the smallest non-negative integer such that $n$ is a factor of $c^k+1$. Then by considering the powers of $c$ ($\bmod n$), it is clear that $n$ is a factor of $c^t+1$ if and only if $t=(2r+1)k$ for some $r$.
Thus $a$ and $b$ must be multiples of $k$ with $\frac ak$ and $\frac bk$ both odd. This means the same powers of $2$ are factors of $a$ and $b$, and $k$ is a factor of $\gcd(a,b)$ with $\frac{\gcd(a,b)}k$ odd, so $n$ is a factor of $c^{\gcd(a,b)}+1$.
QED
</s>