# Property of $2^n+1=xy$

I was wondering if the following were true. It makes sense but I'm having trouble concocting any formal reasoning.

Let $2^n+1=xy$ for some integers $x,y>1$ and $n>0$. For $a\in\mathbb{Z}^+$, does $2^a\mid (x-1)$ $\iff$ $2^a\mid (y-1)$?

Without loss of generality, one only needs to prove one direction. However, I'm not sure how to approach the problem. Here's my attempt: Suppose $2^a\mid (x-1)$. Then $x\equiv 1$ mod $2^a$, so $$y\equiv xy=2^n+1\equiv 2^r+1 \hspace{5mm}(\text{mod }2^a),\hspace{5mm}\text{ where 0\leq r<a}.$$ I'm having trouble continuing from here, since I don't know any extra information to determine $2^r\equiv 0$ mod $2^a$. It doesn't seem like that could be true for arbitrary $a\in\mathbb{Z}$, so I must have veered horribly off-track. I appreciate any help!

-
What does 2^a|(x-1) means if a < 0 e.g. a=-1? – boxdot Jun 26 '12 at 10:25
@finite: I doubt this was considered by OP, but $x\equiv1\bmod 2^a$ would make sense for $a<0$ by considering the quotient ring $\Bbb Z/2^a\Bbb Z$ (just the same as when $a\ge0$). Of course then it would be true for all integers. – anon Jun 26 '12 at 10:45
Ah, sorry, that was a typo. I meant $a\in\mathbb{Z}^+.$ – Dustin Tran Jun 26 '12 at 11:18

• If $a\le n$ and $xy=2^n+1$, then $x\equiv1$ implies $$\begin{array}{c l} y & \equiv yx \\ & \equiv 2^n+1 \\ & \equiv 2^{n-a}(2^a)+1 \\ & \equiv2^{n-a}(0)+1 \\ & \equiv 1 & \mod 2^a \end{array}$$ and hence $2^a\mid(x-1)\implies 2^a\mid(y-1)$. The reverse implication holds by symmetry (simply interchange the roles of $x$ and $y$), so this is in fact a material equivalence.
• If $a>n$ and $xy=2^n+1$, then $2^a>2^n= xy-1> x-1$ and hence $2^a\mid(x-1)$, which means $x=1$, in which case $y\equiv2^n+1\equiv 1\bmod 2^a\iff 2^n\mid 2^a$, and hence is true.
-
Thanks a bunch. I have a quick question: How do you know that $2^n+1\equiv 1\bmod 2^a\iff 2^n\mid 2^a$? – Dustin Tran Jun 26 '12 at 12:06
@Riem: by subtracting $1$: $$2^n+1\equiv 1 \iff 2^n\equiv 0\iff 2^n\mid 2^a.$$ – anon Jun 26 '12 at 12:09
Oh, well that was a rather dumb question haha. Sorry, I was a bit boggled down trying to organize all the iffs and implications in the right succeeding order. – Dustin Tran Jun 26 '12 at 12:17
Sorry, I seem to be missing some connecting step. We have $$2^a\mid (x-1)\iff x=1\iff y=2^n+1$$ and $$2^n+1\equiv 1\mod 2^a\iff 2^n\mid 2^a.$$ So what's the connecting step? – Dustin Tran Jun 26 '12 at 12:26
Ah, okay, I think I understand now. With the conditions that $x,y>1$, it is vacuously true for the cases $a>n$, since neither of the two conditions $2^a\mid(x-1)$ and $2^a\mid(y-1)$ is ever satisfied without breaking $x,y>1$. I also figured out the problem I had connecting your logic previously. It was at the point where you stated $$2^n\equiv 0\iff 2^n\mid 2^a.$$ It should be $$2^n\equiv 0\iff 2^a\mid 2^n,$$ because we're doing it over $\mod 2^a$ (that is, $a\equiv b\mod m\iff m\mid(b-a)$). And what confused me previously is the fact that $2^a>2^n$, which is contradictory. – Dustin Tran Jun 26 '12 at 13:17

I'll assume $a \ge 1$ and $2^a \mid (x-1)$.

$2^n$ is zero mod $2^a$. This is because $a < n$: if not, you would have $2^n \mid 2^a$, so $2^n \mid (x-1)$. In particular, $2^n \le x-1$, which can't hold, as $2^n = xy - 1 > x - 1$.

Therefore, your argument gives $y = 2^n + 1 = 1 \mod 2^a$.

-
I made the mistake of assuming $2^n=2^{ka+r}=2^{ka}\cdot2^r\equiv 1\cdot 2^r\mod 2^a$. That is, I accidentally did $\mod a$ on the exponents. – Dustin Tran Jun 26 '12 at 11:49

You should have $2^n\equiv 0$ mod $2^a$ instead of $2^n\equiv 2^r$ mod $2^a$

-

Let $x=2^ac+1\ and\ y=2^bd+1$ where c,d are odd natural numbers and a≥b>0. So, $(2^n+1)=xy=(2^ac+1)(2^bd+1)$ =>$(2^n+1)=xy=(2^{a+b}cd+ 2^ac+ 2^bd +1)$ =>$2^n=(2^{a+b}cd+ 2^ac+ 2^bd)$ =>$2^{n-b}=(2^acd+ 2^{a-b}c+ d)$. =>d=$2^{n-b}-2^acd+ 2^{a-b}c\$ will be even unless a=b. So, if $(2^n+1)$ has a factor of the form $2^ac+1$, the other must be of the form $(2^bd+1)$ where c,d are odd natural numbers.

-

Hint $\$ Case $\rm\, 1\!:\ \, 2^a\mid 2^n,\, \ so\ \ mod\ 2^a\!:\,\ xy \equiv 1+2^n\equiv 1,\$ so $\rm\,\ x\equiv 1\iff y\equiv 1.\$

Case $\rm\,2\!:\ \ 2^n\mid 2^a,\,$ so $\rm\:xy\!-\!1 = 2^n\mid 2^a\mid x\!-\!1\:\Rightarrow\:y=1\Rightarrow\Leftarrow\,$ (by $\rm\:xy\!-\!1 > x\!-\!1\:$ for $\rm\:y>1).$

-