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

- a
^{2}=-1 (mod*p*),

as long as p is of the form 4k+1.
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}.

## Existence of square root of -1 (mod p)Edit

Fermat's little theorem tells us that the polynomial x^{p-1} − 1 = 0 (mod p) has p-1 solutions, namely {1, 2, ..., *p*-1}. If we let *h* be half this number, that is, *h*=(*p*-1)/2, then we can factor x^{p-1} − 1 as

- (x
^{h}+1)(x^{h}−1)

so at most *h* elements of {1, 2, ..., *p*-1} are roots of x^{h}+1=0, and at most *h* elements are roots of x^{h}−1=0. Since all elements are roots of one equation or the other, this means that exactly half the numbers, x, are roots of each equation. Thus the *existence* of a number, *x*, such that x^{h}=-1, is assured.

## Finding the square root of -1 (mod p)Edit

As a practical matter, random guessing will find such a number pretty quickly, in practice. By testing 2, then 3, then other small primes in succession, it won't be long before a number, *x*, is discovered such that x^{h}=-1. Then, since *h* is even, to find the square root of -1 (mod p), we just find x^{h/2}, which is one of the two square roots of -1. The other square root, of course, will be -x^{h/2}.