# $2^n+1 =xy \implies (2^a|(x-1) \iff 2^a|(y-1))$

I'd like my proof to be verified of the following exercise from Niven's The Theory of Numbers.

Section 1.1 Problem 52: Suppose $2^n+1=xy$, where $x$ and $y$ are integers $>1$ and $n>0$. Show that $2^a|(x-1)$ if and only if $2^a|(y-1)$.

Proof: Suppose $2^a|(x-1)$. Then $(x-1)=2^ak$, for some $k\in\mathbb{N}$ and so \begin{align*} \implies x&=2^ak+1\\ \implies xy&=2^aky+y\\ \implies xy-1 &= 2^aky+y-1\\ \implies y-1 &= 2^a(-k)y+xy-1\\ \implies y-1 &= 2^a(2^{n-a}-ky). \end{align*}

I believe my proof to be complete (once noting that this is done without loss of generality). However, I wonder if there is a nicer way to prove this.

• How do you prove $2^a \mid 2^n$? Commented May 24 at 23:18

Let $\displaystyle x=A2^a+1,y=B2^{a+c}+1$ where positive integers $A,B$ are odd and $c\ge0$

$\displaystyle\implies xy=AB2^{2a+c}+A2^a+B2^{a+c}+1=2^n+1$

$\displaystyle\implies AB2^{a+c}+A+B2^c=2^{n-a}$ which is even as $n>a$ as $x,y>1$

but $\displaystyle AB2^{a+c}+A+B2^c$ is odd if if $\displaystyle c>0$

• Thank you for the reply. One question though, why can we assume that both $y-1$ is divisible by $2^{a+c}$ for some $c\geq0$? Commented May 6, 2014 at 19:26

I think is the same idea but it is quicker.

$$2^n + 1 = xy = (x-1 + 1) y = (x-1)y + y$$

Then

$$2^n = (x-1)y + (y -1)$$

If $a \leq n$ we have the result, only we have remember if $d$ divides two terms in $A + B = C$, then $d$ divides the third term.