How do you prove this divisibility?

Question

If $n$ is any natural number, prove that $3\mid 2^{2^n}-1$ is true. I can't find out how to do it. Thanks.

Answer 1

It is easiest if we use congruence notation. We have $2\equiv -1\pmod{3}$, and therefore $$2^{2^n}\equiv (-1)^{2^n}=1\pmod{3}.$$

But there are other ways. For example, we can do it by induction. The result is true at $n=1$. Suppose that $3$ divides $2^{2^k}-1$. We show that $3$ divides $2^{2^{k+1}}-1$. This follows immediately from the fact that $$2^{2^{k+1}}-1=(2^{2^{k}}-1)(2^{2^{k}}+1).$$

Answer 2

We could also prove by induction: when $n=1$, we get $4-1=3$, so the statement is true.

Now if $3\mid 2^{2^k}-1$ then $3\mid (2^{2^k}-1)(2^{2^k}+1)\implies 3\mid({2^{2^k}})^2-1\implies 3\mid{2^{2^{k+1}}}-1$.

Answer 3

Induction:

The statement is true for n=1:

$2^{2^{1}}-1=3$ that is divisible by 3.

Now suppose it's true for some natural number p, i.e:

$2^{2^p}-1$ is divisible by 3. Then:

$2^{2^{p+1}}-1=(2^{2^{p}})^2-1=(2^{2^{p}}-1)(2^{2^{p}}+1)$

which is divisible by 3 under the above assumption.

Hence, the statement is true for all natural numbers n.

Answer 4

Note that the exponent $2^n$ is even and $4\equiv 1 \mod 3$