Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.