234 HlSTOEY OF THE THEORY OF NuMBEES. [CHAP. VIII
introduced in a way free from any logical objections. Avoiding their use, Gauss began his investigation by showing that two polynomials in x with integral coefficients have a greatest common divisor modulo p, which can be found by Euclid's process. It is understood throughout that p is a prime (cf. Maser, p. 627). Hence if A and B are relatively prime polynomials modulo p, there exist two polynomials P and Q such that
PA+QB^l (modp).
Thus if A has no factor in common with B or C modulo p, we find by multiplying the preceding congruence by C that A has no factor in common with the product BC modulo p. If a polynomial is divisible by A} B, C, . . ., no two of which have a common factor modulo p, it is divisible by their product.
A polynomial is called prune modulo p if it has no factor of lower degree modulo p. Any polynomial is either prime or is expressible in a single way as a product of prime polynomials modulo p. The number of distinct polynomials xn+axn"l+ . . . modulo p is evidently pn. Let (n) of these be prime functions. Then pn=2d(d), where d ranges over all the divisors of n (only a fragment of the proof is preserved). It is said to follow easily from this relation that, if n is a product of powers of the distinct primes a, 6,..., then
n(ri)=pn-2pn/a+2pn/ab- ....
The rth powers of the roots of an equation P = 0 with integral coefficients are the roots of an equation PT=0 of the same degree with integral coefficients. If T is a prime, PT=P (mod r).
A prime function P of degree m, other than x itself, divides x"— 1 for some value of v<pm. If v is the least such integer, v is a divisor of pm-]. Hence P divides
(1) a""1-1-!.
The latter is congruent modulo p to the product of the prime functions, other than x, whose degrees are the various divisors of m.
If P = xm-Axm~~1+Bxm~2— ... is a prime function modulo p, the remainders by dividing the sum, the sum of the products by twos, etc., of
by P are congruent to A, B, etc., respectively.
If v is not divisible by p and if m is the least positive integer for which pm==l (mod v), each prime function dividing xv — l modulo p is a divisor of (l} and its degree is therefore a divisor of m. Let 5 be a divisor of m, and d'} 5 "5-. . . the divisors <5 of <5; let p. be the g. c. d. of v and p5— 1, M' the g. c. d. of v and p*' — 1, . . . and set \f =ju/V, X" =/Z/M"> .... Then the number of prime divisors modulo p of degree d of xv — 1 is N/8, if N is the number of integers </z which are divisible by no one of A', A", . . .. A method of finding all prime functions dividing x" — 1 is based on periods of powers of x with exponents < v and prime to v (pp. 620-2).