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.

Is there a quick way to solve $3^8 \equiv x \mod 17$?

Like the above says really, is there a quick way to solve for $x$? Right now, what I started doing was $3^8 = 6561$, and then I was going to keep subtracting $17$ until I got my answer.

share|improve this question
2  
Having gotten to $6561$ you can do long division with remainder to find it. The result is $6561=17*385+16$ –  Ross Millikan Jan 10 '13 at 23:48
add comment

5 Answers 5

up vote 6 down vote accepted

I usually just do it in steps if it's reasonable enough.
$3^3=10$
$3^4=10*3=13$
$3^5=13*3=5$
$3^8=5*3^3=5*10=16$

share|improve this answer
add comment

When dealing with powers, squaring is a good trick to reduce computations (your computer does this too!) What this means is:

$ \begin{array}{l l l l l} 3 & &\equiv 3 &\pmod{17}\\ 3^2 &\equiv 3^2 & \equiv 9 &\pmod{17}\\ 3^4 & \equiv 9^2 & \equiv 81 \equiv 13 & \pmod{17}\\ 3^8 & \equiv 13^2 & \equiv 169 \equiv 16 & \pmod{17}\\ \end{array} $


Slightly irrelevant note: By Euler's theorem, we know that $3^{16} \equiv 1 \pmod{17}$. Thus this implies that $3^{8} \equiv \pm 1 \pmod{17}$. If you know more about quadratic reciprocity, read Thomas Andrew's comment below.

share|improve this answer
2  
Calvin: Yes there is. If $p\not\mid a$, $a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)\pmod p$ so you can use quadratic reciprocity in this case. (Where $\left(\frac{a}{p}\right)$ is the Legendre symbol.) –  Thomas Andrews Jan 10 '13 at 23:44
    
@ThomasAndrews I didn't know how much the OP knew, considering that OP did $3^8 = 6561$. I just looked up the questions that he asked, and realized that this should most prob just be done by quadratic reciprocity... I think you should post that as a solution. –  Calvin Lin Jan 10 '13 at 23:45
    
Yeah, I just object to using the phrase, "there isn't much more that we can do from here here," since there is, and "we" includes you. Better to not mislead, but rather say, "Unless you are familiar with quadratic reciprocity, there isn't much more you can do from here." –  Thomas Andrews Jan 10 '13 at 23:47
add comment

My immediate response was that $3^2=9$, so $3^4=81\equiv-4\pmod{17}$, and $3^8\equiv16\pmod{17}$, though if I had any further computing to do, I’d probably convert that to $-1\pmod{17}$.

share|improve this answer
add comment

Strictly speaking, the fastest way would probably be just to use some sort of computer/software.

For example, here is the answer found in Wolfram|Alpha: $3^8 \equiv x \mod 17$

share|improve this answer
3  
Lol fair enough! +1 because it does answer my question pretty well. But I need a method incase I have to do something in my exam. –  Kaish Jan 10 '13 at 23:50
add comment

Here is a simple way of calculating it, which unfortunately only works for these numbers.

Note that $2^4=16=-1 \pmod {17}$.

Then

$$3^8=-2^43^8=-2^49^4=-18^4=-1^4=-1 \pmod{17}$$

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