5
$\begingroup$

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?

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

1 Answer 1

22
$\begingroup$

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

$\endgroup$
8
  • 2
    $\begingroup$ I love infinite descent arguments. This is a pretty clever one. $\endgroup$ Jul 31, 2013 at 4:39
  • 1
    $\begingroup$ Very nice argument. It shows that in general $y^a+1$ is not divisible by $y^b-1$ for any $y>1$, right? $\endgroup$
    – Prism
    Jul 31, 2013 at 4:56
  • $\begingroup$ With a small number of exceptions! $\endgroup$ Jul 31, 2013 at 5:01
  • $\begingroup$ Can you explain the last line a little more please? $\endgroup$
    – James
    Aug 1, 2013 at 7:15
  • 1
    $\begingroup$ 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! $\endgroup$ Aug 1, 2013 at 16:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .