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.

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.

share|improve this question
1  
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
,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

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.