CHAP. V] EULER'S ^-FUNCTION. 133
the <j>(k) integers ^k and prime to k occurs just once among the residues modulo k of the integers from Ik to (Z+l)fc; taking Z = 0, 1,. . ., p — 1, we obtain this residue p times. Hence there are pcf>(k) numbers ^pk and prime to k. These include </>(&) multiples of p, whence <t>(pk) = (p — !)<£(&)• For, if r is one of the above residues, then r, r+k,. . ., r-f (p — 1)& form a complete set of residues modulo p and hence include a single multiple of p. Hence
if a, 6, c, ... are distinct primes. Next, for n = aab0. . ., we use the sets of numbers from lab. . .to (Z-J-l)ab. . ., for Z = 0, 1,. . ., aa~lbf*~l . . . — 1.
Borel and Drach81 noted that the period of the least residues of 0, a, 2a} . . . modulo N} contains N/8 terms, if d is the g. c. d. of a, N; conversely, if d is any divisor of N, there exist integers such that the period has d terms. Taking a = 0, 1, . . ., N-l, we get (4).
H. Weber82 defined <£(n) to be the number of primitive nth roots of unity. If a is a primitive ath root of unity and /3 a primitive 6th root, and if a, b are relatively prime, a/3 is a primitive abth root of unity and all of the latter are found in this way. Hence <j)(ab) =$(a) cj)(b). This is also proved for relatively prime divisors a, b of n — 1, where n is a prime, by use of integers a and /3 belonging to the exponents a and b respectively, modulo n, whence a/3 belongs to the exponent ab.
K. Th. Vahlen83 proved that, if Ja,^(n) is the number of irreducible fractions between the limits a and /3, a>/3^0, with the denominator n,
where d ranges over the divisors of n. For /3 = 0, the first was given by Laguerre.35 Since Ii,Q(n)—4>(n)} these formulas include (4) of Gauss and that by Dirichlet.21
J. J. Sylvester84 corrected Ms66 first formula to read
and proved it. By the usual formula for reversion,
T\j] =*W) -*(ij) +*(#) -*(&) +*(*j) - ....
A. P. Minin85 solved |<^(w) =2? for ra when # has certain values. The equation determines the number of regular star polygons of m sides. Fr. Rogel86 gave the formula of Dirichlet.21
"Introd. th^orie des nombres, 1895, 23.
"Lehrbuch der Algebra, I, 1895, 412, 429; ed. 2, 1898, 456, 470.
"Zeitschrift Math. Phys., 40, 1895, 126-7.
"Messenger Math., 27, 1897-8, 1-5; Coll. Math. Papers, 4, 738-742.
"Report of Phys. Sec. Roy. Soc. of Friends of Nat. Sc., Anthropology, etc. (in Russian), Mos-
cow, 9, 1897, 30-33. Cf. Hammond.113 "Educat. Times, 66, 1897, 62.