1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jul 4 '16 at 18:53
  • $\begingroup$ @BillDubuque : I've shown it from the $xy\geq x$ line onwards. I'll edit it accordingly, sorry. $\endgroup$ – Prish Chakraborty Jul 4 '16 at 18:56
  • $\begingroup$ 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\ \ $ $\endgroup$ – Bill Dubuque Jul 4 '16 at 19:21
  • $\begingroup$ @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. $\endgroup$ – Prish Chakraborty Jul 4 '16 at 19:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Jul 4 '16 at 19:45
2
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.