Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 6 down vote accepted
  • 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.
share|cite|improve this answer
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$.

share|cite|improve this answer
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$

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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