# 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

-
Hint: there is a special identity for $x^{2n+1}+1$ that you can use. – Raskolnikov Feb 9 '11 at 10:15
@Raskolnikov: Many thanks ;) – Chan Feb 9 '11 at 10:16

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.

-
@milcak: Thanks ;) – Chan Feb 9 '11 at 20:30
@milcak: I tried to factor out, but still don't get it. Could you give me one more tiny hint ^_^! – Chan Feb 10 '11 at 7:25
@Chan added hint! – milcak Feb 11 '11 at 10:15
@milcak: I finally finished the proof using your method. I had to use concrete example to understand each step but it was such a great experiment. Once again, thank you very much for all your help. I was so happy that I could not sleep last night :P! I will prove it again when I get into congrugence theorem. – Chan Feb 15 '11 at 0:04

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.

-
Thanks a lot but I don't understand the triple notation above. Would you mind adding a brief explanation? – Chan Feb 9 '11 at 20:31
@Chan: If you're studying elementary number theory and you haven't yet encountered modular arithmetic then you probably will shortly. When you do I recommend that you revisit this problem. – Bill Dubuque Feb 9 '11 at 20:39
Thanks! I will be there soon ;) – Chan Feb 10 '11 at 7:22

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!

-