HISTORY OF THE THEOKY OF NUMBERS. [CHAP, vm
R. Dedekind71 developed the subject of higher congruences by the methods of elementary number theory without the use of algebraic principles. As by Gauss60 he developed the theory of the g. c. d. of functions modulo p, a prime, and their unique factorization into prime (or irreducible) functions, apart from integral factors. Two functions A and B are called congruent modulis p, M, if A— B is divisible by the function M modulo p. We may add or multiply such congruences. If the g. c. d. of A and B is of degree d, Ay^B (mod p, M) has pd incongruent roots y(x) modulis p} M.
Let <t>(M) denote the number of functions which are prime to M modulo p and are incongruent modulis p, M. Let /i be the degree of M. A primary function of degree a is one in which the coefficient of x* is = 1 (mod p). If D ranges over the incongruent primary divisors of M, then 2<£(D)=p". If M and N are relatively prime modulo p, then </>(MN) ==<£(M)<£(]V). If A is a prime function of degree a, <t>(Aa) =pao(l - l/p°) . If M is a product pf powers of incongruent primary prime functions a, . . . , p,
If P is prime to M modulo p} F*(M)=\ (mod p, M), which is the generalization of Fermat's theorem. Hence if A is prime to M, the above linear congruence has the solution y^BA*"1.
If P is a prime function of degree x, a congruence of degree n modulis p, P has at most n incongruent roots. Also
(3) y>'-l-lmH(y-F) (mod p, P),
identically in y} where F ranges over a complete set of functions incongruent modulis p, P and not divisible by P. In particular, 1+IIF=0 (mod p, P), the generalization of Wilson's theorem.
There are 0(pr— 1) primitive roots modulis p, P. Hence we may employ indices in the usual manner, and obtain the condition for solutions of yn^A (mod p, P), where A is not divisible by P. In particular, A is a quadratic residue or non-residue of P according as
ACp*-1)/2= + l or -1 (mod p, P).
His extension of the quadratic reciprocity law will be cited under that topic. A function A belongs to the exponent p with respect to the prime function P of degree IT if p is the least positive integer for which App=A (mod p, P). Evidently p is a divisor of TT. Let N(p) be the number of incongruent functions which belong to an exponent p which divides TT. Then pf> = 'ZN(d), where d ranges over the divisors of p. By the principle of inversion (Ch. XIX),
where a, 6, ... are the distinct primes dividing p. Since the quotient of this sum by its last term is not divisible by p, we have N(p)>0.
"Jour, fttr Math., 54, 1857, 1-26.