Skip to main content

Full text of "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 xaBlj 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 pf+g2. Determine u and 2; so that c  gupz. 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 6nB = Mp and set x = 6 -{-A p. Then xnB 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.