Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
$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
3  
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
3  
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

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
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}$. –  MJD May 14 '12 at 15:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.