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

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.

## 2 Answers

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$

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

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