# Odd Power of 2 is Congruent to 2 Modulo 3

## Theorem

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

Then:

$2^n \equiv 2 \pmod 3$

## Proof

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

We have that $n$ is odd.

Hence:

 $\displaystyle 2^n$ $\equiv$ $\displaystyle -1$ $\displaystyle \pmod 3$ $\displaystyle$ $\equiv$ $\displaystyle 3 - 1$ $\displaystyle \pmod 3$ $\displaystyle$ $\equiv$ $\displaystyle 2$ $\displaystyle \pmod 3$

$\blacksquare$