Find $\sqrt 7 \pmod {2579}$

Question

Find $\sqrt 7 \pmod {2579}$.

I think I understand how I would solve a very basic equation like this:

$x^2 = 1 \pmod 5$

make a table of all the possible solutions like this

$x=0 \implies x^2=0 \\ x=1 \implies x^2=1 \\ x=2 \implies x^2=4 \\ x=3 \implies x^2=4 \\ x=4 \implies x^2=1 \\ x=5 \implies x^2=0$

then take the ones that work. In this case $\pm 1$ and $\pm 4$ are the roots, but how do I do this with a huge prime that I can't list out all the possibilities for?

Answer 1

First, check that there are solutions for $x^2 \equiv 7 \bmod 2579 $ using Euler's criterion:

If $p$ is a prime that does not divide $a$, then
$\qquad x^2 \equiv a \bmod p$ has a solution $\iff a^{\tfrac{p-1}{2}} \equiv 1 \bmod p$.

We compute and see that $7^{\frac{2579-1}{2}} \equiv 1 \bmod 2579$.

Next, we find the solutions using a theorem of Lagrange, which is easily checked:

If $p \equiv 3 \bmod 4$ and $a$ is a quadratic residue mod $p$, then
$\qquad$ the solutions of $x^2 \equiv a \bmod p$ are $x \equiv \pm a^{\frac{p+1}{4}} \bmod p$.

This theorem applies because $2579 \equiv 3 \bmod 4$ and $7$ is a quadratic residue mod $2579$, as above.

So, we compute $7^{645} \equiv 88 \bmod 2579$ and so the solutions are $\pm 88 \bmod 2579$.