Some history: Wilson and Lagrange 

Here I have to move quickly (in fact I'll simply have to fly through this section), and attempt not to get too involved in covering standard material (of a type that I covered last November 2004 with my 2nd year BEd and BA students).  

The essential point about Wilson and Lagrange is that they discovered fundamental connections 

in Wilson's case between the residues in the full set of non-zero residues for a prime p 

in Lagrange's case between the residues in the two natural half-sets of non-zero residues for a prime p 

First the classic theorem of Wilson (of which there are many, many proofs, including one-and-a-half of my own (published in 1967)): 

Wilson's theorem (first proved by Lagrange in 1777). For p prime one has (mod p). 

Note. The converse of Wilson's theorem: 

if (mod n), then n is prime 

is a complete triviality (however, should polynomial time factorial modular computation ever become a reality then that would be a different matter!). 

Numerical examples (here I am interested only in demonstration, not in fancy footwork; in short, I want you to see the potential size of the numbers involved).  

>	p := 37; # a prime, of course (p-1)!; # the actual value of the factorial (p-1)! mod p; # the normal remainder mods((p-1)!, p); # the least absolute remainder

 

(4.1)

 

(4.1)

 

(4.1)

 

(4.1)

 

>	p := 39; # NOT a prime (p-1)!; # the actual value of the factorial (p-1)! mod p; # the normal remainder mods((p-1)!, p); # the least absolute remainder

 

(4.2)

 

(4.2)

 

(4.2)

 

(4.2)

 

>	p := nextprime(1234); # a prime (p-1)!; # the actual value of the factorial (p-1)! mod p; # the normal remainder mods((p-1)!, p); # the least absolute remainder

 

(4.3)

 

(4.3)

 

(4.3)

 

(4.3)

 

>

 

Lagrange besides publishing the first proof of Wilson's theorem in 1777, published some important related work: he proved - using Wilson's theorem - important distinctions (discovered by Fermat, who could not provide proofs) between the way in which primes leaving remainders 1 and 3 on division by 4 behaved. 

Briefly, Fermat had observed (in equivalent non-congruence language; congruence notation only came in with Gauss in his monumental Disquisitiones Arithmeticae (1801)) that 

the quadratic congruence (mod p) has no solutions for prime p satisfying p = 3 (mod 4)  

the quadratic congruence (mod p) has exactly two solutions for prime p satisfying p = 1 (mod 4) 

Numerical illustrations. 

>	p := nextprime(1000); p mod 4; msolve(x^2 + 1 = 0, p);

 

(4.4)

 

(4.4)

 

(4.4)

 

>	p := nextprime(2000); p mod 4; msolve(x^2 + 1 = 0, p);

 

(4.5)

 

(4.5)

 

>

 

Suffice it to say that Lagrange noted the following (trivially-derived) consequence of Wilson's theorem: 

               (mod p)       (Lagrange congruence) 

(you see why, of course? Use (mod p), for , and...) 

In summary, this is what one had: 

For prime p = 3 (mod 4), (mod p).

It should be noted that a consequence of that was that either or -1 (mod p), and it was a long-standing unsolved problem for many years to determine the sign (see Dec 15th 2004 email from Andrew Granville)   

For prime p = 1 (mod 4), (mod p), from which it is easily deduced that (mod p) has at least two solutions, and a further result of Lagrange's then allowed one to conclude there were exactly two solutions.