History Of The Theory Of Numbers - I

CHAP. VII] BINOMIAL CONGRUENCES. 205
as those of the term ymn~n for y=l,..., mn, and hence equal (mri—n)!, so that Q(y) is not divisible by p for some values 1,..., mn of #.
Euler152 recurred to the subject. The main conclusion here and from his former paper is the criterion that, if p=wn+1 is a prime, xn==a (mod p) has exactly n roots or no root, according as a"*=l (mod p) or not. In particular, there are just ra roots of aw=l, and each root a is a residue of an nth power.
Euler152a stated that, if a^+6=p2, all the values of x making ax+5 a square are given by x= ay*=*=2py+q.
J. L. Lagrange153 gave the criterion of Euler, and noted that if p is a prime 4n+3, J?(p~1)/2-l is divisible by p, so that x=Bn+l is a root of x2=B (mod p). Given a root £ of the latter, where now p is any odd prune not dividing B, we can find a root of x2^B (mod p2) by setting x = £+Xp, £2-£=pco. Then x2-B=(\2+fj,)p2 if 2£X+co=/ip. The latter can be satisfied by integers X, ^ since 2£ and p are relatively prime. We can proceed similarly and solve x2=B (mod pn).
Next, consider £2=J3 (mod 2n), for n>2 and B odd (since the case B even reduces to the former). Then £ = 22+1, £2—B=Z-}-I— B, where Z=42(2+1) is a multiple of 8. Thus l—B must be a multiple of 8. Let ra>3 and l-.B = 2r/3, r>3. If r^n, it suffices to take z = 2n~2f, where £ is arbitrary. If r<n, Z must be divisible by 2r, whence z = 2r~2f or jr~2f—1. Hence w=f(2r~2f±l)+^ must be divisible by 2n~r. If n-r^r-2, it suffices to take f ±0 divisible by 2n~r. The latter is a necessary condition if n-r>r-2. Thus f = 2r-2/> =F& w = 2r-2(f2=*=p). Hence f2=*=p must be divisible by 2w~2r+2. We have two sub-cases according as the exponent of 2 is ^ or >r —1; etc.
Finally, the solution of x2=B (mod m) reduces to the case of the powers of primes dividing m. For, if / and g are relatively prime and £2 — B is divisible by /, and \l/2 — B by g, then z2—B is divisible by fgiix—ju/=*= % = vg*=\t/. But the final equality can be satisfied by integers /-t, *> since / is prime to g.
A. M. Legendre154 proved that if p is a prime and w is the g. c. d. of n and p — 1 =cop/, there is no integral root of
(1) xn=B (mod p)
unless $P'E= 1 (mod p); if the last condition is satisfied, there are co roots of (1) and they satisfy
(2) xu=Bl (mod p), where I is the least positive integer for which
(3) ln-q(p-I)=a>.
For, from (1) and x*~ls*l, we get xln=Bl, xff(p~1}=l, and hence (2), by use of (3). Set n = con'. Then, by (2) and (1),
Bn'l=xn^B, Bp>lzExp'»=xp-l=l (mod p).
1MNovi Comm..Petrop., 8, 1760-1, 74; Opusc. Anal. 1, 1772, 121; Comm. Arith., 1, 274, 487. 152aOpera postuma, 1, 1862, 213-4 (about 1771).
»'M6m. Acad. R. Sc. Berlin, 23, ann6e 1767, 1769; Oeuvres, 2, 497-504. . Ac. R. Sc. Paris, 1785, 468, 476-481. (Cf. Legendre.155)