1
$\begingroup$

I was trying to solve a question from CLRS where it asks to show that if a prime is of the form $p = 4k + 3$, then:

$$ a^{k+1} \pmod p$$

is a square root of $a$ when $a$ is a Quadratic Residue in $\mathbb{Z}^*_p$. I wasn't quite sure how to show that but I did notice the following:

If $a$ is a Quadratic Residue, then the Legendre Symbol is 1. Thus:

$$ a^{\frac{p-1}{2}} \equiv 1 \pmod p$$

If we substitute the form of $p = 4k + 3$ we get:

$$ a^{\frac{4k+3-1}{2}} \equiv a^{\frac{4k+2}{2}} \equiv a^{2k+1} \equiv 1 \pmod p$$

which in turn implies:

$$ a^{-2k} \equiv a \pmod p \implies (a^{-k})^2 \equiv a \pmod p $$

Therefore, one of the square roots of $a$ bust be $a^{-k}$. Therefore I am suspecting that somehow either $x = a^{-k}$ is the same as $a^{k+1}$ or $a^{k+1} = -x = -a^{-k}$. Not sure which one, but I will try to find out. I am so close!

$\endgroup$

2 Answers 2

1
$\begingroup$

From $a^{(p-1)/2}\equiv 1\pmod{p}$, by multiplying both sides by $a$ we get $$a^{(p+1)/2}\equiv a\pmod{p}.\tag{1}$$

But $\frac{p+1}{2}=2k+2$. Thus from (1) we have $(a^{k+1})^2\equiv a\pmod{p}$.

$\endgroup$
1
$\begingroup$

Since $a$ is a quadratic residue there is a $b$ so that $a\equiv b^2$.

Now notice $(a^{k+1})^2\equiv a^{2k+2} \equiv (b^2)^{2k+1}\equiv b^{4k+4} \equiv b^{4k+3}b\equiv b^p b$.

Fermat's little theorem tells us $b^p\equiv b$ and so $b^pb\equiv bb\equiv b^2 \equiv a$.

Which is what we wanted to prove (that $a^{k+1}$ is a square root of $a$ is the same thing as saying $(a^{k+1})^2\equiv a$).

$\endgroup$
3
  • $\begingroup$ I can't follow. Do you mind writing more details? $\endgroup$ Commented Dec 10, 2015 at 21:03
  • 1
    $\begingroup$ I wrote more details, please tell me if something is unclear. $\endgroup$
    – Asinomás
    Commented Dec 10, 2015 at 21:35
  • $\begingroup$ that makes sense! Nice! Thanks! $\endgroup$ Commented Dec 10, 2015 at 21:41

You must log in to answer this question.

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