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

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.

-
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

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$

-

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.

-
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

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

-

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$

-
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

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

-