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.
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^{*}}$
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^+$
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$.
$\in$for $\in$. – Shaun Aug 25 '17 at 12:11