# Simple congruence relation (modular arithmetic)

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

Thanks!

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.

• 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! – iadvd Aug 24 '15 at 9:20
• When is $\genfrac{(}{)}{}{}{p}{5} = 1$? – Daniel Fischer Aug 24 '15 at 9:48
• When $p^2 \equiv 1 \mod 5$ – querty Aug 24 '15 at 10:01
• @querty $p^2\equiv 1\pmod{5}\iff p\equiv \{1,4\}\pmod{5}$. – user236182 Aug 24 '15 at 10:12
• @querty In general, $x^2\equiv a^2\pmod{p}$ always has exactly two solutions, namely $x\equiv \pm a\pmod{p}$. – 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}$.