show $2^{2^n} + 1 \equiv 2 \pmod{2^{2^m} + 1} $ with $0<m<n$

Question

This is given as the very first part of an explanation to a "Basics" question in Concrete Mathematics - it's not even the answer to the question, just the preamble to the answer. So I'd expect there to be something very obvious about the two operands to mod that I just do not see.

I've seen some variants to the question here and elsewhere, but they too assume that this particular relationship is clear.

Thanks in advance...

(this actually is not my "homework", but I can imagine it is someone's homework - hope it's OK to tag as such)

Answer 1

$2^{2^n} + 1 = (2^{2^{m}})^{2^{n-m}} + 1 \equiv (-1)^{2^{n-m}} + 1 = 1 + 1 = 2 \mod (2^{2^m} + 1)$.

Answer 2

The following generalization is true as well. $$a^{2^n}+1 \equiv 2 \bmod \left(a^{2^m}+1 \right)$$ for all $n > m$.

Let $A_n = a^{2^n}+1$. Then note that $a^{2^n}-1 = \left(\left(a^{2^m} \right) ^ 2 \right)^{2^{n-m-1}}-1.$

Hence, we get that $\left(a^{2^m} \right)^ 2 - 1 \vert a^{2^n}-1$. This is because $(x-1)$ is a factor of $x^k - 1$.

Hence, we get that $a^{2^m} + 1 \vert a^{2^n} - 1$. This means that $$a^{2^n}-1 \equiv 0 \bmod \left(a^{2^m}+1 \right)$$

Hence, $$a^{2^n}+1 \equiv 2 \bmod \left(a^{2^m}+1 \right)$$

Answer 3

Hint $\ $ Put $\rm\: A = 2,\ F(N) = 2^N\:$ in the generalization below (which is simpler to prove).

If $\rm\: M\!<\!N\Rightarrow F(M)\:|\:F(N)$ evenly, i.e. $\rm\:F(N) = 2\:\!K\:F(M),\:$ for $\rm\: K = K_{M,N}\in \mathbb Z,\:$ then

$\rm\ mod\:\ A^{F(M)}\!+1\!:\ \ A^{F(M)}\equiv -1\:\Rightarrow\: A^{F(N)} = (A^{F(M)})^{2K} \equiv (-1)^{2K} \equiv 1\:\Rightarrow\:\! A^{F(N)}\!+1\equiv 2 $

Remark $\ $ The proof generalizes and simplifies by abstracting out the essential property required of the exponent sequence (that successors in the sequence are even multiples of predecessors). Frequently this happens, so it it always a good idea to spend some time seeking the optimal level of generality before diving head-first into a proof.