Simple congruence relation (modular arithmetic)

74 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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