Let $p \neq 2,5$ be prime. Suppose you know that $p \equiv 1 \mod 4$ and that $(\frac{p}{5}) = 1$, with $(\cdot)$ the Legendre Symbol.

How does it follow that $p \equiv 1 \mod 20 $ or that $p \equiv 9 \mod 20$?


EDIT: well, this is part of a larger question, this is the final part of my efforts, if I can solve this one, I solved the exercise. It's just an exercise found online, and I thought I could use this, for $a \in \mathbb{Z}$: $$(\frac{a}{q}) \equiv a^{(q-1)/2} \mod q,$$ with $q \neq 2$ prime. That gives you, combined with the fact that $p \equiv 1 \mod 4$, the solution $1 \mod 20$. I'm afraid I don't know how to obtain that $9 \mod 20$ though.

  • $\begingroup$ Welcome to Mathematics Stack Exchange! I would suggest you to explain a little bit how you tried to solve it, at least your thoughts, so other people could help you better. Good luck! $\endgroup$ – iadvd Aug 24 '15 at 9:20
  • $\begingroup$ When is $\genfrac{(}{)}{}{}{p}{5} = 1$? $\endgroup$ – Daniel Fischer Aug 24 '15 at 9:48
  • $\begingroup$ When $p^2 \equiv 1 \mod 5 $ $\endgroup$ – querty Aug 24 '15 at 10:01
  • 1
    $\begingroup$ @querty $p^2\equiv 1\pmod{5}\iff p\equiv \{1,4\}\pmod{5}$. $\endgroup$ – user236182 Aug 24 '15 at 10:12
  • 1
    $\begingroup$ @querty In general, $x^2\equiv a^2\pmod{p}$ always has exactly two solutions, namely $x\equiv \pm a\pmod{p}$. $\endgroup$ – user236182 Aug 24 '15 at 10:15

$1^2\equiv \color{#00f}1,\, 2^2\equiv\color{#00f}4,\, 3^2\equiv\color{#00f}4,\, 4^2\equiv\color{#00f}1\pmod{5}$.

Therefore $\left(\frac{p}{5}\right)=1\iff p\equiv \{\color{#00f}1,\color{#00f}4\}\pmod{5}$.

It's given $p\equiv 1\pmod{4}$.

Now apply Chinese Remainder Theorem.


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.