116 HlSTOKY OF THE THEORY OF NUMBERS. [CHAP. V notation, a(kA-+- 1), a(kA+a),. . ., a(M+w) give all the numbers between kaA and (k+l)aA which are divisible by a and are prime to A. Taking fc = 0, 1, . . ., aa~l — I, we see that there are exactly aa~l<j>(A) multiples of a which are <AB and prime to A. Hence F. Minding9 proved Legendre's formula (5). The number of integers ^n, not divisible by the prime 6, is n — [n/0]. To make the general step by induction, let plt . . . , pk be distinct primes, and denote by (B ; p1} . . . , pk) the number of integers ^ B which are divisible by no one of the primes pi, . . . , pk. Then, if p is a new prime, The truth of (4) for the special case N = p — 1, where p is a prime, follows (p. 41) from the fact that <t>(d) numbers belong to the exponent d modulo p if d is any divisor of p — 1. N. Druckenmuller10 evaluated <£(&), first for the case in which b is a product cd. . . kl of distinct primes. Set b =0Z and denote by \^(b) the number of integers <6 having a factor in common with 6. There are lp(@) numbers < b which are divisible by one of the primes c, . . . , ft, since there are ^(0) in each of the sets I,2,...,j8; 0+1,... ,20; ...; (1-1)0+1,. .., 0. Again, Z, 2Z, . . ., fil are the integers <b with the factor I. Of these, 0(0) are prime to 0, while the others have one of the factors c, . . . , k and occur among the above ^(0). Hence ^(6)=Z^(0)+0(0). But Hence Next, let 6 be a product of powers of c, d, . . ., I, and set 6=L/3, 0 = cd. . J. By considering L sets as before, we get E. Catalan11 proved (4) t>y noting that where there are as many factors in each product as there are distinct prime factors of N. A. Cauchy12 gave without reference Gauss'5 proof of (1). E. Catalan13 evaluated <t>(N) by Euler's2 second method. C. F. Arndt14 gave an obscure proof of (4), apparently intended for Catalan's.11 It was reproduced by Desmarest, Th6orie des nombres, 1852, p. 230. _ _____ •Anfangsgriinde der Hoheren Arith., 1832, 13-15. "Theorie der Kettenreihen . . .Trier, 1837, 21. 11 Jour, de Mathe"matiques, 4, 1839, 7-8. "Comptes Rendus Paris, 12, 1841, 819-821; Exercices d'analyse et de phys. math., Paris, 2, 1841, 9; Oeuvrea, (2), 12. "Nouv. Ann. Math., 1, 1842, 466-7. "Archiv Math. Phys., 2, 1842, 6-7.