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.

In this (btw, nice) answer to Twin primes of form $2^n+3$ and $2^n+5$, it was said that:

If $n\equiv 2\pmod 3$, then $7\mid 2^n+3$?

I'm not familiar with these kind of calculations, so I'd like to see, if my answer is correct:

  1. Let $n=3k+2$ so then $2^{3k+2}+3\equiv 2^{3k+2}-4 \equiv 4\left(2^{3k}-1\right)\equiv \phantom{4\cdot } 0 \pmod 7$.

  2. Reading a bit about Modular arithmetics, I found that $ a_1 \equiv b_1 \pmod N $ and $ a_2 \equiv b_2 \pmod N $ then $ a_1 a_2 \equiv b_1 b_2 \pmod n$, if $a_i$ and $b_i$ are integers.

  3. Since we have $4\equiv 4 \pmod 7$, I conclude that $2^{3k}-1 \equiv 0 \pmod 7$.

  4. Finally we use that $ 2^{3n}-1=(2^3-1)\cdot \left(1+2^3+2^{2\cdot 3}+2^{3\cdot 3}+\cdots+2^{(k-1)3}\right) $ and are done.

Are there alternative ways to prove it?

share|improve this question
    
step 3 is not quite right. To cancel 4 you want to multiply it by its inverse mod 7, which is 2. so the step 3 should be modified as: Since $2\equiv 2$ ... –  Keivan May 22 '12 at 21:39
    
@Keivan I don't see the difference to Brian's answer? –  draks ... May 22 '12 at 21:44
    
If I just had seen this before... –  draks ... May 22 '12 at 21:58
add comment

3 Answers

up vote 2 down vote accepted

In fact, we can prove a stronger result and the proof is easier. The result we will prove is that $$x^2+x+1 \text{ divides }x^{3k+2} + x+1$$ for all $k \in \mathbb{N}$. Setting $x=2$ gives the result, you are looking for.

The proof follows immediately from the remainder theorem since $(x^2+x+1) = (x-\omega)(x-\omega^2)$, where $\omega$ is the complex cube-root of unity.

(Remember that $(x-a)$ divides $f(x)$ if and only if $f(x) = 0$)

Plugging in $\omega$ in $x^{3k+2}+x+1$ gives us $\omega^{3k+2} + \omega + 1 = \omega^2 + \omega + 1 = 0$. This gives us that $(x- \omega)$ divides $x^{3k+2}+x+1$.

Similarly, plugging in $\omega^2$ in $x^{3k+2}+x+1$ gives us $\omega^{6k+4} + \omega^2 + 1 = \omega + \omega^2 + 1 = 0$. This gives us that $(x- \omega^2)$ divides $x^{3k+2}+x+1$.

Hence, $(x-\omega)(x-\omega^2) = x^2 + x + 1$ divides $x^{3k+2}+x+1$.

Setting $x=2$ gives us the result you want i.e. $2^2 + 2 + 1 = 7$ divides $2^{3k+2}+2+1 = 2^{3k+2}+3$.

EDIT (Deleted the other answer and merged with this)

Another way to prove $x^2+x+1 \text{ divides }x^{3k+2} + x+1$ for all $k \in \mathbb{N}$ is by induction. All that is needed for induction is that $$x^{3k+5} + x + 1 = x^3 \left(x^{3k+2} + x + 1\right) - x^4 - x^3 +x + 1\\ = x^3 \left(x^{3k+2} + x + 1\right) - x^3 (x+1) +x + 1\\ = x^3 \left(x^{3k+2} + x + 1\right) - (x^3-1) (x+1)$$

So if $x^2 + x +1$ divides $\left(x^{3k+2} + x + 1\right)$, then it also divides $x^{3k+5} + x + 1$ since $x^2 + x +1$ divides $x^3-1$. Also, the base case $k=0$ is trivially true since $x^2 + x + 1$ divides $x^{3 \times 0 + 2} + x + 1 = x^{2} + x + 1$.

Hence, $x^2 + x + 1$ divides $x^{3k+5} + x + 1$ forall $k \in \mathbb{N}$. Setting $x=2$ as before gives you what you want.

share|improve this answer
    
Wow, this is a great answer! –  draks ... May 23 '12 at 6:17
add comment

$$\begin{align*} 2^{3k+2}+3&\equiv 2^{3k+2}-4\\ &\equiv 4\left(2^{3k}-1\right)\\ &\equiv 4\left((2^3)^k-1\right)\\ &\equiv 4\left(1^k-1\right)\\ &\equiv 4\cdot0\\ &\equiv 0 \pmod 7\;, \end{align*}$$

since $8\equiv1\pmod7$.

share|improve this answer
    
Cool, thanks for the short cut. –  draks ... May 22 '12 at 21:33
add comment

It doesn't require factorization or any other such ingenuity, just simple modular arithmetic:

$$\rm mod\ 7\!:\ \ 3 + 2^{\:\!2+3\:\!K} = 3 + 4\cdot 8^K \equiv 3 + 4\cdot 1^K\equiv 3+4 \equiv 0$$

share|improve this answer
1  
The OP also asks for other ways to prove it. –  user17762 May 23 '12 at 2:06
    
@Marvis My remark refers to the factorization used by the OP, not others. –  Bill Dubuque May 23 '12 at 2:23
add comment

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.