What special properties does the number of the form $2^k + 1$ have? Prove that $$(2^k + 1)|( 2^{ k( 2n + 1 ) } + 1 )$$  
How can I approach this problem? Using algebra manipulation with the number $$2^{ k( 2n + 1 ) } + 1 $$ (this is what I tried, but failed :( ), or there are some other properties are more useful. Any hint?  
Thanks,
Chan
 A: Hints:


*

*$2n+1$ is odd.

*$2^{k(2n+1)} + 1 = 2^{k(2n+1)} + 1 + 2^{2kn} - 2^{2kn}$

*try to show that $2^k + 1 | (2^{k(2n+1)} + 1)$ if and only if $2^k + 1 | (2^{k(2n-1)} + 1)$

*$\cdots$

*$2^k + 1 | 2^k + 1 $  $\square$
EDIT: 
Hint $2$ to Hint $3$:
$$2^{k(2n+1)} + 1 = 2^{k(2n+1)} + 1 + 2^{2kn} - 2^{2kn} = 2^{2kn+k} + 1 + 2^{2kn} - 2^{2kn} =$$ 
$$=2^{2kn}2^k + 1 + 2^{2kn} - 2^{2kn} = 2^{2kn}(2^k + 1) + 1 - 2^{2kn} =$$
Let $a = 2^{2kn}(2^k + 1)$, now the equality is:
$$= a + 1 - 2^{2kn} = a + 1 - 2^{k(2n-1)+k} = a + 1 - 2^{k(2n-1)}2^k =$$
$$= a + 1 - 2^{k(2n-1)}2^k +2^{k(2n-1)} - 2^{k(2n-1)}= a + 1 - 2^{k(2n-1)}(2^k +1) +2^{k(2n-1)}$$
Now let $b= 2^{k(2n-1)}(2^k +1)$, and you are left with:
$$2^{k(2n+1)} + 1 = (a - b) +( 2^{k(2n-1)} + 1)$$
Note that $a,b$ are divisible by $2^k +1$ to reach Hint $3$ (I read in some other post that you haven't learned modular arithmetic yet - once you do this becomes so so so so much easier!).
Now it smells like induction. Apply Hint $1$ and draw a square.  
A: HINT $\rm\ \ \ 2^K\ \equiv\: -1\ \ \Rightarrow\ \ (2^K)^{\:2N+1}\ \equiv\: -1\ \ \ (mod\ \ 2^K+1)$
Notice how converting the problem from relational form (divisibility) to functional form (equality or congruence) has the effect of greatly simplifying the problem, reducing it to the obvious fact that $-1$ to an odd power is $-1\:$. This is one of the great powers of congruence arithmetic - converting obfuscated divisibility problems into intuitive arithmetical problems. It is essential to master this reduction in order to succeed in elementary number theory.
A: We know that $-1$ is a root of every polynomial of the form $x^{2n+1}+1$. By factor theorem $x+1$ is a factor of $x^{2n+1}+1$. It clearly factorises over $\mathbb Z$
So, $x+1$ divides $x^{2n+1}+1$ for all integers $x$. Putting $x=2^k$ we are done!
