# If $p\equiv1\pmod{4}$ is a prime, then $-4$ and $(p-1)/4$ are both quadratic residues of $p$.

I'm working on the following problem:

If $p\equiv1\pmod{4}$ is a prime, then $-4$ and $(p-1)/4$ are both quadratic residues of $p$.

This means it must be shown that $(-4/p)=1$ and $(((p-1)/4)/p)=1$, where $(a/p)$ denotes the Legendre symbol.

I managed to solve the first part. Since $p\equiv1\pmod{4}$, $(-1/p)=1$. Then: \begin{align*} (-4/p) &= (-1/p)(2^2/p) \\ &= 1\cdot1 \\ &= 1, \end{align*} since $(a^2/p)=1$.

However, I have no clue how to solve the second part. Can anyone give a hint how to start this part?

• By the way, \pmod{4} for providing $x = y \pmod{4}$ should suffice instead of using your complicated \hbox expressions. – Zain Patel Jul 16 '15 at 20:29
• @Zain Patel Thanks. – user95864 Jul 16 '15 at 20:36

Let $n=(p-1)/4$. Then $4n=p-1\equiv-1$, and $$\left(\frac{-1}p\right)=\left(\frac{4n}p\right)=\left(\frac{4}p\right)\left(\frac{n}p\right).$$ You know everything else except $\left(\frac{n}p\right)$, so you can solve it from this equation.

• Thanks a lot! That solved my problem! – user95864 Jul 16 '15 at 20:42

Hmmm... $\sqrt{-4}= 2 \sqrt{-1}$ and $\sqrt{\frac{p-1}{4}} = \frac{1}{2} \sqrt{-1}$ so one way to think of it is to start from showing $\sqrt{-1}$ is a quadratic residue mod $p$.

You are trying to solve $x^2 = \frac{p-1}{4} \mod p$ it is the same to solve $(2x)^2 = -1 \mod p$

Similarly, when you aolve $x^2 = - 4 \mod p$, you can solve $(\frac{1}{2}x)^2 \equiv -1 \mod p$, where $\frac{1}{2}\equiv \frac{p+1}{2} \mod p$ .

• I'm not sure whether this is the correct approach. I want to show that (p-1)/4 is a QR and not the square root of it. And to be honest, working with square roots in modular arithmetic doesn't make me happy... Thanks for your response though. – user95864 Jul 16 '15 at 20:23
• Ok, but I don't want to find $x$ such that $x^2\equiv (p-1)/4\pmod{p}$, I only want to show it exists. – user95864 Jul 16 '15 at 20:35