1
$\begingroup$

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

  • 0
    Yes. That's the way it works more often than not.2012-05-14

2 Answers 2

3

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.

To address your last question:
"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}.$

  • 0
    @Aesir: Wow, you read that quickly! I'm glad it helped.2012-05-14
0

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

  • 6
    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}$.2012-05-14