# Congruence Modulo 3 of Power of 2

## Theorem

Let $n \in \Z_{\ge 0}$ be a positive integer.

Then:

$2^n \equiv \paren {-1}^n \pmod 3$

That is:

$\exists q \in \Z: 2^n = 3 q + \paren {-1}^n$

## Proof

The proof proceeds by induction.

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

$2^n \equiv \paren {-1}^n \pmod 3$

$P \left({0}\right)$ is the case:

 $\displaystyle 2^0$ $=$ $\displaystyle 1$ $\displaystyle$ $=$ $\displaystyle \paren {-1}^0$ $\displaystyle$ $\equiv$ $\displaystyle \paren {-1}^0$ $\displaystyle \pmod 3$

Thus $\map P 0$ is seen to hold.

### Basis for the Induction

$\map P 1$ is the case:

 $\displaystyle 2^1$ $=$ $\displaystyle 2$ $\displaystyle$ $=$ $\displaystyle 3 + \paren {-1}$ $\displaystyle$ $=$ $\displaystyle 3 + \paren {-1}^1$ $\displaystyle$ $\equiv$ $\displaystyle \paren {-1}^1$ $\displaystyle \pmod 3$

Thus $\map P 1$ is seen to hold.

This is the basis for the induction.

### Induction Hypothesis

Now it needs to be shown that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.

So this is the induction hypothesis:

$2^k \equiv \paren {-1}^k \pmod 3$

from which it is to be shown that:

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

### Induction Step

This is the induction step:

 $\displaystyle 2^{k + 1}$ $=$ $\displaystyle 2 \times 2^k$ $\displaystyle$ $=$ $\displaystyle 2 \times \paren {3 q + \paren {-1}^k}$ $\displaystyle$ $=$ $\displaystyle \paren {3 \paren {2 q} + 2 \paren {-1}^k}$ $\displaystyle$ $=$ $\displaystyle \paren {3 \paren {2 q} + 2 \paren {-1}^k}$

If $k$ is odd, this means:

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

If $k$ is even, this means:

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

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

$\forall n \in \Z_{\ge 0}: 2^n \equiv \paren {-1}^n \pmod 3$

$\blacksquare$