7
$\begingroup$

Sorry this is a really simple problem but I couldnt figure it out. I'm trying to find the value of $3^{1000}\bmod 7$. I know the actual value is 4, but I used a calculator. How would I simplify this problem to get the correct answer without a calculator? I dont want a direct answer, but maybe a nudge in the right direction, such as tricks I could use or maybe an alternate way of writing it.

$\endgroup$
  • $\begingroup$ Here's a hint: find the number $k$ such that $3^k = 1$. $\endgroup$ – Eric O. Korman Jan 23 '11 at 0:58
  • $\begingroup$ @Eric wouldnt that just be 0? $\endgroup$ – Snowman Jan 23 '11 at 1:09
  • 2
    $\begingroup$ that's true, let me rephrase: find a positive number $k$ such that $3^k = 1$ (mod 7). $\endgroup$ – Eric O. Korman Jan 23 '11 at 1:34
11
$\begingroup$

If you know Fermat's Little Theorem, then you know you can reduce the exponent. If you don't, you can simply do a bit of testing: \begin{align*} 3 &\equiv 3 &\pmod{7}\\ 3^2 &\equiv 2&\pmod{7}\\ 3^3 &\equiv 2\times 3&\pmod{7}\\ &\equiv -1 &\pmod{7}. \end{align*} At this point, you will also know that $3^6 = (3^3)(3^3)\equiv (-1)^2 \equiv 1 \pmod{7}$.

That means that the remainders will "cycle" every seven steps, since $3^7 = 3(3^6) \equiv 3(1) = 3 \pmod{7}$.

So now, notice that since $1000 = 6(166) + 4$, then $$3^{1000} = 3^{6(166)+4} = (3^6)^{166}3^4 = (3^6)^{166}3^33^1.$$ You know what each of the factors is modulo $7$, so you're done.

$\endgroup$
  • $\begingroup$ Once again, I'll ask for future reference: Is there a particular reason for the downvote? $\endgroup$ – Arturo Magidin Jan 23 '11 at 2:06
  • 1
    $\begingroup$ dunno about the down vote. But in the last tep, since $3^6 = 1$ wouldn't it be better to factor $1000 = 4 mod 6$? $\endgroup$ – Willie Wong Jan 23 '11 at 3:00
  • $\begingroup$ @Willie: Oops; quite right. That was silly of me. $\endgroup$ – Arturo Magidin Jan 23 '11 at 4:58
  • $\begingroup$ Just got around to actually read this answer in detail, and I found myself very confused :( I thin you used a lot of tricks that I have no idea how you used them, like $(3^3)(3^3)$ is congruent to $(-1)^2$..but I guess this is a complicated problem anyway $\endgroup$ – Snowman Jan 24 '11 at 6:15
  • $\begingroup$ @mohabitar: It's not really complicated. The "trick", as you call it, is just that you can add and multiply congruences: if $a\equiv b$ and $c\equiv d$, then $a+c\equiv b+d$ and $ac\equiv bd$ (if they are modulo the same thing). Since $3^3\equiv -1$, which we figure out just be computing, then $(3^3)(3^3)\equiv (-1)(-1)$. $\endgroup$ – Arturo Magidin Jan 24 '11 at 14:04
2
$\begingroup$

Try to split the huge number in smaller numbers you know the value of. For example

$3^{1000} \text{mod} 7= (3^{10})^{100} \text{mod} 7= (59049)^{100} \text{mod} 7= 4^{100} \text{mod} 7 = \ldots$

If $3^{10}=59049$ was still too big you could try to rewrite it again etc.

$\endgroup$
  • $\begingroup$ How much more could I simplify $3^{10}$ though? $\endgroup$ – Snowman Jan 23 '11 at 1:08
  • $\begingroup$ $3^{10}\equiv 3^3\cdot 3^3\cdot 3^3 \cdot 3\equiv 6\cdot 6 \cdot 6 \cdot 3 \equiv 36 \cdot 18 \equiv 1 \cdot 4 \equiv 4 (\text{mod} 7)$ for example. $\endgroup$ – Listing Jan 23 '11 at 1:13
2
$\begingroup$

Since that 36mod7=1, then we have 31000=36*166+4=34=4 mod7.

$\endgroup$
1
$\begingroup$

$3^{1000}$ is hard to compute by hand because of the $1000$. Can you learn anything from trying smaller exponents instead?

$\endgroup$
  • $\begingroup$ Well even I know that $3^{10}mod7$ is also 4, but I used a calculator for that too since $3^{10}$ is still a large number that I couldnt compute myself. $\endgroup$ – Snowman Jan 23 '11 at 1:07
  • $\begingroup$ @mohabitar: try $3^k\mod 7$ for $k=1,2,3,...$ and see what happens. $\endgroup$ – Isaac Jan 23 '11 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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