1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Thanks a lot! That solved my problem! $\endgroup$ – user95864 Jul 16 '15 at 20:42
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user95864 Jul 16 '15 at 20:23
  • $\begingroup$ 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. $\endgroup$ – user95864 Jul 16 '15 at 20:35

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.