Show that if $ \ m>n \ $ then $ \ 2^{2^{ \large n}} +1 \ $ divides $ \ 2^{2^{\large m}}-1 \ $

Question

Show that if $ \ m>n \ $ then $ \ 2^{2^{ \large n}} +1 \ $ divides $ \ 2^{2^{\large m}}-1 \ $.

Also show that $\, \gcd(2^{2^{\large n}}+1,2^{2^{\large m}}+1)=1$

Answer:

Since $ \ m>n \ $ , we have $ \ m=n+p \ $, where $\ p \in \mathbb{N} $

Thus,

$ 2^{2^m}-1 \\ = 2^{2^{n+p}}-1 \\ = \left(\left(2^{2^n} \right)^{2^{p-1}} \right)^2-1 \\ = \left( \left(2^{2^n} \right)^{2^{p-1}}-1 \right) \left( \left(2^{2^n} \right)^{2^{p-1}} +1 \right) \\ = \left( 2^{2^n}-1 \right) {\color{Blue} {\left(2^{2^n}+1 \right)}} ........... \left( \left(2^{2^n} \right)^{2^{p-1}} +1 \right) \ \ (Decomposing \ \ the \ \ first \ \ term) \ $

Thus from the last line we can see that $ \ 2^{2^n}+1 \ $ divides $ \ 2^{2^m}-1 \ $.

Kindly check my calculation.

Next part,

Since $ \ 2^{2^n}+1 \ $ divides $ \ 2^{2^m}-1 \ $ , we conclude

$ 2^{2^n}+1 \ $ does not divide $ \ 2^{2^m}+1 \ $.

Hence we have

$\gcd(2^{2^{ \large n}} +1, 2^{2^{ \large m}} +1)=1 \ $

Please check my calculation in both parts and confirm my work.

Answer 1

The first proof is correct, but somewhat long-winded. The second proof is incorrect : just because $2^{2^n} + 1$ does not divide $2^{2^m} + 1$, does not mean that their $\gcd$ is $1$. For example, $4$ does not divide $6$, but their $\gcd$ is $2$.

---

To show the first one elegantly, proceed by induction : fix $n$, and start induction with $m = n+1$. The base case is $2^{2^{n+1}} -1 = (2^{2^n} + 1)(2^{2^n} - 1)$, so we are done.

Also, if it works for $m > n$, then $2^{2^{m+1}} - 1 = (2^{2^m} - 1)(2^{2^m} + 1)$. Since $2^{2^m} + 1$ is a multiple of $2^{2^n} + 1$, therefore so is $2^{2^{m+1}}+1$, and we are done without writing more than a simple difference of squares.

For the second part, note that $2^{2^{m}} +1 = k(2^{2^n} + 1) + 2$, where $k = \frac{2^{2^m} - 1}{2^{2^n} + 1}$. So if $d$ is a common factor of $2^{2^m} + 1$ and $2^{2^n} + 1$, then $d$ is a factor of $2$ from the given equation. But $d \neq 2$ since both the given numbers are odd. Hence, $d = 1$ is forced.

Answer 2

Notice: $(k + 1)(k^{2a - 1} - k^{2a - 2} + ...... + k - 1) = k^{2a} -1$.

So $k+1|k^b - 1$ if $b=2a$ is even.

So if $m > n$ then $2^{2^n} + 1$ will divide $2^{2^m} -1 = 2^{2^n2^{m-n}}- 1 = (2^{2^n})^{2^{m-n}} - 1$ if $2^{m-n}$ is even. Which, as $m - n \ge 1$, it is.

Second part:

$2^{2^m} + 1 = (2^{2^m} - 1) + 2=(2^{2^n} +1)*k + 2$ for some integer $k$. So any common factor of $2^{2^n}-1$ and $(2^{2^n} +1)*k + 2$, will have to be a factor of $2$ as well. But as $2^{2^n} +1$ and $2^{2^m} + 1$ are odd, that means the the gcd is $1$.