# Understanding congruence and using the notation correctly

I am working on the following problem presented in a text:

Find the remainder when $3^{1000}$ is divided by 13. I have just been introduced to the notation for saying that $a\equiv b \pmod{n}$. From what I understand of this it is stating that $a$ is congruent to $b$ when divided by $n$, that is $a$ will have the same remainder as $b$ when $b$ is divided by $n$ and vice versa.

From this I am assuming that $a \equiv a \pmod{n}$, where $a$ and $n$ are any integers?

The following property has also been introduced:

If $a \equiv b \pmod{n}$, then $a^k \equiv b^k \pmod{n}$ (*).

We have

$3^1 \equiv 3 \pmod{13}$, $3^2 \equiv 9 \pmod{13}$, and $3^3\equiv 27 \equiv 1 \pmod{13}$.

The above line bothers me because essentially it looks like we are just writing

$3 \equiv 3 \pmod{13}$, $9 \equiv 9 \pmod{13}$

however the first part I don't get is $3^3\equiv 27 \equiv 1 \pmod{13}$ is the extra 1 present here. Assuming my conclusion above is true then I would not have a problem with writing

$3^1 \equiv 3 \pmod{13}$, $3^2 \equiv 9 \pmod{13}$, and $3^3\equiv 27 \pmod{13}$,

but the extra 1 included is really bothering me as I do not understand its significance.

Secondly the next line in the solution states that:

"We repeatedly multiply by 3 and use property (*):

$3^4 \equiv 3 \pmod{13}$, $3^5 \equiv 9 \pmod{13}$, $3^6 \equiv 1 \pmod{13}$.

Thus the remainders form the repeating pattern 3,9,1,3,9,1,... .

I am not following why we have stopped writing that $3^n$ is congruent to the result of $3^n$. So where before we had $3^2 \equiv 9 \pmod{13}$, why do we now have $3^5 \equiv 9 \pmod{13}$ instead of $3^5 \equiv 243 \pmod {13}$?

-
$27$ and $1$ have the same remainder when divided by $13$, so $27\equiv 1\pmod{13}$. Or, preferrably, use the definition of congruence: $a\equiv b\pmod n$ means that $n\mid (a-b)$. In your case $13$ divides $27-1=2\cdot13$, so $27\equiv1\pmod{13}$. –  Jyrki Lahtonen May 14 '12 at 13:59
Or is it the use of repeated $\equiv$-signs that's giving you a headache? You can think of $\equiv$ as being like the equality sign "$=$". You often see equality signs used sequentially. Like $$2(1+1)=2\cdot1+2\cdot1=2+2=4.$$ With congruences it works much the same way: $$9\equiv 7\equiv 5\equiv3\equiv1\pmod{2}.$$ The modulus ($2$ in my example, $13$ in yours) is only given at the end. That chain of congruences simply means that $9\equiv 7\pmod2$ and $7\equiv5\pmod2$ and $\ldots$ –  Jyrki Lahtonen May 14 '12 at 14:07
@JyrkiLahtonen: But why do we write it as congruent to 1? Why would it not just be left as $3^3 \equiv 27 \pmod{13}$? I don't understand what is gained from noticing that it is also congruent to 1. –  Aesir May 14 '12 at 14:07
Ah! That's what the rest of the argument is all about! Because $27\equiv1\pmod{13}$, then also $27^2\equiv1^2\pmod{13}$. And, more to the point: $27^{333}\equiv1^{333}\pmod{13}$. Here $27^{333}=3^{3\cdot333}=3^{999}$ and $1^{333}=1$. We have just shown that $$3^{999}\equiv 1\pmod{13}.$$ In other words, at this point we know that $3^{999}$ has remainder $1$ when divided by $13$. The point is to use a intermediate results to simplify the calculation of the remainder of large number. And it is very easy to raise $1$ to a high power. –  Jyrki Lahtonen May 14 '12 at 14:12
Ok so this is an example, therefore whoever set the problem new that searching for a congruence to 1 would be significant. Is this a common result, do most problems require you to search for an integer congruent to 1 and this marks a repeating pattern? To add this is assuming that there is always a repeating pattern in the first place? Thanks for the help so far! –  Aesir May 14 '12 at 14:18
show 1 more comment

When doing anything with integers modulo $n$, we might as well reduce modulo $n$ as often as we can, to keep the numbers nice and small, and therefore easier to do arithmetic with.

In your example with powers of $3$ modulo $13$, the first power that is bigger than $13$ is $3^3 = 27$. Since we've reached a number bigger than $13$, we might as well reduce it modulo $13$. As it happens we get $1$, but that is not the reason we bother to reduce.

Consider another example, say powers of $4$ modulo $7$. We have $4^1\equiv 4 \pmod 7$ and $4^2 \equiv 16 \equiv 2 \pmod 7$. Now this is useful, because we can calculate $4^3 \pmod 7$ without having to calculate $4^3$: $$4^3 \equiv 4\cdot 4^2 \equiv 4\cdot 2 \equiv 8 \equiv 1 \pmod 7.$$ Now we have indeed gotten back to $1$, but as you see, it was useful to reduce already before that.

"I am not following why we have stopped writing that $3^n$ is congruent to the result of $3^n$. So where before we had $3^2\equiv 9 \pmod{13}$, why do we now have $3^5\equiv 9\pmod{13}$ instead of $3^5\equiv 243 \pmod{13}$?"

We could write $3^5\equiv 243 \pmod{13}$ if we like, but if we never do any reduction modulo $13$, then we are not doing anything more than standard arithmetic, and so we are not going to see what the pattern modulo $13$ is. Also, while we could work out that $243\equiv 9 \pmod{13}$, it's much easier to use what we've already done and say: $$3^5\equiv 3^3\cdot 3^2 \equiv 1\cdot 9\equiv 9 \pmod{13}.$$

-
Excellent, this is just what I needed, thanks! –  Aesir May 14 '12 at 17:29
@Aesir: Wow, you read that quickly! I'm glad it helped. –  Tara B May 14 '12 at 17:30
Fermat's Theorem tells us that $\,\,3^{13}\equiv 3\pmod{13}\Longrightarrow 3^{12}\equiv 1\pmod{13}\,$ , and since $\,1,000=12\cdot 83+4\,$ , we get $$3^{1,000}=\left(3^{12}\right)^{83}3^4\equiv81\equiv 3\pmod{13}$$
That is correct, but Fermat's theorem seems like a rather large hammer to use on this little problem, since as the commenters have pointed out, it is easy to see that $3^3\equiv 1\pmod{13}$. –  MJD May 14 '12 at 15:53