# Full text of "History Of The Theory Of Numbers - I"

## See other formats

CHAP. VII] BINOMIAL CONGRUENCES. 211 ,.! (mod p). By taking ^=(lfc/1)2 and replacing 1 by (-l)fc+1 in 6(x-h) = l, the last results become the fundamental formula given without proof by Wronski169 in his Re" forme des Math&natiques. G. L. Dirichlet172 discussed the solution of #2=D for any modulus. G. F. Meyer173 gave an elementary discussion of the solution of ofefo (mod &), for k a prime, power of prime, or any integer. V. A. Lebesgue174 employed a prime p, a divisor n of p — l=nnf, and a number a belonging to the exponent n' modulo p. Then the roots of xn=za (mod p) are aa&*, where b is not in the period of a, and b is a quadratic non-residue of p if a is a quadratic residue, and bn is the least power of b congruent to a term of the period of a. If we set 6n=a" (mod p), then must na,+v($=l (mod n'). The roots x are primitive roots of p. In the construction of a table of indices, his method is to seek a primitive root giving to =t=2 the minimum index (rather than to =t=10, used by Jacobi); thus we use the theorem f or a — =*= 2. Lebesgue175 gave reasons why the conditions imposed on 6 in his preceding paper are necessary. He added that when we have found that xn^=a (mod p) leads to a primitive root x=g of p, it is easy to solve xm=r (mod p) when m divides p — 1, by expressing r as a power of g by the equivalent of an abridged table of indices. Lebesgue176 noted that the usual method of solution by indices leads to the theorem: If a belongs to the exponent e modulo p, and if n divides p — 1, and we set n = e'm, where e' has only prime factors which divide e, while m is prime to e, then, for every divisor M of m, xn = a (mod p) has e'<t>(M) roots belonging to the exponent M. If a belongs to the exponent e modulo p, there are e<t>(n) numbers 6, not in the period of a, for which bnz== a? (mod p), with n a minimum. A common divisor of n and i does not divide e. Then the n roots of xn= a (mod p) are a'6", where nt—iu — l~ev, t<e, u<n. This generalization of his174 earlier theorem is used to find the period of a primitive root of p from the period of 2. R. Gorgas177 stated that, if p is the residue modulo M of the pth term of \(M-l)/2\2, . . ., 22, 12, thenp(p-l) =p=fcm+Jlfa, according as Jlf = 4m=*=l. Take the lower signs and solve for p; we get 2p = ldb&, 62 = M(4a-l)+4p. Set 4p = Mc4-p'. Hence the initial equation x2 = My-\-p has been replaced by &2 = M(4a-fc — l)+p' of like form. Let p' be the p'th place from the end. The process may be repeated until we reach an equation P(P— 1) = MA+pm— m solvable by inspection. l72Zahlentheorie, 1863, §§32-7; ed. 2, 1871; ed. 3, 1879; ed. 4, 1894. 173Archiv Math. Phys., 43, 1865, 413-36. 174Comptes Rendus Paris, 61, 1865, 1041-4. "6/6id., 62, 1866, 20-23. 17«76id., 63, 1866, 1100-3. 177Ueber Losung dioph. Gl. 2. Gr., Progr., Magdeburg, 1867.