Solution to Divisibility Problem

I have attempted to solve problem which is stated as follows:

$2^n+1=xy$ where $n>0$ and $x,y>1$. Prove that $2^a$ divides $x-1$ iff $2^a$ divides $y-1$.

My solution is as follows:

$x$ and $y$ are evidently odd so let $x-1=2^a q_{x}$ where $y-1=2^b q_{y}$, where $q_{x},q_{y}$ are odd. So: $$2^n+1=(2^a q_{x}+1)(2^a q_{y}+1)$$ $$\implies2^n=2^{a+b}q_{x}q_{y}+2^a q_{x}+2^b q_{y}$$ $$\implies2^{n-a}=2^{b}q_{x}q_{y}+q_{x}+2^{b-a} q_{y}\text{ }(1)$$ In the above, assuming $b>a$. Also: $$xy\geq x$$ $$\implies xy-1\geq x-1$$ $$\implies2^n\geq 2^a q_{x}$$ $$\implies n\geq a$$ Assuming $n>a$, $2^{n-a}$ must be even, and $q_{x}$ is odd so $2^{b-a}q_{y}$ must be odd too so $b=a$. Also, $n\neq a$ because the sum on the right of (1) cannot equate to $1$.

Q.E.D.

NOTE: This is not a homework problem.

• You didn't explicitly consider the case $\,a \ge n.\,$ Also you need to state how those lists of equations are related, e.g. by $\iff$ or by $\Rightarrow\,$? Without such, it is difficult to judge correctness since it is not clear precisely what is intended. – Bill Dubuque Jul 4 '16 at 18:53
• @BillDubuque : I've shown it from the $xy\geq x$ line onwards. I'll edit it accordingly, sorry. – Prish Chakraborty Jul 4 '16 at 18:56
• That's a bit clearer. But once you know that $\,2^a\mid 2^n\,$ then it is trivial since then $\,{\rm mod}\ 2^a\!:\ xy\equiv 1+2^n\equiv 1,\,$ i.e. $\,xy\equiv 1\$ so $\ x\equiv 1\!\iff\! y\equiv 1\ \$ – Bill Dubuque Jul 4 '16 at 19:21
• @BillDubuque : The method you have mentioned is indeed much cleaner, but I'm not familiar enough with modulo to think of using them right away. – Prish Chakraborty Jul 4 '16 at 19:28
• I expanded the Remark in my answer to show how to do the same without congruences. You should learn congruences asap since they greatly simplify many problems in number theory. – Bill Dubuque Jul 4 '16 at 19:45

Hint $\$ After your deduction that $\,a\le n\,$ we know $\,2^a\mid \color{#c00}{2^n}\,$ therefore

$\qquad\ \ {\rm mod}\ \color{}{2^a}\!:\,\ xy\equiv 1\!+\color{#c00}{2^n}\equiv 1\!+\color{#c00}0,\$ i.e. $\ xy\equiv 1\$ so $\ x\equiv 1\iff y\equiv 1\ \ \$ QED

Remark $\$ If congruences are unfamiliar we can eliminate them as below.

$\ \ \begin{eqnarray}\\[-1em] 2^n = xy\!-\!1 = \smash[t]{(\overbrace{x\!-\!1}^{\large b})(\overbrace{y\!-\!1}^{\large c})} + x\!-\!1 + y\!-\!1\, =\, bc+b+c\end{eqnarray}$

therefore $\ 2^a\!\mid 2^n\!= bc+b+c\$ implies $\ 2^a\mid b\!\iff\! 2^a\mid c\ \ \$ QED

• Thank you for the response, but is my solution correct? – Prish Chakraborty Jul 4 '16 at 18:38

Note that in order $2^a$ to divide $x-1$ we must have $a \le n$. Now assume $x\equiv 1 \pmod{2^a}$. Then taking the equation modulo $2^a$ we have $y \equiv 1 \pmod{2^a}$, therefore $2^a \mid y-1$.

Similarly you can prove the other side of the equivalence.

In your solution, you want to say that $x$ and $y$ are evidently odd, but that's just a slip.

Your idea is good, but not carried on correctly.

What you have to prove is that, if $2^a$ divides $x-1$, then $2^a$ divides $y-1$. By symmetry, you also have the other implication.

Assume $x-1=2^aq$ for some $q$ (not necessarily odd) and $y-1=2^br$ (with $r$ odd). You have to prove that $a\le b$.

Now $2^n+1=(2^aq+1)(2^br+1)$, so $$2^n=2^{a+b}qr+2^aq+2^br$$ If $b<a$, then you can collect $2^b$ on the right-hand side and get $$2^{n-b}=2^aqr+2^{a-b}q+r$$ which is odd. A contradiction, because the right-hand side is $\ge3$ so $n-b>0$ and the left-hand side is even.

• Sorry about the odd-even typo and thank you for the help – Prish Chakraborty Jul 4 '16 at 20:57