Prove that if $a$ is a quadratic residue of $p$ where $p \equiv 3 \pmod 4$ then the quadratic congruence
$$ x^2 \equiv a \pmod p $$
has the solutions
$$ x \equiv \pm a^{\frac{p+1}{4}} \pmod p $$
Solve the following quadratic congruences (all moduli are prime):
(a) $x^2 \equiv 3 \pmod {83}$
(b) $x^2 \equiv 2 \pmod {2^{13}-1}$
(c) $x^2 \equiv 5 \pmod {127}$
We're given $a$ is a quadratic residue of prime $p$. By Euler's Criterion we have
$$ a^{\frac{p-1}{2}} \equiv 1 \pmod p$$
We can multiply through by $a$ because $p \not \mid a$,
$$ a^{\frac{p+1}{2}} \equiv a \equiv x^2 \pmod p$$
And so by proposition (3.14b)
$$ x \equiv \pm a^{\frac{p+1}{4}} \pmod p$$
We need to ensure the index $\frac{p+1}{4}$ is an integer. Since $p \equiv 3 \pmod 4$, then for some integer $k$ we have $p=4k+3$, and so $\frac{p+1}{4} = \frac{4k+4}{4} = k+1$, an integer.
And so $ x^2 \equiv a \pmod p $ has solutions $ x \equiv \pm a^{\frac{p+1}{4}} \pmod p $ for $p \equiv 3 \pmod 4$.
(a) We first check that 3 is a quadratic residue of 83, using Euler's Criterion (7.5).
$$ 3^{\frac{83-1}{2}} \equiv 3^41 \equiv (3^8)^5 \times 3 \equiv 4^5 \times 3 \equiv 1 \pmod {83} $$
So 3 is a quadratic residue of 83.
Because $83 \equiv 3 \pmod 4$, the above result gives us
$$ x \equiv \pm 3^{\frac{83+1}{4}} \equiv \pm 3^21 \equiv \pm 70 $$
That is, $x \equiv 13 \pmod {83}$ and $x \equiv 70 \pmod {83}$.
(b) We first check that 2 is a quadratic residue of $2^{13}-1$, using Euler's Criterion (7.5).
$$ 2 ^ {\frac{2^{13}-1 -1}{2}} \equiv 2 ^ {2^{12}-1} \equiv 2^{4095} \pmod {2^{13}-1}$$
We note that $2^{13} \equiv 1 \pmod {2^{13}-1}$ and so 2 is a quadratic residue of $2^{13}-1$
$$ 2^{4095} \equiv (2^{13})^{315} \equiv 1^{315} \equiv 1 \pmod {2^{13}-1}$$
Because $2^{13}-1 \equiv 3 \pmod 4$, the above result gives us
$$ x \equiv \pm 2^{\frac{2^{13}-1+1}{4}} \equiv \pm 2^{2048} \equiv (2^{13})^157 \times 2^7 \equiv 128 $$
That is, $x \equiv 128 \pmod {2^{13}-1}$ and $x \equiv 8063 \pmod {2^{13}-1}$.
(c) We first check 5 is a quadratic residue of 127, by Euler's Criterion.
$$ 5^{\frac{127-1}{2}} \equiv 5^63 \equiv (5^7)^9 \equiv 20^9 \equiv -1 \pmod {127} $$
This means the congruence has no solutions.