64 HlSTDKY OF THE THBOKY OF NlJMBEBS. [CHAP. Ill
From the (p - 1) th order of differences for xp~l — 1 ,
Set x=l and use Fermat's theorem. Hence l+(p-l)! is divisible by p. E. Waring,16 1782, 380-2, made use of
x-l). . .(s-r+2)
where P=l+2+ . . . +(r-l), Q=PAl-B, etc., B denoting the sum of the products of 1, 2,..., r-1 two at a time, and A1 = l+2+. . .+(r— 2). Then
s. . .(z-r+2)
T — J
Take r=x and let z+1 be a prime. By Fermat's theorem, 1*, 2V . ., of each has the remainder unity when divided by x +1, so that their sum has the remainder x. Thus l+x\ is divisible by x+1.
Genty24 proved the converse of Wilson's theorem and noted that an equivalent test for the primality of p is that p divide (p— w)!(n— 1)! — (-l)n. For n=(p-f l)/2, the latter expression is {(£j!)!}2=fcl [Lagrange18]. Franz von Schaffgotsch25 was led by induction to the fact (of which he gave no proof) that, if n is a prime, the numbers 2, 3, . . . , n— 2 can be paired so that the product of the two in any pah* is of the form xn+1 and the two of a pair are distinct. Hence, by multiplication, 2-3...(n— 2) has the remainder unity when divided by n, so that (n— 1)! has the remainder n— 1. For example, if n=19, the pairs are 2-10, 4-5, 3-13, 7-11, 6-16, 8-12, 9-17, 14-15. Similarly, for n any power of a prime p, we can so pah* the integers <n— 1 which are not divisible by p. But for n=15, 4 and 4 are paired, also 11 and 11. Euler26 had already used these associated residues (residua sociata).
F. T. Schubert260 proved by induction that the nth order of differences of F, 2n,....isn!.
A. M. Legendre27 reproduced the second proof by Euler12 of Fermat's theorem and used the theory of differences to prove (2) for a = x. Taking z=p— 1 and using Fermat's theorem, we get (p-l)!=(l — l)p — 1 (mod p).
**Histoire et m6m. de Tacad. roy. sc. iasc. de Toulouse, 3, 1788 (read Dec. 4, 1783), p. 91.
»Abhandlungen d. Bohmischen Gesell. Wiss., Prag, 2, 1786, 134.
»Opusc. anal., 1, 1783 (1772), 64, 121; Novi Comm. Ac. Petrop., 18, 1773, 85, §26; Comm.
Axith. 1, 480, 494, 519.
'"Nova Acta Acad. Petrop., 11, ad annum 1793, 1798, mem., 174-7. "The'orie des nombres, 1798, 181-2; ed. 2, 1808, 166-7.