# If $\gcd(a,b)=1$ , and $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$?

How to prove that:

$\gcd(a,b)=1 \Rightarrow \gcd(2^{a}+1,2^{b}+1)=1$ ,where $a$ is even and $b$ is odd natural number

For example:

$\gcd(2^8+1,2^{13}+1)=1 , \gcd(2^{64}+1,2^{73}+1)=1$

I know that Knuth showed that:

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

so: $\gcd(a,b)=1\Rightarrow \gcd(2^{a}-1,2^{b}-1)=1$

but I don't see whether this fact is useful.

-
I highly doubt Knuth was the first to show that equality... –  Ragib Zaman Nov 3 '11 at 6:20
@Ragib,maybe you are right but see bottom of this page –  pedja Nov 3 '11 at 6:27
Do you have reason to believe this is true? If so, perhaps its possible to use the three-branch generation of odd-odd coprime pairs to explicitly construct any pair $2^a+1,2^b+1$ as described. –  anon Nov 3 '11 at 6:55
@anon,I have checked for many $(a,b)$ pairs using Maple.$\gcd$ is always $1$ –  pedja Nov 3 '11 at 7:09

This is a minor tweak of my answer to an earlier post by user952949. That one asked for a proof that if $a$ and $b$ are relatively prime and odd, then $\gcd(2^a+1,2^b+1)=3$.

A very useful fact: If $a$ and $b$ are relatively prime, there exist integers $x$ and $y$ such that $ax+by=1$.

We can arrange for $x$ to be $\ge 0$ and $y$ to be $\le 0$. So there are non-negative integers $u$ and $v$ such that $au=bv+1$. Thus $$2^{au}=2^{bv+1}=2\cdot 2^{bv}. \qquad\text{(Equation 1)}$$

Let $m$ be any common divisor of $2^a+1$ and $2^b+1$. Then $2^a \equiv -1\pmod{m}$ and $2^b\equiv -1 \pmod m$. It follows that $$2^{au} =(2^a)^u \equiv (-1)^u \pmod{m} \qquad\text{and}\qquad 2^{bv} =(2^b)^v \equiv (-1)^v \pmod{m}.$$ From Equation $1$, we conclude that $$(-1)^u \equiv 2\cdot (-1)^v\pmod{m}.$$ If $(-1)^u=(-1)^v$, we find that $1\equiv 0\pmod{m}$, so the only positive common divisor of $2^a+1$ and $2^b+1$ is $1$. If $(-1)^u=-(-1)^v$, we find that $3\equiv 0\pmod{m}$.

If we only know that $3\equiv 0\pmod{m}$, then all we can say is that any common divisor of $2^a+1$ and $2^b+1$ divides $3$.

We need to rule out the possibility that $3$ divides both of $2^a+1$ and $2^b+1$. This is easy. One of $a$ or $b$ is even, say $a$. Then $2^a\equiv 1 \pmod{3}$, so $2^a+1$ is not divisible by $3$.

-

We post a second answer that, instead of doing details, recycles old results. The OP mentioned the following standard result, but was not sure it was useful:
$$\gcd(2^{x}-1,2^{y}-1)=2^{\gcd(x,y)}-1.$$ It is useful! By the result, if $\gcd(a,b)=1$, then $$\gcd(2^{2a}-1,2^{2b}-1)=2^{2}-1=3.$$ Thus
$$\gcd((2^{a}+1)(2^a-1)\;,\;(2^b+1)(2^b-1)=3.$$ It follows that any common divisor of $2^a+1$ and $2^b+1$ must divide $3$, and therefore $\gcd(2^a+1,2^b+1)$ is $1$ or $3$.

Like in the other answer, we rule out $3$ by using the fact that one of $a$ and $b$, say $a$, is even. For even $a$, $2^a\equiv 1\pmod{3}$, so $3$ does not divide $2^a+1$.

-
,could you make some comment on this answer ? –  pedja Nov 3 '11 at 14:14
@pedja: Maybe I will comment on it later. I have just posted another answer to that more general question. You may like it, it uses only familiar machinery, including again the result you quoted, and some basic divisibility results. –  André Nicolas Nov 3 '11 at 16:55