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$
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$
  • $\begingroup$ What is $aR_p$? $\endgroup$ – Username Unknown Apr 12 '15 at 5:44
  • 1
    $\begingroup$ @UsernameUnknown, Find the symbol in the link $\endgroup$ – lab bhattacharjee Apr 12 '15 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$ – Username Unknown Apr 12 '15 at 5:49
  • $\begingroup$ @UsernameUnknown, $587\equiv3\pmod4, a=116, b\equiv a^{(p+1)/4}$ $\endgroup$ – lab bhattacharjee Apr 12 '15 at 6:00
  • $\begingroup$ @UsernameUnknown I explain why this works in my answer. $\endgroup$ – Bill Dubuque Apr 12 '15 at 15:37
1
$\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$

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.