# Powers of 3 Modulo 8/Proof 1

## Theorem

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

Then:

$3^n \equiv \begin {cases} 1 \pmod 8 & : \text {$n$even} \\ 3 \pmod 8 & : \text {$n$odd} \end {cases}$

## Proof

Let the statement be rewritten as:

For all $r \in \Z_{\ge 0}$:

$3^r \equiv \begin {cases} 1 \pmod 8 & : r = 2 n \\ 3 \pmod 8 & : r = 2 n + 1 \end {cases}$

where $n \in \Z_{\ge 0}$.

The proof proceeds by induction.

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

$3^{2 n} \equiv 1 \pmod 8$

$\map P 0$ is the case:

$3^{2 \times 0} = 3^0 = 1 \equiv 1 \pmod 8$

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

### Basis for the Induction

$\map P 1$ is the case:

 $\ds 3^{2 \times 1}$ $=$ $\ds 3^2$ $\ds 3^{2 \times 1}$ $=$ $\ds 9$ $\ds$ $\equiv$ $\ds 1 \pmod 8$

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 1$, then it logically follows that $\map P {k + 1}$ is true.

So this is the induction hypothesis:

$3^{2 k} \equiv 1 \pmod 8$

from which it is to be shown that:

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

### Induction Step

This is the induction step:

We have:

 $\ds 3^2$ $\equiv$ $\ds 1$ $\ds \pmod 8$ Basis for the Induction $\ds 3^{2 k}$ $\equiv$ $\ds 1$ $\ds \pmod 8$ Induction Hypothesis $\ds \leadsto \ \$ $\ds 3^2 \times 3^{2 k}$ $\equiv$ $\ds 1 \times 1$ $\ds \pmod 8$ Congruence of Product $\ds \leadsto \ \$ $\ds 3^{2 \paren {k + 1} }$ $\equiv$ $\ds 1$ $\ds \pmod 8$

So $\map P k \implies \map P {k + 1}$ and then it follows by the Principle of Mathematical Induction that:

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

Then we have:

 $\ds 3^{2 n + 1}$ $=$ $\ds 3 \times 3^{2 n}$ $\ds$ $\equiv$ $\ds 3 \times 1$ $\ds \pmod 8$ Congruence of Product $\ds$ $\equiv$ $\ds 3$ $\ds \pmod 8$

and the result follows.

$\blacksquare$