CHAP. VIII] HlGHEE CONGRUENCES, GALOIS IMAGINARIES. 235 If X has been expressed as a product of relatively prime factors modulo p, we can express X as a product of a like number of factors mod pn congruent to the former factors modulo p. There is a fragment on the case of multiple factors. C. G. J. Jacobi61 noted that, if q is a prune 6^—1, za+1=l (mod q) has q— 1 imaginary roots a +&V— 3, where a +362=1 (modq), besides the roots =fcl. E. Galois62 employed imaginary roots of any irreducible congruence F(o;)=0 (mod p), where p is a prune. Let i be one imaginary root of this congruence of degree v. Let a be one of the p"— 1 expressions in which the a's are integers <p, not all zero. Since each power of a can be expressed as such a polynomial, we have an = 1 for some positive integer n. Let n be a minimum. Then 1, a, . . . , a""1 are distinct. Multiply them by a new polynomial /3 in i; we get n products distinct from each other and from the preceding powers of a. If 2n<p" — 1, we use a new multiplier, etc. Hence n divides p"— 1, and (2) a^-^l. [This is known as Galois's generalization of Format's theorem.] It follows that there exist primitive roots a such that a* 7*1 if e<pv — 1. Any primitive root satisfies a congruence of degree v irreducible modulo p. Every irreducible function F(x) of degree v divides xpV~ x modulo p. Since \F(x)\ pn=F(xpn) modulo p, the roots of F(x)ssQ are All the roots of xp"=x are polynomials in a certain root i, which satisfies an irreducible congruence of degree v. To find all irreducible congruences of degree v modulo p, delete from xpV — x all factors which it has in common with xptL-~x, n<v. The resulting congruence is the product of the desired ones; the factors may be obtained by the method of Gauss, since each of their roots is expressible in terms of a single root. In practice, we find by trial one irreducible congruence of degree v, and then a primitive root of (2); this is done for p = 7, z> = 3. Any congruence of degree n has n real or imaginary roots. To find them, we may assume that there is no multiple root. The integral roots are found from the g. c. d. of F(x) and rcp~1 — 1. The imaginary roots of the second degree are found from the g. c. d. of F(x) and re*5"1 — !; etc. V. A. Lebesgue63 noted that, if p is a prime, the roots of all quadratic "Jour, fur Math., 2, 1827, 67; Werke, 6, 235. MSur la thgorie des nombree, Bulletin des Sciences Mathe*matiques de M. Ferussac, 13, 1830, 428. Reprinted in Jour, de Math6matiques, 11, 1846, 381; Oeuvres Math. d'Evariste Galois, Paris, 1897, 15-23; Abhand. Alg. Gleich. Abel u. Galois, Maser, 1889, 100. "Jour, de Mathe'matiques, 4, 1839, 9-12.