Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to prove that:

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

This statement is generalization of the statement from my previous question.

I have checked for many $(a,b)$ pairs using Maple, and $\gcd(2^{a}+1,2^{b}+1)$ is always $1$

For example : $\gcd(2^{66}+1,2^{33}+1)=1 , \gcd(2^{4422}+1,2^{3333}+1)=1$ and so on.

share|cite|improve this question
up vote 3 down vote accepted

Looking for a counterexample with $a$ is even and $b$ is odd and $\gcd(2^{a}+1,2^{b}+1)=k \gt 1$ then

  1. the order of $2 \mod k$ is must be odd for $a$ and $b$ to have different parities, and so the order of $2 \mod p$ of any prime factor $p$ of $k$ must also be odd
  2. $k$ divides both $2^{a}+1$ and $2^{b}+1$ and so any prime factor $p$ of $k$ divides both $2^{a}+1$ and $2^{b}+1$

This is not possible, since the primes $p$ such that the order of $2 \mod p$ is odd (OEIS A014663) are also the primes $p$ which do not divide $2^n+1$ for any $n$. Since there are no counterexamples with $a$ and $b$ different parities, the assertion is true.

share|cite|improve this answer
,I don't understand why the order of $2\mod k$ must be odd for $a$ and $b$...can you explain that ? – pedja Nov 3 '11 at 12:04
If $2^a = k-1 \text{ (or }-1\text{)}\mod k$ and $2^b = k-1 \text{ (or }-1\text{)}\mod k$ then the order of $2 \mod k$ must divide $|a-b|$, which by supposition is odd. – Henry Nov 3 '11 at 16:40
thanks for explanation – pedja Nov 4 '11 at 4:34

The following result is well-known. Solutions have even been posted on this site: $$\gcd(2^{x}-1,2^{y}-1)=2^{\gcd(x,y)}-1.$$ Let $d=\gcd(a,b)$. Then $\gcd(2a, 2b)=2d$, and therefore $$\gcd((2^{2a}-1,2^{2b}-1)=\gcd((2^{a}+1)(2^a-1)\;,\;(2^b+1)(2^b-1))=2^{2d}-1.$$ Since $d$ is odd, $2d$ divides $a$, and therefore $2^{2d}-1$ divides $2^a-1$. Note also that $\gcd(2^a+1,2^a-1)=1$ (unless $a=0$). Now we have all the pieces we need.

We are trying to prove that $\gcd(2^a+1,2^b+1)= 1$. Suppose to the contrary that the gcd is $>1$. Then there is a prime $p$ that divides both $2^a+1$ and $2^b+1$. Thus $p$ divides $\gcd((2^{a}+1)(2^a-1)\;,\;(2^b+1)(2^b-1))$, so $p$ divides $2^{2d}-1$. But $2^{2d}-1$ is a factor of $2^a-1$, so $p$ divides $2^a-1$.

Since $2^a+1$ and $2^a-1$ are relatively prime, $p$ cannot divide $2^a+1$, and we have our contradiction.

share|cite|improve this answer

Your Answer


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.