# $2^a +1$ is not divisible by $2^b-1$.

Let $a,b>2$ be positive integers. We need to show that $2^a +1$ is not divisible by $2^b-1$.

Could any one give me hint?

• Not sure if this will help, but have you tried looking at mods (e.g. mod 3, 5, 7)? Jul 31, 2013 at 4:31
• Wlog $a>b>1$. $2^b\equiv1\Rightarrow 2^a\equiv1^{a-b}$ mod $(2^b-1)$.
– anon
Jul 31, 2013 at 4:34
• except that isn't WLOG since divisibility is not symmetric. Jul 31, 2013 at 4:37
• Indeed, it isn't wlog by symmetry, it's wlog for other reasons.
– anon
Jul 31, 2013 at 4:47
• Apr 26, 2016 at 15:08

Let $b$ be a fixed positive integer. If there is a $k$ such that $2^b-1$ divides $2^k+1$, then there is a smallest such $k$. Call this smallest $k$ by the name $a$.

We first show that $a\lt b$. Suppose to the contrary that $a\ge b$. Note that $$2^a+1=2^{a-b}(2^b-1) +2^{a-b}+1.$$ Thus if $2^b-1$ divides $2^a+1$, then $2^{b}-1$ divides $2^{a-b}+1$, contradicting the minimality of $a$.

It follows that $2^b-1$ divides $2^a+1$ for some $a\lt b$. In particular, $2^b-1\le 2^a+1\le 2^{b-1}+1$.

From $2^b-1\le 2^{b-1}+1$, we conclude that $2^{b}-2^{b-1}=2^{b-1}\le 2$. Thus $b-1\le 1$ and therefore $b\le 2$.

Remark: If $b=1$, then $2^b-1$ divides $2^a+1$ for all $a$. If $b=2$, then $2^b-1$ (that is, $3$) divides $2^a+1$ for all odd values of $a$.

• I love infinite descent arguments. This is a pretty clever one. Jul 31, 2013 at 4:39
• Very nice argument. It shows that in general $y^a+1$ is not divisible by $y^b-1$ for any $y>1$, right? Jul 31, 2013 at 4:56
• With a small number of exceptions! Jul 31, 2013 at 5:01
• Can you explain the last line a little more please? Aug 1, 2013 at 7:15
• You are welcome. Note that the structure of the proof "explains" why $b=2$ is an exception. $2^b-1$ is almost always bigger than $2^{b-1}+1$, but not quite always! Aug 1, 2013 at 16:54