# 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?

• @AnuragA $2^{61}- 1$ is a prime number, it is $2^{61}+ 1$ that is divisible by three. I apologise if I made a mistake writing the question Jan 19, 2016 at 22:20
• If you know that $2^{61}-1$ is prime, $2^{61}+1$ has to be a multiple of 3, since $(a,a+1,a+2)$ must contain a multiple of 3 and the first two can't be (this doesn't address the general case in the question, so it's a comment not an answer) Jan 20, 2016 at 0:47
• @Glen_b Just for fun, I wrote out an answer using this sort of observation! Jan 20, 2016 at 8:14
• As hinted at in several answers below, this is exactly the kind of thing that modular arithmetic was invented for. While you can present a solution using "elementary" language, without using (or even being aware of) any terminology from modular arithmetic, that's a bit like driving a nail using a large stone instead of a hammer. Sure, either way works, but having the proper tool makes it so much less awkward. Jan 20, 2016 at 13:36
• Jan 20, 2016 at 15:10

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

• Note that this logic also shows that any even power of two, minus one, is a multiple of 3. Jan 20, 2016 at 19:49
• I'm suprised such an easy answer got so many votes. Apr 17, 2016 at 10:18

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

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}

• Wouldn't it be just easier to prove that if a = b mod m then a^k = b^k mod m by induction then immediately use that fact? Jan 20, 2016 at 0:29
• That proof is super trivial if you assume that a = b mod m implies ax = bx mod m, which you do. tldr, this isn't "another way." Jan 20, 2016 at 0:30
• @djechlin: Fair point. I will rewrite to avoid modular arithmetic altogether. Jan 20, 2016 at 4:31
• +1, but I would have said it a little more simply: $2^{k+2}+1=4\cdot2^k+1=3\cdot2^k\,+\,(2^k+1)$, which is a multiple of 3 iff $2^k+1$ is.  You can also use that to prove that adding 1 to any even power of 2 yields a number that is not a multiple of 3. Jan 20, 2016 at 17:20
• This inline notation makes it difficult to see where you've used to hypothesis. Took me way longer to comprehend than it should have for such a simple induction proof Jan 20, 2016 at 20:29

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"

• (Just to fill in the last details: Let $k \in \mathbb{Z}$ be arbitrary. Among the three consecutive integers $2^{k} - 1, 2^{k}, 2^{k} + 1$ must be exactly one divisible by three; since $2^{k}$ is not divisible by three, it must be one of the other two, hence their product is divisible by three. This product is $(2^{k} - 1)(2^{k} + 1) = 2^{2k} - 1$; note that multiplying this number by $2$ and then adding $3$ does not affect its divisibility by three, whence $2(2^{2k} - 1) + 3 = 2^{2k+1} + 1$ is divisible by $3$ as desired. QED) Jan 22, 2016 at 2:08

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.

• Well written for readability by non-mathematicians. Good job. Jan 20, 2016 at 22:31
• Thank you for the acknowledgement. Jan 20, 2016 at 22:32
• A superb answer. Jan 23, 2016 at 12:26

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

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.

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

### 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

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.

• Welcome to MathSE! See this guide for how to mark up math nicely on this site. Jan 20, 2016 at 14:43
• Thanks! Is the explanation ok? Jan 20, 2016 at 14:47
• This looks find. Although it seems basically the same answer as the one posted here. In any case, welcome to the site. Jan 20, 2016 at 15:03
• It's hard for me to follow - matching up the $n^2=1$ bit with half of $2 * 2^{k-1} - 2$ for instance. And it relies on the assumption that $n$ (which is presumably meant to stand for $2^{(k-1)/2}$?) is not a multiple of 3. Jan 20, 2016 at 15:09
• As far as I know 2 is NOT a multiple of 3 ;). I don't say $n^2=1$ anywhere. Jan 20, 2016 at 15: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$.