Proving a statement using modular arithmetic I keep running into the same type of failure when attempting to prove a statement using modular arithmetic, when the expression at hand is exponential.
For example:

Prove that the remainder of a power of $2$ divided by $6$ is either $2$ or $4$.

It's pretty easy for $5$ out of $6$ cases:


*

*$n\equiv\color\red1\pmod6\implies2^n\equiv2^\color\red1\equiv2\pmod6$

*$n\equiv\color\red2\pmod6\implies2^n\equiv2^\color\red2\equiv4\pmod6$

*$n\equiv\color\red3\pmod6\implies2^n\equiv2^\color\red3\equiv2\pmod6$

*$n\equiv\color\red4\pmod6\implies2^n\equiv2^\color\red4\equiv4\pmod6$

*$n\equiv\color\red5\pmod6\implies2^n\equiv2^\color\red5\equiv2\pmod6$


But I am unable to get it straight for $n=0$:


*

*$n\equiv\color\red0\pmod6\implies2^n\equiv2^\color\red0\equiv1\pmod6$


Now, I can work it out by using $n=6$ instead:


*

*$n\equiv\color\red6\pmod6\implies2^n\equiv2^\color\red6\equiv4\pmod6$


But it doesn't feel right to use the notation "$n\equiv6\pmod6$".
So there is definitely some sort of flaw in my method, and I would like to know what that is.
Thanks
 A: To make your proof work, you would need to prove the following:

If $2^n\equiv2\pmod6$, then $2^{n+6}\equiv2\cdot2^6\equiv2\pmod6$


If $2^n\equiv4\pmod6$, then $2^{n+6}\equiv4\cdot2^6\equiv4\pmod6$

Without these two statements, looking at the exponent mod $6$ is not going to help, since in general, $b\equiv c\pmod{m}$ does not imply that $a^b\equiv a^c\pmod{m}$.
Using these two statements, and the fact that $2^n\equiv2\pmod6$ or $2^n\equiv4\pmod6$ for $n=1$ to $n=6$, proves the statement for all $n\ge1$ by induction.

However here is a simpler proof of the statement:
Note that $2^1\equiv2\pmod6$.
Suppose that $2^n\equiv2\pmod6$, then $2^{n+1}\equiv4\pmod6$.
Suppose that $2^n\equiv4\pmod6$, then $2^{n+1}\equiv8\equiv2\pmod6$.

Therefore, by induction, if $n\ge1$, then $2^n\equiv2\pmod6$ or $2^n\equiv4\pmod6$.

Note that the statement is false for $n=0$, so the highlighted statement above is the best that can be made.
A: I have never heard of the theorem you are using. You are using something like
$a\equiv b$ (mod $n$)$\implies k^a\equiv k^b$ (mod $n$).
A simple counterexample would be
$5\equiv 1$ (mod $4$) but $2^5\not\equiv 2^1$ (mod $4$).
