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.

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

share|improve this question
1  
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

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
@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
    
@milcak: I'm stuck. Please help :( –  Chan Feb 11 '11 at 6:15
    
@Chan added hint! –  milcak Feb 11 '11 at 10:15
1  
@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.

share|improve this answer
    
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!

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.