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