The **Square root (mod p)** of *n* is a number (or more properly, residue class), *a*, that solves the equation

- a
^{2}=*n*(mod*p*).

If *n* is a quadratic residue (mod p), which just means if *n* is the square of some number (mod p), then the Shanks-Tonelli algorithm can find the number whose square is *n*.

## Special cases: square root of -1Edit

*Main article: Square root of -1 (mod p)*

We shall see that the square root of -1 (mod p) exists, as long as p is of the form 4k+1. Fermat's little theorem tells us that all the elements of {1, 2, ..., *p*-1} are roots of the polynomial x^{p-1}−1 = 0 (mod p). We can factor

- x
^{p-1}−1 = (x^{(p-1)/2}+1)(x^{(p-1)/2}−1),

each factor of which has at most (p-1)/2 roots, and together having exactly p-1 roots, so each factor has exactly (p-1)/2 roots, assuring not just the existence but the plentiful supply of such an *x* where x^{(p-1)/2}=-1, so the square roots of -1 are ±*x*^{(p-1)/4}.