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
$\endgroup$ 52 Answers
$\begingroup$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.
$\endgroup$ 5 $\begingroup$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$).
$\endgroup$
