Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
What does 2^a|(x-1) means if a < 0 e.g. a=-1? –  finite 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}^+.$ –  Riem Jun 26 '12 at 11:18
add comment

5 Answers

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|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$? –  Riem 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. –  Riem 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? –  Riem Jun 26 '12 at 12:26
1  
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. –  Riem Jun 26 '12 at 13:17
show 1 more comment

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|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. –  Riem Jun 26 '12 at 11:49
add comment

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

share|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.