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.