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.

  • 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
    @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!