# Characterization of the solutions to $x^2 \equiv a \ (\text{mod} \ p),$ where $p=8n+5$ is a prime.

If $$a$$ is a quadratic residue of the prime $$p= 8n+5,$$ then the solutions of $$x^2 \equiv a \ (\text{mod} \ p)$$ are $$x \equiv \pm a^{n+1}$$ or $$\pm 2^{2n+1}a^{n+1} \ (\text{mod} \ p)$$

I have shown that $$x \equiv \pm a^{n+1}$$ or $$\pm 2^{2n+1}a^{n+1} \ (\text{mod} \ p)$$ are the possible solutions. How do I show they are all the possible solutions? Appreciate any advice, thank you.

$$(\mathbb{Z}/p\mathbb{Z})^\times$$ is cyclic of order $$p-1$$, generated by $$b$$ say. Let $$a=b^n$$ and $$x=b^m$$. Then $$2m$$ must agree with $$n$$, mod $$p-1$$. If $$n$$ is even then divide through by 2, so $$m=n/2$$ or $$n/2+(p-1)/2$$. If $$n$$ is odd then there is no solution. So either way there can't be more than two.
• One really should justify why there cannot be more than $2$ solutions since that is the heart of the matter. Simply stating that it is true is far from a proof. Nov 8, 2018 at 15:06
• Let $x=b^m$ say. Then $2m=n \bmod p-1$. Nov 8, 2018 at 15:11
• Well done. +1  Nov 8, 2018 at 15:24