1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You wrote mod 97 three times and formatted it three different ways. Are you familiar with successive squaring? $\endgroup$ – T. Bongers May 5 '16 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 Andrews May 5 '16 at 3:02
  • $\begingroup$ Ohh. r =8 is the answer. $\endgroup$ – Surojit May 5 '16 at 3:05
  • $\begingroup$ en.wikipedia.org/wiki/Euler%27s_criterion $\endgroup$ – user236182 May 5 '16 at 3:10
1
$\begingroup$

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

$\endgroup$

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.