CHAPTER VII.
PRIMITIVE ROOTS, BINOMIAL CONGRUENCES. PKIMITIVE ROOTS, EXPONENTS, INDICES.
J. H. Lambert1 stated without proof that there exists a primitive root g of any given prime p, so that ge — I is divisible by p for e=p— 1, but not
L. Euler2 gave a proof which is defective. He introduced the term primitive root and proved (art. 28) that at most n integers x<p make xn—l divisible by p, the proof applying equally well to any polynomial of degree n with integral coefficients. He stated (art. 29) that, for n<p, xn—l has all n solutions "real" if and only if n is a divisor of p — 1 ; in particular, x**1 — 1 has p — 1 solutions (referring to arts. 22, 23, where he repeated his earlier proof of Fermat's theorem). Very likely Euler had in mind the algebraic identity xp~l — 1 = (xn— 1)Q, from which he was in a position to conclude that Q has at most n— p-\-I solutions, and hence xn — 1 exactly n. By an incomplete induction (arts. 32-34), he inferred that there are exactly 4>(ri) integers x<p for which xn— 1 is divisible by p, but x2 — 1 not divisible by p for 0<Z<n, n being a divisor of p — 1 (as the context indicates). In particular, there exist <t>(p — 1) primitive roots of p (art. 46). He listed all the primitive roots of each prime ^ 37.
J. L. Lagrange3 proved that, if p is an odd prime and
where Z, £, F are polynomials hi x with integral coefficients, and if xm and XM are the highest powers of x in X and £ with coefficients not divisible by p, there are m integral values, numerically <p/2, of x which make X a multiple of p, and M values making £ a multiple of p. For, by Fermat's theorem, the left member is a multiple of p for x = =*= 1, =*=2, . . . , =*= (p — 1)/2, while at most m of these values make X a multiple of p and at most /z make | a multiple of p.
L. Euler4 stated that he knew no rule for finding a primitive root and gave a table of all the primitive roots of each prime ^41.
Euler5 investigated the least exponent x (when it exists) for which fax+g is divisible by N. Find X such that —g=r\N is a multiple, say aar, of a. Then /ax~a-r is divisible by N. Set r^\'N = afis, 0^1. Then fax~a~^ — s is divisible by JV; etc. If the problem is possible, we finally get / as the residue of fax~°-~ •••"*", whence x = a+ . . . +f . For example, to find the least x for which 2X — 1 is divisible by N = 23, we have
l+23 = 233, 3-23= -225, -5-23= -227, -7+23 = 24l, whence x = 3+2+2+4 = ll.
Wova Acta Eruditorum, Leipzig, 1769, p. 127. »Novi Comm. Acad. Petrop., 18, 1773, 85; Comm. Arith., 1, 516-537. 8Nouv. M6m. Ac. Roy. Berlin, annexe 1775 (1777), p. 339; Oeuvrea 3, 777. 40pusc. Anal., 1, 1783 (1772), 121; Comm. Arith., 1, 506.
B0pusc. Anal., 1, 1783 (1773), 242; Comm. Arith., 2, p. 1; Opera postuma, I, 172-^.
181