What is all N that make $2^N + 1$ divisible by 3?

Question

When $N = 1$, $2^N + 1 = 3$ which is divisible by $3$.

When $N = 7$, $2^N + 1 = 129$ which is also divisible by $3$.

But when $N = 2$, $2^N + 1 = 5$ which is not divisible by $3$.

A quick lookout can determine that when $N$ is an odd number, $2^N + 1$ is divisible by $3$. If is that correct, how can it be proven? Otherwise, what is the counterexample and the correct $N$?

Can this be made into a more general form, for example $2^N + C$ or something similar?

Answer 1

When $N = 1 + 2k$;

\begin{align}2^{1+2k} +1 \pmod 3 & \equiv 2(2^{2k})+1 \pmod 3\\ &\equiv 2(4^{k})+1 \pmod 3\\ &\equiv 2+1 \pmod 3\\ &\equiv \pmod 3 \end{align}

When $N = 2k$

$$2^{2k} +1 \pmod 3\equiv 2 \pmod 3$$

Answer 2

You can easily prove by induction on $k$ that $2\times 4^k+1$ is divisible by $3$: It is for $k=1$, and if it is for some $k$, then $$2\times 4^{k+1}+1=2\times 4^k\times 4+1=4(2\times 4^k+1)-3$$ Therefore $2^{2m+1}+1$ is divisible by $3$ for every natural $m$.

Answer 3

If $2^N+1$is divisible by $3$ then in other words $2^N+1$ is a multiple of $3$ . $2^N+1=3k \implies 2^N=3k-1$ so we want $3k-1$ to be even then we want $3k$ to be odd. $3k$ is odd only when $k$ is odd.

Answer 4

Okay, so here's an interesting approach to the matter, in my opinion. It's probably not the best, but it was the first that came to mind since I knew this (relatively?) obscure bit of knowledge.

The mathematical underpinning of this idea, in terms of validity, is tied to modular arithmetic, and is explained a bit at a Stack Overflow post here.

---

Imagine the number $2^N+1$ in binary. Owing to how binary is written and that $1=2^0$, this basically amounts to

$$2^N + 1 = 1\underbrace{000\cdots 000}_{\text{N-1 zeroes}}1$$

In general, if we have a binary number, we can determine if it is divisible by three by the following:

• Count the number of nonzero bits in even position, starting at the right. For the binary number $11101$, this would be $1$: the even positions from the right are the second and fourth, which are $0$ and $1$ respectively. For $1111$, there are two (second and fourth from the right.)

• Do the same for those in the odd positions. For the above pair of examples, the numbers are $3$ and $2$ respectively.

• Call these numbers $E$ and $O$ respectively. If $E-O$ is divisible by three, the original number is too.

For the above examples, $E-O$ is $2$ and $0$ respectively. Thus, $11101$ ($29$) is not divisible by $3$, but $1111$ ($15$) is.

In the case of $2^N+1$, our binary number is $N+1$ digits long, and only has nonzero bits at positions $N$ and $1$.

Consider cases for $N$ even and $N$ odd.

• $N$ even: In this case, the first and $(N+1)^{th}$ bits are nonzero. Thus, two nonzero odd bits are there, and none for even. Thus, $E=0,O=2 \implies E-O=2$. $2$ is not divisible by $3$ however, so $2^N+1$ is not divisible by $3$ for $N$ even.

• $N$ odd: Similarly, now there is one odd nonzero bit (the first) and one nonzero even bit (the $(N+1)^{th}$). Thus $E=0=1$ and $E-O=0$, which is divisible by $3$. Thus, $2^N+1$ is divisible by $3$ for $N$ odd.

Answer 5

$((-1)+3))^N+1= $

$\sum_{k=0}^{N}\binom{N}{k}(-1)^{N-k}3^k+1=$

$(-1)^N +1+\sum_{k=1}^{N}(-1)^{N-k}3^k.$

The expression is divisible by $3$ $\iff$

$(-1)^N+1=0.$

Hence?