Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
3  
You can show that $2^a+1$ and $2^b+1$ are multiples of $3$ simply enough: since $a=2k+1$, then $2^a+1 = 2(2^{2k})+1 = 2(4^k)+1$, and since $4\equiv 1\pmod{3}$, then $2^a+1 \equiv 2(4^k)+1 \equiv 2(1)+1 = 0\pmod{3}$. Same with $2^b+1$. But the fact that they are both divisible by $3$ only tells you the gcd is a multiple of $3$, it doesn't tell you the gcd is $3$. –  Arturo Magidin Nov 2 '11 at 17:07
    
Good point, I was thinking of that at first, but your right, it doesn't prove that gcd is 3 –  user952949 Nov 2 '11 at 17:29
    

4 Answers 4

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?

share|improve this answer
    
Thanks, I think I will see where I can get with this. –  user952949 Nov 2 '11 at 17:30
    
@Arturo, I think you forgot 'are odd' in your first sentence right after $2^{b} + 1$. –  sxd Nov 2 '11 at 17:41
    
@DimitriSurinx: So I did; thank you. –  Arturo Magidin Nov 2 '11 at 18:03

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$.

share|improve this answer

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$.

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.