5
$\begingroup$

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 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!

  • 0
    Ah, sorry, that was a typo. I meant $a\in\mathbb{Z}^+.$2012-06-26

5 Answers 5

0

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

6

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

  • 0
    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.2012-06-26
6
  • 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.
  • 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.2012-06-26
2

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

0

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.