618 NUMBERS these y, then in the series of powers y, y" 2 , g . . . y p ~ l , the first term which is = 1 (mod.p) is yP~ l , that is, we have y, g 2 , yt, . . .yP-i = l, 2, 3, . . . p - 1 in a different order. Any such number y is said to be a prime root of p, and the number of prime roots is <$>(p - 1), the number of in tegers less than and prime to p - 1. The notion of a prime root was applied by Gauss to the solution of the binomial equation x c -1=0, or, what is the same thing, to the question of the division of the circle (Kreistheilung), see EQUATION, Nos. 30 and 31 (vol. viii., p. 507) ; and, as remarked in the introduction to the pre sent article, the roots or periods of roots of this equation present themselves as the units of a complex theory in the Theory of Numbers. 17. Any number x less than p is = y m , and, if m is not prime to p - 1, but has with it a greatest common measure e, suppose m = ke, p-l = ef, then x = g ke , a/= g l ^= g k(p ~ 1} = 1, that is, xf= 1 ; and it is easily seen that in the series of powers x, x~, . . . a/, we have xf as the first term which is = 1 (mod. p). A number =y m , where m is not prime to j)-l, is thus not a prime root; and it further appears that, y being any particular prime root, the <f>(p - 1) prime roots are = the numbers y m , where m is any number less than p - 1 and prime to it. Thus in the foregoing example p 7, where the prime roots were 3 and 5, the integers less than 6 and prime to it are 1, 5 ; and we in fact have 5 = 3 5 and 3 = 5 5 (mod. 7). 18. Integers belonging to a given exponent; index of a number. If, as before, p-l=ef, that is, if / be a sub- multiple of p-l, then any integer x such that xf is the lowest power of x which is = 1 (mod. p) is said to belong to the exponent/. The number of residues, or terms of the series 1, 2, 3,...p-l, which belong to the exponent / is <(/), the number of integers less than / and prime to it ; these are the roots of the congruence [xf- 1] = of the order </>(/). It is hardly necessary to remark that the prime roots belong to the exponent p . A number x = y m is said to have the index m ; observe the distinction between the two terms exponent and index ; and further that the index is dependent on the selected prime root y. 19. Special forms of composite modulus. If instead of a prime modulus p we have a modulus p m which is the power of an odd prime, or a modulus 2p or 2p m which is twice an odd prime or a power of an odd prime, then there is a theory analogous to that of prime roots, viz., the numbers less than the modulus and prime to it are congruent to successive powers of a prime root y ; thus, if^ m = 3 2 , we have 2, 4, 8, 16, 32, 64 = 2, 4, 8, 7, 5, 1 (mod. 9), and if 2/? m =2 . 3 2 , we have 5, 25, 125, 625, 3125, 15625 = 5, 7, 11, 13, 17, 1 (mod. 18). As regards the even prime 2 and its powers for the modu lus 2 or 4 the theory of prime roots does not come into existence, and for the higher powers it is not applicable ; thus with modulus = 8 the numbers less than 8 and prime to it are 1, 3, 5, 7 ; and we have 3 2 = 5 2 = 7 2 = 1 (mod. 8). 20. Composite modulus N=a a bPcV . . . no prime roots irregularity. In the general case of a composite modulus it has been seen that, if x is any number less than N and prime to it, then #0W -1=0 (mod. N). But (except in the above-mentioned cases p m , 2p m , 2 or 4) there is not any number a such that 0W is the first power of a which is = 1 ; there is always some submultiple such that a 1 is the first power which is = 1. For instance, say N= 24, <^(N} = 8, then the numbers less than 24 and prime to it are 1,5,7,11,13,17,19,23; and we have P = l, 5 2 = 7 2 =13 2 = 17 2 E=19 2 = 23 2 =1 (mod. 24), that is, 1 has the exponent 1, but all the other numbers have the exponent 2. So again where iV=48, the 16 numbers less then 48 and prime to it have, 1 the exponent 1, and 7, 13, 17, 23, 25, 31, 35, 41, 47 each the exponent 2, and the remaining numbers 5, 11, 19, 29, 37, 43 each the ex ponent 4. We cannot in this case by means of any single root or of any two roots express all the numbers, but we can by means of three roots, for instance, 5, 7, 13, express all the numbers less than 48 and prime to it ; the numbers are in fact = 5 a 7/ 3 13 y , where a = 0, 1, 2, or 3, and (3 and y each = or 1 . [Comparing with the theorem for a prime number p, where the several numbers 1, 2, 3, ... p - 1, are expressed by means of a single prime root, =.y a , where a = 0, 1, 2, . . .p - 1, we have the analogue of a case presenting itself in the theory of quadratic forms, the " irregularity " of a deter minant (post, No. 31) ; the difference is that here (the law being known, N a composite number) the case is not re garded as an irregular one, while the irregular determinants do not present themselves according to any apparent law.] 21. Maximum indicator application to solution of a linear congruence. In the case N= 48 it was seen that the exponents were 1, 2, 4, the largest exponent 4 being divisible by each of the others, and this property is a general one, viz., if N=a a lPcV . . in the series of expo nents i (or, as Cauchy calls them, indicators) of the numbers less than N and prime to it, the largest exponent / is a multiple of each of the other exponents, and this largest exponent Cauchy calls the maximum indicator ; the maxi mum indicator / is thus a submultiple of <$>(N), and it is the smallest number such that for every number x less than N and prime to it we have x 1 -1=0 (mod. JV). The values of / have been tabulated from JV= 2 to 1000. Reverting to the linear congruence ax = c (mod. b), where a and b are prime to each other, then, if / is the maximum indicator for the modulus b, we have a T =l, and hence it at once appears that the solution of the con gruence is x = ca r ~ l . 22. Residues of powers for an odd prime modulus. For the modulus p, if y be a prime root, then every num ber not divisible by p is = one of the series of numbers y,y*, . . .y p ~^ ; and, if k be any positive number prime to p-l, then raising each of these to the power k we re produce in a different order the same series of numbers y,y...y p ~ l , which numbers are in a different order = 1, 2, . . . . p - 1, that is, the residue of a kih power may be any number whatever of the series 1, 2, . . ,p - 1. But, if k is not prime to^> - 1, say their greatest common measure is e, and that we have p - 1 = ef, k = me, then for any number not divisible by p the kih power is = one of the series of / numbers y e , y 2e , y fe . ; there are thus only /, = -(p - 1), out of thep - 1 numbers 1, 2, 3, ... .p - I,
which are residues of a kih power. 23. Quadratic residues for an odd prime modulus. In particular, if k = 2, then e = 2, /= ^(p - 1), and the square of every number not divisible by p is =. one of the (p - 1 ) numbers # 2 , y 4 , . . . y p ~ l ; that is, there are only %(p - 1) numbers out of the series 1, 2, 3,. ..p-l which are resi dues of a square number, or say quadratic residues, and the remaining (p - 1) numbers are said to be quadratic non-residues of the modulus p, we may say simply, resi dues and non-residues. But this result can be obtained more easily without the aid of the theory of prime roots. Every number not divisible by p is, to the modulus p, = one of the series of numbers 1, 2, 3, . . |(/>- 1) ; hence every square number is = one of the series of num bers I 2 , 2 2 , 3 2 , . . (/> - I) 2 ; and thus the p-l numbers 1, 2, 3, p-l, are one-half of them residues and the
