120 HlSTOBY OF THE THEORY OF NUMBERS. [CHAP. V
E. Betti26 evaluated <£(w), where m is a product of powers of the distinct primes al} a2, ____ Consider the set d of the products of the a's taken t at a time and their multiples £m. Thus C0 is 1, . . . , m, while C2 is
m 0 m
, 2a1a2,. . ., -- ai<*2;
Let x be an integer <m divisible by au. . ., att. Then x occurs
H-OKK"-*"
times in the sets C0, C2, C4, . . . ; and 20-1 times in C1} C3, . . . . Summing
for each of the m—<t>(m) integers rg?n having factors in common with m, we get
But S ?" is the number of integers having in common with m one of the
factors dij o2,. . ., and hence equals S— . Next, sT^) ig the number of
integers having in common with m one of the factors a1a2, ai#3, . . . , and hence equals S {.m/CoiO^ } . Thus
^(?n) =m— S — 1-2 -- . . . . di aja2
R. Dedekind27 gave a general theorem on the inversion of functions (to be explained hi the chapter on that subject), which for the special case of 0(n) becomes a proof like Betti's. Cf. Chrystal's Algebra, II, 1889, 511; Mathews7 Theory of Numbers, 1892, 5; Borel and Drach,81 p. 27.
J. B. Sturm28 evaluated <t>(N) by a method which will be illustrated for the case N = 15. From 1, . . ., 15 delete the five multiples of 3. Among the remaining ten numbers there are as many multiples of 5 as there are multiples of 5 among the first ten numbers. Hence <^>(15) = 10--2 = 8. The theorem involved is the following. From the three sets
1, 2, 3,* 4, 5; 6,* 7, 8, 9,* 10; 11, 12,* 13, 14, 15*
delete (by marking with an asterisk) the multiples of 3. The numbers 11, 13, 14 which remain in the final set are congruent modulo 5 to the numbers 6, 3, 9 deleted from the earlier sets.
J. Liouville29 proved by use of (4) that, for |z|
26Bertrand's Alg£bre, Ital. transl. with notes by Betti, Firenze, 1856, note 5. Proof reproduced
by Fontebasso34, pp. 74-77.
"Jour, fur Math., 54, 1857, 21. Dirichlet-Dedekind, Zahlentheorie, §138. *8Archiv Math. Phys., 29, 1857, 448-452. "Jour, de mathSmatiques, (2), 2, 1857, 433-440.