I want find out the Smallest positive integer r such that $8^{17} \equiv r \pmod{97}$.
Fermat's theorem only tells us $8^{96} \equiv 1 \pmod{97}.$
How can I proceed. Any hint will be appreciated.
Thank you in advance.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ You wrote mod 97 three times and formatted it three different ways. Are you familiar with successive squaring? $\endgroup$– user296602Commented May 5, 2016 at 3:00
-
1$\begingroup$ Hint: $8^{16}=2^{48}\equiv \pm 1\pmod{97}$. When is $2^{(p-1)/2}\equiv 1\pmod p$? $\endgroup$– Thomas AndrewsCommented May 5, 2016 at 3:02
-
$\begingroup$ Ohh. r =8 is the answer. $\endgroup$– SurojitCommented May 5, 2016 at 3:05
-
$\begingroup$ en.wikipedia.org/wiki/Euler%27s_criterion $\endgroup$– user236182Commented May 5, 2016 at 3:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
We have that $2$ is a quadratic residue $\pmod p$ when $p \equiv \pm 1 \pmod 8$. In this case, $97 \equiv 1 \pmod 8$, ensuring that $2$ is a quadratic residue.
By Euler's Criterion, we have that $8^{16}=2^{48} \equiv 1 \pmod {97}$. Thus, $8^{17} \equiv 8 \pmod {97}$.
