1
$\begingroup$

Let $p$ be a prime satisfying $p\equiv 3 \mod 4$. Let $a$ be a quadratic residue modulo $p$. Prove that the number $$b\equiv a^\frac{p+1}{4} \mod p$$ has the property that $b^2\equiv a \mod p$. (Hint: Write $\frac{p+1}{2}$ as $1+\frac{p-1}{2}$.) This gives an easy way to take square roots modulo $p$ for primes that are congruent to $3$ modulo $p$. \textit{Hint:} Write $\frac{p+1}{2}$ as $1+\frac{p-1}{2}$ and use Exercise $3.36$.) This gives an easy way to take square roots modulo $p$ for primes that are congruent to $3$ modulo $p$.

I assume that the proof comes directly from the proof of quadratic residues but I am not sure how.

$\endgroup$

2 Answers 2

2
$\begingroup$

Lagrange noticed that one can easily compute a square root in groups of odd order $\,\color{#c00}{2n+1},\,$ i.e. the equation $\,x^2 = a\,$ has solution $\,x = a^{n+1}\,$ by $\,x^2 = a\, a^{\color{#c00}{2n+1}} = a,\,$ by Lagrange's Theorem.

Here mod $\,\color{#0a0}{p = 4n+3}\,$ the subgroup $\,S\,$ of squares has odd order $\,(p-1)/2 = 2n+1.\,$ Thus, by above, any square $\,a\in S\,$ has a square root $\,x = a^{n+1}.\,$ Here $\,n\!+\!1 = \color{#0a0}{(p+1)/4}$.

$\endgroup$
1
$\begingroup$

Yes, you are right, from the definition of $aR_p\implies a^{(p-1)/2}\equiv1\pmod p$

Now $\left(a^{(p+1)/4}\right)^2=a^{(p-1)/2}\cdot a\equiv a\pmod p$

$\endgroup$
5
  • $\begingroup$ What is $aR_p$? $\endgroup$ Apr 12, 2015 at 5:44
  • 1
    $\begingroup$ @UsernameUnknown, Find the symbol in the link $\endgroup$ Apr 12, 2015 at 5:45
  • $\begingroup$ I knew I was over thinking of this thank you for you help. I have one more question what if I wanted to use this method to compute some applied problems such as $b^2\equiv 116 \mod 587$? $\endgroup$ Apr 12, 2015 at 5:49
  • $\begingroup$ @UsernameUnknown, $587\equiv3\pmod4, a=116, b\equiv a^{(p+1)/4}$ $\endgroup$ Apr 12, 2015 at 6:00
  • $\begingroup$ @UsernameUnknown I explain why this works in my answer. $\endgroup$ Apr 12, 2015 at 15:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .