How to prove that all odd powers of two add one are multiples of three

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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}

Answer 4

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"

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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

Answer 10

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.

Answer 11

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