How to prove that all odd powers of two add one are multiples of three 
For example
  \begin{align} 
2^5 + 1 &= 33\\
2^{11} + 1 &= 2049\ \text{(dividing by $3$ gives $683$)}
\end{align}

I know that $2^{61}- 1$ is a prime number, but how do I prove that $2^{61}+1$ is a multiple of three?
 A: A direct alternative to the answer via congruences is to note that for $k$ odd one has the well-known polynomial identity
$$
x^{k} + 1 = (x + 1) (x^{k-1} - x^{k-2} + \dots - x + 1),
$$
and then substitute $x = 2$.
A: In binary:
\begin{align*}
11 &= 11 \cdot 01 \\
1111 &= 11 \cdot 0101 \\
111111 &= 11 \cdot 010101 \\
11111111 &= 11 \cdot 01010101 \\
1111111111 &= 11 \cdot 0101010101 \\
&~~\vdots
\end{align*}
Clearly the LHS are of the form $2^{2k}-1$. And we've proved that these are multiples of three by factoring out $11$ in binary! Thus if we double and add three, $$2 \cdot (2^{2k}-1)+3=2^{2k+1}+1$$ is also a multiple of three.
A: $2^2=4\equiv1\pmod 3$, so $4^k\equiv1\pmod3$ for all integers $k$.  And so for any odd number $2k+1$, we get $2^{2k+1}+1 = 4^k\cdot 2+1\equiv 2+1\equiv0\pmod3$.
A: Using geometric series
Consider $S_k = 1 + 2\sum_{i=0}^{k-1}4^i$. It follows that $S_k$ is in $\mathbb{N}^{+}$. However,
$$S_k = 1 + 2\cdot\frac{4^k - 1}{4 - 1} = \frac{2^{2k+1}+1}{3}$$
QED
Using recurrence
For $k\in\mathbb{N}$, consider the recurrence $J_{k+1} = 4J_{k} - 1$, with $J_0 = 1$.
Since $J_0 = 1$, it follows that each of $J_k$ is in $\mathbb{N}^{+}$.
Solving the recurrence yields: $J_k = \frac{1}{3}(2^{2k + 1}+ 1)$.

 The characteristic equation $r^2 - 5r + 4 = 0$ follows from $J_{k+2} = 5J_{k+1} - 4J_{k}$. Hence, $J_k = A\lambda_1^k + B\lambda_2^k$, with $\lambda_1 = 4$ and $\lambda_2 = 1$ as solutions to the characteristic equation.  As $J_0 = 1 \implies J_1 = 3$, it follows that $A = \frac{2}{3}$ and $B = \frac{1}{3}$.

QED
A: If $k$ is odd, then $2^k$ is $2*2^{k-1}$. If $n$ is not a multiple of 3 then $n^2-1$ is since $n^2-1 = (n-1)(n+1)$ and at least one of them is a multiple of 3. This means that $2*2^{k-1} - 2$ is a multiple of $3$ as is $2*2^{k-1} + 1$.
Hope I helped.
A: Another way is by induction:
$$
2^1+1 = 3 = 3 \cdot 1
$$
Then, if $2^k+1 = 3j, j \in \mathbb{N}$, then
\begin{align}
2^{k+2}+1 & = 4\cdot2^k+1 \\
          & = 4(2^k+1)-3 \\
          & = 4(3j)-3 \qquad \leftarrow \text{uses induction hypothesis} \\
          & = 3(4j-1)
\end{align}
A: One of your examples is that $2^{11} + 1$ is divisible by $3$. We investigate as follows:
Let us consider instead raising $2$ to an even power and subtracting $1$. And then let us factor.
Example: $2^{10} - 1 = (2^5 - 1)(2^5 + 1)$.
Among any three consecutive integers, exactly one of them must be divisible by $3$.
Clearly $2^5$ is not divisible by $3$, so either its predecessor or successor is divisible by $3$.
That is, either $2^5 - 1$ or $2^5 + 1$ is divisible by $3$, whence their product is, as well.
Okay: Their product is $2^{10} - 1$, which we have now established is divisible by $3$.
This number is still divisible by $3$ after being doubled, and still divisible by $3$ when we add $3$ to it. 
So: We have that $2(2^{10} - 1) + 3 = 2^{11} - 2 + 3 = 2^{11} + 1$ is divisible by $3$ as desired.
A similar bit of reasoning around $2^{2k} - 1$ yields the assertion at hand. "QED"
A: Since $2 \equiv -1 \pmod{3}$, therefore $2^{k} \equiv (-1)^k \pmod{3}$. When $k$ is odd this becomes $2^k \equiv -1 \pmod{3}$. Thus $2^k+1 \equiv 0 \pmod{3}$.
A: There are only three possibilities for the divisibility of an integer by $3$, which are: no remainder, a remainder of $1$, or a remainder of $2$. But if we multiply $2$ by itself over and over again, the no remainder option is impossible, as that would mean that $2$ is a multiple of $3$, which it is not.
The thing is also that we can multiply reminders. So $2$ leaves a remainder of $2$, and $2 \times 2 = 4$, which leaves a remainder of $1$. And $1 \times 2 = 2$, which leaves a remainder of $2$ again.
Therefore the powers of $2$ alternate remainders on division by $3$ according to the parity of the exponent: $2^n \equiv 1 \pmod 3$ if $n$ is even and $2^n \equiv 2$ or $-1 \pmod 3$ if $n$ is odd.
A: $2 = 3-1$
$2^k = (3 - 1)^k = 3^k - k*3^{k - 1} ..... = \sum_{n = 0}^k {k \choose n}3^{k - n}(-1)^n = \sum_{n = 0}^{k - 1} {k \choose n}3^{k - n}(-1)^n + {k \choose 3}3^{k - n}(-1)^k = \sum_{n = 0}^{k - 1} {k \choose n}3^{k - n}(-1)^n \pm 1$
Since $k$ is odd:
$2^k = \sum_{n = 0}^{k - 1} {k \choose n}3^{k - n}(-1)^n - 1$
$2^k + 1 = \sum_{n = 0}^{k - 1} {k \choose n}3^{k - n}(-1)^n = 3\sum_{n = 0}^{k - 1} {k \choose n}3^{k - n - 1}(-1)^n$
which is a multiple of 3.
A: There is exactly one integer that divides three among any three consecutive integers. Since $2^{61}-1$ is prime, $2^{61}$ trivially is not a multiple of $3$, $2^{61}+1$ is a multiple of $3$. 
