Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$

Question

Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$.

I was thinking among the lines of:

Since $a$ and $b$ are coprime numbers, $\gcd(a,b)=1$. Then there exist integers $x$ and $y$ such that, $ax+by=1$.

Then, $a=(1-by)/x$, $b=(1-ax)/y$

So if I write $2^a+1$ as:

$2^{(1-by)/x}+1$

Then can I say that the above expression is equivalent to 0 (mod 3)?

Answer 1

Note that both $2^a+1$ and $2^b+1$ are odd, so any common divisor is odd.

Now, if $d$ divides $2^a+1$ and $2^b+1$, then it also divides $(2^a+1)-(2^b+1) = 2^a-2^b$, hence it divides $2^{\min(a,b)}(2^{|a-b|}- 1)$. But since $d$ is odd, then $d$ divides $2^{|a-b|}-1$. That is, if, say, $a\geq b$, then $$d|2^{a}-1,2^b-1 \Longleftrightarrow d|2^a-1, 2^b-1, 2^{a-b}-1.$$ But if $d$ divides both $2^{a-b}-1$ and $2^b-1$, then it divides $$2^b(2^{a-b}-1) + (2^b-1) = 2^a-1.$$ So: $$d|2^a-1,2^b-1 \Longleftrightarrow d|2^b-1, 2^{a-b}-1.$$ We are assuming $a\geq b$; be careful with that assumption; more generally, we have: $$\text{For }a,b\text{ odd, }\gcd(2^a-1,2^b-1) = \gcd(2^{\min(a,b)}-1, 2^{|a-b|}-1).$$

This looks very much like the gcd identity $$\gcd(x,y) = \gcd(y,x-y),$$ which is very useful. Maybe you can make it work for you?

Answer 2

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}.$$ Since $a$ and $b$ are odd, $u$ and $v$ have opposite parity. Thus $-1\equiv 2\pmod {m}$, that is, $3\equiv 0 \pmod m$, and therefore $m$ divides $3$.

If $c$ is odd, then $2^c\equiv -1\pmod{3}$, so $3$ divides $2^c+1$. Thus $3$ divides our gcd. But our gcd divides $3$, so it is $3$.

Answer 3

If $d\mid 2^a+1$, then $2^a \equiv -1 \pmod d$. But then that means that the order of $2\pmod d$ must be a divisor of $2a$. Similarly, if $d\mid 2^b +1$, the order of $2 \pmod d$ must divide $2b$. But that means that order of $2\pmod d$ must divide $(2a,2b)=2$. So the order of $2\pmod d$ must be a divisor of $2$, or $2^2=1\pmod d$. So $d=3$ or $d=1$.

Answer 4

One of the possible form of odd coprime numbers is:

$a=2m-n$ and $b=m$ , (see this page)

So we may write following equalities:

$2^{a}+1=2^{2m-n}-2+3=2(2^{2m-n-1}-1)+3$

$2^{b}+1=2^{m}-2+3=2(2^{m-1}-1)+3$

So in order to prove that $\gcd(2^{a}+1,2^{b}+1)=3$ we need to prove that:

$\gcd(2^{2m-n-1}-1,2^{m-1}-1)=2^{\gcd(2m-n-1,m-1)}-1=3\cdot p $ for some natural number $p$

The last equality is true only if: $\gcd(2m-n-1,m-1)=2\cdot k$ (even number) for all $m,n$. Since $m$ and $n$ are odd numbers you can easily show that this is always true.

Similarly you can show for other two forms of $a$ and $b$ that $\gcd(2^{a}+1,2^{b}+1)=3$