66 HISTORY OF THE THEORY or NUMBERS. [CHAP, in J. A. Grunert36 considered the series to which Euler's (3) reduces for a==n, x=m, and proved that [m, n]=n{[ra-l, n-l]+[m-l, n]}. This recursion formula gives [w,n] = 0 (m = 0, l,...,n-l); [n, n]=n! [cf. (2)], 4 A Any [m, n] is divisible by n !. As by the proof of Lagrange,18 [m, n] + ( — l)n is divisible by m+1 if the latter is a prime >n. Again, mlhm=(x+mhr-m\x+(m-l)h\"+(^) \x+(m-2)h\m+ . . .+(-l)m^m, which for x=0, /i=l, gives [m, 7w]=m!. W. G. Horner37 proved Euler's theorem by generalizing Ivory's33 method. If TI, . . . , rv are the integers <m and prime to m, then r^N, . . . , r^N have the r's as their residues modulo m. P. F. Verhulst38 gave Euler's proof22 in a slightly different form. F. T. Poselger39 gave essentially Euler's10 first proof. G. L. Dirichlet40 derived Format's and Wilson's theorems from a common source. Call m and n corresponding numbers if each is less than the prime p and if mn=a (mod p)3 where a is a fixed integer not divisible by p (thus generalizing Euler's26 associated numbers). Each number 1, 2,. . ., p — 1 has one and but one corresponding number. If z2=a (mod p) has no integral solution, corresponding numbers are distinct and (p-l)!=a(p-1)/2 (modp). But if k is a positive integer <p such that P=a (mod p), the second root is p-k, and the product of the numbers 1, . . . , p — 1, other than k and p—k, has the same residue as a(p~3)/2, whence The case a=l leads to Wilson's theorem. By the latter, we have _ qfr-^gsfcl (modp), _ ''Math. Abhandlungen, Erste Sammlung, Altona, 1822, 67-93. Some of the results were quoted by Grunert, Archiv Math. Phys., 32, 1859, 115-8. For an interpretation in factoring of [m, n], see Minetola160 of Ch. X. "Annals of Phil. (Mag. Chem. . . .), new series, 11, 1826, 81. 38Corresp. Math. Phys. (ed. Qu&elet), 3, 1827, 71. "Abhand. Ak. Wiss. Berlin (Math.), 1827, 21. "Jour, fur Math., 3, 1828,. 390; Werke, 1, 1889, 105. Dirichlet,88 §34.