# Prove with modular arithmetics that $4^n =4 \pmod 6$.

How do I prove $4^n\equiv 4\pmod 6$ where $n \in \Bbb Z_+$?

I was always doing it by checking $n \in \{1,2,3,4,5 \}$ and if there was a pattern then I assume that it is correct.

So I was wondering if there is a easier and faster way to prove it with modular arithmetics.

• Perhaps use induction – JohnColtraneisJC Aug 25 '17 at 12:08
• $4^n - 4 = 4(4^{n-1} - 1)$. Note that $x^m - y^m = (x-y)(x^{m-1} + x^{m-2}y + \cdots + xy^{m-2} + y^{m-1})$, so $4^{n-1} -1 = (4-1) (4^{n-2} + \cdots + 1)$ is divisible by $3$. Conclusion? – Cauchy Aug 25 '17 at 12:10
• Use $\in$ for $\in$. – Shaun Aug 25 '17 at 12:11

Proof by induction for $n>1$ $$4^1 = 4 \mod 6$$

No assume its true for some $n$ $$4^n = 4 \mod 6$$ $$4^{n+1} = 16 \mod 6$$ $$4^{n+1} = 4 \mod 6$$

So its true for $\mathbb Z^+$

First check mod $3$ and then mod $2$. Since both $2$ and $3$ divide $4^n-4$, then so must $6.$

Proof by induction is the easiest way.

$\left[4^{n} \equiv 4\ \mathrm{(mod\ 6)} \implies 4^{n+1} \equiv 16\ \mathrm{(mod\ 6)}\equiv 4\ \mathrm{(mod\ 6)}\right] \land \left[4^{1} \equiv 4\ \mathrm{(mod\ 6)}\right]\\\implies 4^{n} \equiv 4\ \mathrm{(mod\ 6)}\ \forall n\in\mathrm{N^{*}}$

Because $4^n = 2^{2n} = (2^n)^2$, this is always a square number. There are only $3$ possible values of $m^2\bmod 6$: $\{0,1,4\}$. Since $4^n$ is not divisible by $6$ and is not odd, it must be that $4^n\equiv 4 \bmod 6$.