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.

$3^k \not\equiv -1 \pmod {2^e}$ for $e > 2, k > 0$. Is this true? I have tried to prove it by expanding $(1 + 2)^k$. [Notation: $(n; m) := n! / (m! (n - m)!)$] E.g., for $e = 3$ I get: $(1+2)^k + 1 = 2 + (k; 1) 2 + (k; 2) 2^2 + (k; e) 2^e + ...$ So, here it's enough to prove that $2^3$ does not divide $2 + (k; 1) 2 + (k; 2) 2^2$. The validity for general e seems very hard to prove.

share|improve this question
    
In case you're interested, the TeX-syntax for the binomial coefficient ${n\choose m}$ is {n \choose m}. –  Jyrki Lahtonen Apr 12 '12 at 9:30
add comment

4 Answers

up vote 3 down vote accepted

Hint :

It is sufficient to show that :

$ 8 \nmid 3^k+1$

share|improve this answer
add comment

Based on pedja,we only prove that $8 \nmid 3^k+1$,

1.when $k=2m+1$,$3^k+1=3^{2m+1}+1=9^m \times 3+1 \equiv 4 \pmod{8} $

2.when $k=2m$,$3^k+1=3^{2m}+1=9^m+1 \equiv 2 \pmod{8} $ so we have $8 \nmid 3^k+1$,this is $3^k \not\equiv -1 \pmod {2^e}$

share|improve this answer
add comment

Just a bit more explanative in case the other answers are too compressed.
We do this by induction. The remarkable property, that $\small 3^2=9=8+1$ suggests, to try this modulo 8 (but that could as well be suggested by the problem and it was asked that the factor $\small 2^e $ with $\small e=2 $ should not be exceeded)

  1. we observe for the first even exponent
    $\small 3^2+1 = 10 = (8 \cdot 1 + 1) +1 $

  2. we try the general ansatz
    $\small 3^k+1 = (8 m_0 + 1) +1 $
    then
    $\small \begin{eqnarray} 3^{k+2}+1 &=& \\ 9 \cdot 3^k+1 &=& (8+1)(8 m_0 + 1) +1 \\ &=& 8 (8 m_0+1) + (8 m_0 + 1) +1 \\ &=& 8 (9 m_0+1) + 1 +1 \\ &=& (8 m_1+1)+1 \end{eqnarray}$
    and see, that the structure persists when we increase the exponent by 2. Because that structure is true for exponent k+2 when it is true for k, and we know, that it is true for k=2, we know it is true for all even exponents.

  3. Then we look at the odd exponents and observe for the first one
    $\small 3^1+1 = 4 = (8 \cdot 0+3)+1 $

  4. we do the general ansatz
    $\small 3^k+1 = (8m+3)+1 $
    and then
    $\small \begin{eqnarray} 9 \cdot 3^k+1 &=& (8+1)(8m_0+3)+1 \\ &=& 8(8m_0+3)+1 \cdot 8m_0+1 \cdot 3+1 \\ &=& 8(9m_0+3)+4 \\ &=& (8m_1+3)+1 \end{eqnarray} $

In 2) and 4) we conclude, that we have for even exponents k $\small 3^k \equiv 1 \pmod 8$ and for odd exponents $\small 3^k \equiv 3 \pmod 8$ and thus $\small 3^k \equiv -1 \pmod 4$ or $\small 3^k \equiv -1 \pmod 2$ but not $\small \pmod 8$

share|improve this answer
add comment

Hint $\ $ Put $\rm\:m= 8,\ a = 3\:$ in

$$\rm mod\ m\!:\ a^2\equiv 1\ \Rightarrow\ a^n \in \{a, 1\}\ \ so\ \ a^k\equiv -1\ \Rightarrow\ a\equiv -1\ \ or\ \ 1\equiv -1\ (\!\!\iff\!\! m=2\ or\ 1) $$

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