CHAP. VIII] HlGHEB CONGRUENCES, GALOIS IMAGINABIES. 237
F(x) is irreducible modutis p, a. Hence if m is a divisor of pw— 1, and if g(a) is a primitive root of ' .
x*""1?-! (mod p, a),
and if k is prime to m, then xm—gk is irreducible modulis p, a.
If F(x, a) is irreducible modulis p, a, and if at least one coefficient satisfies
x**~l:= 1 (mod p, a) if and only if v is a multiple of n, then
t(x)=niL F(x, a^) (mod p, a)
J-O
has integral coefficients and is irreducible modulo p.
If G(x) is of degree ran and is irreducible modulo p} and G(a) = 0, algebraically, and if r(a) is a primitive root of x*mn= 1 (mod p, a), then
has integral coefficients and is irreducible modulo p.
The last two theorems enable us to prove the existence of irreducible congruences modulo p of any degree. First,
is the product of the irreducible functions of degree pn modulo p. To prove the existence of an irreducible function of degree lpn, where I is any integer prime to p, assume that there exists an irreducible function of each degree <Zpn, and hence for the degree a~Apn, where A=<t>(l)<l Let a be a root of the latter, and r a primitive root of £•**""" *= 1 (mod p, a), where P=p°. Since I divides P— 1 by Euler's generalization of Fermat's theorem, xl~~r is irreducible modulis p, a. Hence by the theorem preceding the last, Jlfy(xl — r^) is irreducible modulo p. Since its degree is lpnA, the last theorem gives an irreducible congruence of degree lpn.
Every irreducible factor modulo p of xpn~~l — 1 is of degree a divisor of n. Conversely, every irreducible function of degree a divisor of n is a factor of that binomial. If n is a prune, the number of irreducible functions modulo p of degree nv is (pn"~ pn"" )/n". If n is a product of powers of distinct primes A, B,. . ., say four, the number of irreducible congruences of degree n modulo p is
t _L.pCD__pA__ —PD\
where P = pn/(ABCD\ Replacing p by pro, we get the number of irreducible congruences of degree n modulis p, a, where a is a root of an irreducible congruence of degree m.
If n is a prime and p belongs to the exponent e modulo n, f = (xn — • 1 ) / (x — 1 ) is congruent modulo p to the product of (n — l)/e irreducible functions of