History Of The Theory Of Numbers - I

206 HlSTOKY OF THE THEORY OF NUMBERS. [CHAP. VII
Since In' — qp' = 1 , the first gives Bqp'z= I . Hence
BP> = £PW-SP') « (£py/(B«>y = ! (mod p) .
Conversely, if £p'=l,
re"-1- l=xp'u-Bp'1 (mod p)
has the factor xa—Blj so that (Lagrange3) congruence (2) has co roots.
If 4n divides p — 1, the roots of ^2ft= —1 (mod p) are the odd powers of an integer belonging to the exponent 4n modulo p.
Let n divide p — 1, and m divide (p~l)/n. Let co be the g. c. d. of m, n and set n = COP. Determine positive integers I and g such that lv — qm = l. If #m===fcl (mod p), (1) is satisfied by the roots of x"=Bly (mod p), where i/ ranges over the roots of y"= (=*= I)3 (mod p). For, the last two congruences give
xn = xv"=Bvlyv=Bqm+1(±l)q=B (mod p).
Hence by means of the roots of #'===*= 1, we reduce the solution of (1) to binomial congruences of lower degrees. In particular, let n — 2, m — (p — 1)/2, and let 2 be prime to m, so that p =4a— 1, £ = a, <? = 1. Then x2==B (mod p) requires that J3m = l, so that we have the solutions x^^=Ba without trial (Lagrange153). Next, if n=2 and £2*+1= -1, the theorem gives xz=Bk+ly, where y2 = — 1 . But we may generalize the last result. Consider x2 + c2 = 0 (mod p). Since p must have the form 4a+l, we have p—f+g2. Determine u and 2; so that c — gu—pz. Then x^==fu (mod p).
Let a belong to the exponent nw modulo p, where w divides (p — l)/n. Then the roots of Bw = l (mod p) are B = an» (p, = l, . . ., w~~l), and, for a fixed E, the roots of (1) are z = amu)+M (m = 0, 1, . . ., n — 1). For, an belongs to the exponent w, whence J3=anM.
Legendre155 gave the same theorems in his text. He added that, knowing a root 6 of (1), it is easy to find a root of xn^B (mod pa), with the possible exception of the case in which n is divisible by p. Let 6n—B = Mp and set x = 6 -{-A p. Then xn—B is divisible by p2 if
which can be satisfied by integers A, M' if n is not divisible by p. To solve (1) when p is composite, p = aab0 . . . , where a, b> . . . are distinct primes, determine all the roots X of \n = B (mod aa), all the roots ju of /xns=£ (mod 65), ____ Then if ZE=A (mod aa), z=ju (mod 6"), . . ., x will range over all the roots of (1).
Legendre156 noted that if p is a prime 8n-!-5 we can give explicitly the solutions of x2+a = 0 (mod p) when it is solvable, viz., when a'hi4"2= 1. For, either a2ri+1-fl=0 and x = anJrl is a solution, or a2n+1-l = 0 and 6 = an+1 satisfies 02 — a = 0 (mod p), so that it remains only to solve x'2-\-6'2^0, which was done at the end of his154 memoir. For p = 8n+l3 let n = a/3, where a is a power of 2 and ff is odd; if aP=**l, x2-{-a = Q can be solved as in the
1S6Th6orie des nombres, 1798, 411-8; ed. 2, 1808, 349-357; ed. 3, 1830, Noa. 339-351; German
transl. by Maser, 1893, 2, pp. 15-22. ™Ibid., 231-8; ed. 2, 1808, pp. 211-219; Maser, I, pp. 246-7.