Square root of -1 (mod p)

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

a²=-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)

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)

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.