The theory of numbers, by Robert D. Carmichael ...

THE THEOREMS OF FERMAT AND WILSON

59

We shall now prove the following more complete theorem,
without the use of I or II.
III. If p is an odd prime number and a is an integer not
divisible by p, then a is a quadratic residue or a quadratic nonresidue modulo p according as
a(p —1) +I or a~(p)= -i mod p.
This is called Euler's criterion.
Given a number a, not divisible by p, we have to determine
whether or not the congruence
x2 -a mod p
has a solution. Let r be any number of the set
I, 2, 3,..., p-I (A)
and consider the congruence
rx=a mod p.
This has always one and just one solution x equal to a number
s of the set (A). Two cases can arise: either for every r of the
set (A) the corresponding s is different from r or for some r
of the set (A) the corresponding s is equal to r. The former
is the case when a is a quadratic non-residue modulo p; the
latter is the case when a is a quadratic residue modulo p. We
consider the two cases separately.
In the first case the numbers of the set (A) go in pairs such
that the product of the numbers in the pair is congruent to a
modulo p. Hence, taking the product of all 1 (p-i) pairs,
we have
I -2-3... p- I '+(P -t ) mod p.
But
I 2 3... p-i:-i mod p.
Hence
whence the truth of one art of the theore
whence the truth of one part of the theorem.