116 HISTORY OF THE THEORY OF NUMBERS. [CHAP, v
notation, a(kA+l), a(kA+a)}. . ., a(kA+u>) give all the numbers between kaA and (k+i)aA which are divisible by a and are prime to A. Taking fc=0, 1,. . ., a0"1 — 1, we see that there are exactly aa~l<t>(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 pi, . . . , pk be distinct primes, and denote by (B\ plt . . . , pk) the number of integers ^ B which are divisible by no one of the primes PI, . . . , pk. Then, if p is a new prime,
(B; plf . . . , pt, p) = (5; PJ, . . . , p*) - ([B/p]; Pi, . . . , p*)-The truth of (4) for the special case N=*p—l, 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 0(6), first for the case in which b is a product cd. . .kl of distinct primes. Set b=fil and denote by \l/(b) the number of integers <6 having a factor hi common with 6. There are ll/(ff) numbers < 6 which are divisible by one of the primes c, . . . , k, since there are ^(0) in each of the sets
1,2,. ..,0; 0+1,. ..,?0; ...; (1-1)0+1,. . ., V.
Again, I, 21,. . ., $1 are the integers <6 with the factor I. Of these, 0(j3) are prime to /3, while the others have one of the factors c, . . . , /b and occur among the above W0). Hence ^(6)«^(j8)+0(j8). But Hence
Next, let 6 be a product of powers of c, d} . . . , Z, and set 6=I//3, fi = cd. . .1. By considering L sets as before, we get
E. Catalan11 proved (4) toy 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'6 proof of (1).
E. Catalan13 evaluated <f>(N) by Euler's2 second method.
C. P. Arndt" gave an obscure proof of (4), apparently intended for Catalan's.11 It was reproduced by Desmarest, ThSorie des nombres, 1852, p. 230.
•Anfangsgriinde der Hoheren Arith., 1832, 13-15. "Theorie der Kettenreihen . . .Trier, 1837, 21. "Jour, de Math&natiques, 4, 1839, 7-8. "Comptea Rendus Paris, 12, 1841, 819-821; Exercices d'analyse et de phya. math., Paris, 2,
1841, 9; Oeuvres, (2), 12. "Nouv. Ann. Math., 1, 1842, 466-7. "Archiv Math. Phys., 2, 1842, 6-7.