$\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)$.
 A: 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}
A: 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
