1

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

barak manos
  • 43,109
  • Why do you think the implication $a\equiv b\pmod 6\implies 2^a\equiv2^b\pmod 6$ should be true? Prove first that if $a,b\ge1$ then $a\equiv b\pmod2\implies 2^a\equiv2^b\pmod6$. – Jyrki Lahtonen Aug 03 '16 at 08:49
  • In other words, why don't you first experiment to see how the land lies: $2^1\equiv2\pmod6$, $2^2\equiv4\pmod6$, $2^3\equiv2\pmod6$, $2^4\equiv4\pmod6$. Then you realize that powers of two are always even (when the exponent is $>0$), so they always leave remainder $0,2$ or $4$ modulo $6$. The question is about ruling out $0$, which amounts to studying divisibility by three... – Jyrki Lahtonen Aug 03 '16 at 08:53
  • And, there is nothing wrong with the notation $n\equiv6\pmod 6$. It simply means that $n-6$ is a multiple of $6$. You may still be stuck with remainders (programmes at least often are) instead of being conversant with the more flexible congruences: $n\equiv1\pmod 6$ if and only if $n\equiv7\pmod 6$. – Jyrki Lahtonen Aug 03 '16 at 08:55
  • The point of my first comment becomes more apparent when you consider the following: the residue class of $2^n$ modulo $5$ depends on the residue class of the exponent $n$ modulo $4$. The residue class of $2^n$ modulo $9$ depends on the residue class of $n$ modulo $6$ et cetera. You simply cannot reduce the exponent w.r.t. the same modulus. There is no such law in modular arithmetic. You can reduce multiplicative factors or additive terms individually, but not an exponent. It will become clearer when you learn about groups and rings. – Jyrki Lahtonen Aug 03 '16 at 08:58
  • @PeterFranek: I am not trying to prove this specific statement, I am merely using it in order to illustrate the problem that I've been experiencing. – barak manos Aug 03 '16 at 09:01

2 Answers2

1

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.

robjohn
  • 345,667
  • I am not trying to prove this specific statement, I am merely using it in order to illustrate the problem that I've been experiencing. – barak manos Aug 03 '16 at 09:01
  • @barakmanos: I have added to my answer to try to address the problem exhibited. That is, in general, $b\equiv c\pmod{m}$ does not imply that $a^b\equiv a^c\pmod{m}$. – robjohn Aug 03 '16 at 09:20
  • Thank you. Can we still say that this is true for any positive integers $a,b,c,m$? – barak manos Aug 03 '16 at 09:29
  • I am not sure exactly what you mean. In some cases, for example, $a=2$, $m=6$, and $b,c\ge1$, the implication is true. However, in general, it is not. – robjohn Aug 03 '16 at 09:59
  • Yes, I've realized that from @edm's answer below. Not sure what I was thinking to be honest. Thanks... – barak manos Aug 03 '16 at 10:06
1

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$).

edm
  • 5,640