Vtyjkyuk

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

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

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 = frac2^2^m - 12^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.

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