Modular Arithmetic: using congruence to find remainder

Question

How do I use the fact that if $a = b \pmod n$ and $c = d\pmod n$ then $ac = bd\pmod n$ to find the remainder when $3^{11}$ is divided by $7$?

Answer 1

We know that:
$3\equiv3\pmod7$. Multiplying both sides by 3, we get $3^2\equiv9\pmod7$, which simplifies to:
$3^2\equiv2\pmod7$. Multiplying both sides by 3 again (and simplifying):
$3^3\equiv6\pmod7$
$3^4\equiv4\pmod7$
$3^5\equiv5\pmod7$
$3^6\equiv1\pmod7$
$3^7\equiv3\pmod7$
$3^8\equiv2\pmod7$
$3^9\equiv6\pmod7$
$3^{10}\equiv4\pmod7$
$3^{11}\equiv5\pmod7$

There are two ways to speed this up. One is to use Fermat's Little (not to be confused with Last) Theorem, which states that $a^{p-1}\equiv1\pmod p$ when $a\not\equiv0$ and $p$ is prime. So, we have:
$3^{11}\equiv3^63^5\equiv(1)3^5\equiv3^5\pmod7$.
To find $3^5\pmod7$, we only need to use the above method 5 times instead of 11.

Another is to go like this:
$3\equiv3\pmod7$. Squaring both sides:
$3^2\equiv2\pmod7$. Squaring:
$3^4\equiv4\pmod7$. Squaring:
$3^8\equiv2\pmod7$.
Since $11=8+2+1$, we have $3^{11}\equiv3^83^23^1\equiv(2)(2)(3)\equiv12\equiv5\pmod7$.

Answer 2

$3^{11} \equiv (3^2)^5\cdot 3 \equiv 2^5 \cdot 3 \equiv 96 \equiv 5 \pmod 7$

Of course, it's actually easier to employ Fermat's Little Theorem (if you're permitted) like so:

$3^{11} \equiv 3^6 \cdot 3^5 \equiv 1 \cdot (3^2)^2 \cdot 3 \equiv 2^2 \cdot 3 \equiv 12 \equiv 5 \pmod 7$

Answer 3

First, the remainder when blah is divided by $7$ means the congruence of blah mod $7$. The significance of the result you quoted is that when doing a computation in which you’re only interested in the final congruence modulo $7$, you can always replace a number by any other number that’s congruent to it. So, $3^2$ may be $9$, but you can replace that nine by $2$, which is congruent to it modulo $7$. So, we have $3^2\equiv2\pmod7$. Similarly, $3^3\equiv3\cdot2=6\pmod7$. And so you continue, making a list of the powers of $3$ modulo $7$, and you find that there’s a periodic behavior. You can finish it now.