Exercise 1.2.52* (Divisors of $2^n +1$)

Question

Suppose that $2^n +1 = xy$, where $x$ and $y$ are integers $>1$ and $n>0$. Show that $2^a \mid (x-1)$ if and only if $2^a \mid (y-1)$.

Richard Ganaye · Accepted Answer

\begin{proof} Assume that $2^a\mid x-1$. Since $x>1$, $x-1
e 0$, so $2^a \leq x-1 < x < 2^n +1$, therefore $2^a \leq 2^n$, so $a \leq n$.

Since $a \leq n$, and $xy \equiv 1 \pmod {2^n}$, then $xy \equiv 1 \pmod {2^a}$. Moreover $x \equiv 1 \pmod {2^a}$, therefore $y \equiv 1 \pmod {2^a}$. This shows that $2^a \mid y-1$.

Exchanging the role of $x$ and $y$, we prove similarly $2^a \mid y-1 \Rightarrow 2^a \mid x-1$.

We have proved that  $2^a \mid x-1$ if and only if $2^a \mid y-1$.

\end{proof}

Exercise 1.2.52* (Divisors of $2^n +1$)

Answers

Comments

Exercise 1.2.52* (Divisors of $2^n +1$)

Answers

Comments

Add answer