236 HlSTOBY OF THE THEOBY OF NuMBEBS. [CHAP. VIII
congruences modulo p are of the form a+b-\/n, where n is a fixed quadratic non-residue of p, while a, b are integers. But the cube root of a non-cubic residue is not reducible to this form a+b\/n. The p+l sets of integral solutions of y2—nz*=a (mod p) yield the p+l real or imaginary roots x^y+zVn of x^zza (mod p). The latter congruence has primitive roots if a = l.
Th. Schonemann64 built a theory of congruences without the use of Euclid's g. c. d. process. He began with a proof by induction that if a function is irreducible modulo p and divides a product AB modulo p, it divides A or B. Much use is made of the concept norm Nfv of f(x) with respect to <i>(x), i. e., the product /(&).. ./(/3m), where ft,..., pm are the roots of </>(#) = 0; the norm is thus essentially the resultant of / and <£. The norm of an irreducible function with respect to a function of lower degree is shown by induction to be not divisible by p. Hence if / is irreducible and Nf^O (mod p), then/ is a divisor of <t> modulo p. A long discussion shows that if ai,..., an are the roots of an algebraic equation f(x) = xn+... =0 and if f(x) is irreducible modulo p, then njll-jz—0(a,-)f is a power of an irreducible function modulo p.
If a is a root of f(x) and f(x) is irreducible modulo p, and if <j>(a) =^(a)+p#(a); we write <t>^$ (mod p, a); then $(x)—\l/(x) is divisible by f(x) modulo p. If the product of two functions of a is =0 (mod p, a), one of the functions is =0.
If f(x) = xn+ ... is irreducible modulo p and if /(a) = 0, then
/(a;)== (z-a)(s-ap)... (s-a^"1), a^s 1 (mod p, a),
a;""-1-! =PE te-*,(a)J (mod p, a),
where <& is a polynomial of degree n— I in a with coefficients chosen from 0, 1,..., p —1, such that not all are zero. There exist </>(pn—1) primitive roots modulis p, a, i. e., functions of a belonging to the exponent pn—1.
Let F(x) be irreducible modulis p, a, i. e., have no divisor of degree 2>1 modulis p, a. Let F(fi) =0, "algebraically. Two functions of /? with coefficients involving a are called congruent modulis p, a, ft if their difference is the product of p by a polynomial in a, /3. It is proved that
F(*)e (z-0)(a;-/3'n).. - (x-p*-1*), /3^"-l (mod p, o, 0).
If y<w, n being the degree of/(x), and if the function whose roots are the (pF—l)th powers of the roots of f(x) is ^0 (mod p) for z = l, then/(a) is irreducible modulo p. Hence if m is a divisor of p — 1 and if g is a primitive root of p, and if k is prime to m, then xm—gk is irreducible modulo p.
If i><m, m being the degree of F(x), and if the function whose roots are the (pw—l)th powers of the roots of F(x) is ^0 (mod p, a) for z = l, then
MGnindzlige einer allgemeinen Theorie der hohern Congnienzen, deren Modul eine reelle Primzahl iat, Progr., Brandenburg, 1844. Same in Jour, far Math., 31, 1846, 269-325.