<s>[INST] Modular Arithmetic: using congruence to find remainder 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$?
 [/INST] 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$.
</s>