My number theory textbook doesn't explain this particularly well, so I'm having a hard time understanding this concept.

My book proves the simple theorem that $2$ is a square $\bmod p$ iff $p \equiv 1$ or $p \equiv 7 \pmod 8$. Then it explains how to find the square root of $2 \pmod p$. It explains that for a primitive root $g \pmod p$ with order $p-1$, since $8 \vert p-1$, then $g^{\frac{p-1}{8}}=h$ is a primitive 8th root $\bmod p$. Then, from an earlier observation regarding the complex 8th roots of 1, $h+h^7$ is a square root of 2. I understand this and don't have a problem solving a similar problem.

But the book doesn't address how to solve the same problem in the case of $p \equiv 7 \pmod 8$. Since the order of any primitive root of such a $p$ is not divisible by 8, how am I to find a primitive 8th root $\bmod p$? At first glance I would imagine the solution has something to do with the fact that $p^2 \equiv 1 \pmod 8$ and thus $\frac{(p-1)^2}{8}$ may be usable as an exponent in some way.

  • 1
    $\begingroup$ See this answer. Among other things it is shown there that $2^{(p+1)/4}$ will be a square root of two modulo $p$. $\endgroup$ – Jyrki Lahtonen Nov 17 '14 at 10:13

Your Answer

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

Browse other questions tagged or ask your own question.