600 numbeks. [795 
17. Any number x less than p is =g m , and, if m is not prime to p— 1, but 
has with it a greatest common measure e, suppose m = ke, p — 1 = ef, then 
x = g ke , xf = g ke f = g k (v ~ l) = 1, 
that is, x? = 1; and it is easily seen that in the series of powers x, x z , ..., xf, we have 
xf as the first term which is = 1 (mod. p). A number = g m , where to is not prime to 
p — 1, is thus not a prime root; and it further appears that, g being any particular 
prime root, the <£ (p — 1) prime roots are = the numbers g m , where to 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 s and 3 = 5 5 (mod. 7). 
18. Integers belonging to a given exponent; index of a number. If, as before, 
p — 1 = ef, that is, if / be a submultiple of p — 1, 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 f 
The number of residues, or terms of the series 1, 2, 3, .... p — 1, which belong to the 
exponent / is </> (/), the number of integers less than f and prime to it; these are 
the roots of the congruence [ccf —1] = 0 of the order </>(/). It is hardly necessary to 
remark that the prime roots belong to the exponent p — 1. 
A number x = g m is said to have the index to; observe the distinction between 
the two terms exponent and index; and, further, that the index is dependent on the 
selected prime root g. 
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 g\ thus, 
if p m = 3 2 , we have 
2, 4, 8, 16, 32, 64 = 2, 4, 8, 7, 5, 1 (mod. 9), 
and if 2p 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 modulus 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 №c y ...—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 — 1 = 0 (mod. A r ). But, except in the above-mentioned cases 
p m , 2p m , 2 or 4, there is not any number a such that a* 6*0 is the first power of a 
which is = 1; there is always some submultiple i = ^ <f> (N) such that a 1 is the first