<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] If $b=a$, then we have the trivial case $c^b+1 = c^a+1$.
Now take $b>a$ (without loss of generality). Note that $\gcd(r,s) \mid \gcd(r+s,r-s)$ for all integers $r,s$. Hence here we need consider
\begin{align}
  &\gcd(c^b+c^a+2,c^b-c^a)\\
  &\qquad= \gcd(c^b+c^a+2, c^a(c^{b-a}-1)) \\
  &\qquad= \gcd\left(c^b+c^a+2, c^a(c-1)(c^{b-a-1}+c^{b-a-2}+\dotsb+1)\right).
\end{align}
Now you can do a factor-by-factor examination, e.g., $\gcd(c^a,c^b+2)$.
EDIT: Notice that right away you can eliminate any odd prime factors of $c-1$, since $\gcd(c-1,c^a+1)=1$ or $2$ because $a$ is even. Hence you only really have to consider
\begin{align}
 \gcd\left(c^b+c^a+2, c^a(c^{b-a-1}+c^{b-a-2}+\dotsb+1)\right).
\end{align}
</s>