Divisibility by 3 near powers of 2

Another post that tidies up a scrap of paper lying about the house. It’s almost a proof by induction that never actually gets going…

Show that alternate powers of 2 ± 1 are divisible by 3. For example 4-1=3, 8+1=9, 16-1=15 etc.

Let’s frame the problem a bit better. Show that $$2^{2n}-1$$ and $$2^{2n+1}+1$$ are divisible by 3 for $$n \in \mathbb{N}$$.

Start with the even powers as there’s an obvious route in:

$$2^{2n}-1 = \left ( 2^n-1 \right ) \left ( 2^n+1 \right )$$

Since this is the product of two numbers from the 3 three consecutive numbers $$2^n-1, 2^n, 2^n+1$$ then either $$2^n-1$$ or $$2^n+1$$ is divisible by 3.

Even powers of two minus one $$2^{2n}-1$$ are divisible by 3.

Now look at the odd powers of two:

$$2^{2n+1}+1 = 2 \times 2^{2n}+1$$

That’s a bit nicer. Now substitute in what we just learned about even powers, and make a correction of +2 to account for it:

$$2 \times 2^{2n}+1 = 2 \times \left (2^{2n}-1 \right ) + 2 + 1\\ 2 \times 2^{2n}+1 = 2 \times \left (2^{2n}-1 \right ) + 3$$

We can clearly factor out 3 from both terms.

Odd powers of two plus one $$2^{2n+1}+1$$ are divisible by 3.

Tags: ×