# 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}$?

1
2022-07-25 20:43:22
Source Share