3
$\begingroup$

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

3 Answers 3

3

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.

  • 0
    @milcak: I tried to factor out, but still don't get it. Could you give me one more tiny hint ^_^!2011-02-10
  • 0
    @Chan added hint!2011-02-11
  • 0
    @milcak: Thank you very much for your hint. However, I was surprised at the way you approach the problem. How did you come up with the idea a, b? plus to show that $$2^{k}+1|(2^{k(2n−1)}+1)$$. What special about $$2^{k(2n-1)}$$ which makes you try to prove it first? I like to have the answer, but more important I want to learn how to approach the problem. Your method was totally beyond what I know, is there a name for this particular method, or just use common sense. And can I prove it by induction on `n`?2011-02-11
  • 0
    @Chan I added the $a,b$ just to make it visually clearer. Once you learn modular arithmetic, you'll see that $a \equiv 0 (\mod{2^k+1})$, so you won't have to write it anymore. What's special about $2^{k(2n-1)}$? It's smaller then $2^{k(2n+1)}$! By induction, I mean that you can repeat this whole computation $n$ times, then in the exponents you will get $k(2n+1), k(2n-1), k(2n-3),\cdots, k(2n-2n+3), k(2n-2n+1)=k$. At the end, you will be left with $2n$ expression that are divisible by $2^{k}+1$, and your final $2^{k}+1$. This way all will be divisible by $2^{k}+1$ as needed.2011-02-12
  • 0
    @Chan and I think this is the easiest method (but most complicated). With modular arithmetic $+$ Bill's hint below, you can solve the problem much faster - in fact it is a two line proof this way.2011-02-12
  • 0
    @milcak: I'm lost again! It was much harder that I thought :(. I understand your hints but I still can prove it myself. I'm so confused now. Sorry, I wish I could be a bit smarter.2011-02-13
  • 0
    @Chan read the wikipedia article on modular arithmetic, then look at Bill's hint. You'll be surprised how easy it is!2011-02-13
  • 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.2011-02-15
3

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.

  • 0
    Thanks a lot but I don't understand the triple notation above. Would you mind adding a brief explanation?2011-02-09
  • 0
    @Chan: If you're studying elementary number theory and you haven't yet encountered [modular arithmetic](http://en.wikipedia.org/wiki/Modular_arithmetic) then you probably will shortly. When you do I recommend that you revisit this problem.2011-02-09
0

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!