# $3^k$ not congruent to $-1 \pmod {2^e}, e > 2$.

$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.

-
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

Hint :

It is sufficient to show that :

$8 \nmid 3^k+1$

-

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}$

-

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$

-

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)$$

-