History Of The Theory Of Numbers - I

CHAP. V] EULER'S ^-FUNCTION. 115
where the summations extend over the combinations of 0, . . . , <o taken 1, 2, . . ., at a time, while A0 is a positive integer <A for which AA0+C is divisible by A, and. [a;] is the greatest integer ^x. We thus derive the approximation stated by Legendre.4 Taking A = l, C=0 (p. 420), we see that the number of integers ^n, which are divisible by no one of the distinct primes 0, X, . . . , w is
A. von Ettingshausen7 reproduced without reference Euler's2 proof of (3) and gave an obscurely expressed proof of (4). Let N=paq^. . ., where p, q, . . .are distinct primes. Consider first only the divisors d = pMg"> where
0, v> 0, so that d involves the primes p and q, but no others. By (3),
-1) ,
y/
2 S
Similarly, £</>(pA) =pa— 1. In this way we treat together the divisors of N which involve the same prime factors. Hence when d ranges over all the divisors of N,
P
where the summation indices range over the combinations of all the prime factors of N taken 1, 2, . . .at a time. [Cf. Sylvester.32]
A. L. Crelle8 considered the number z3- of integers, chosen from n-i, . . . ,n0, which are divisible by exactly j of the distinct primes pb . . ., pm] and the number s;- of the integers, chosen from %,..., na, which are divisible by at least j of the primes p». Then
Let v be the number of the integers nly . . ., na which are divisible by no one of the primes p^. Then
In particular, take nl5. . ., na to be 1, 2,. . ., N, where N = paqpry. . ., and take p!,. . ., pm to be p, g, r,. . .. Then
N JV AT 7Vr JV ,
He proved (1) for B = a", where a is a prime not dividing A (p. 40). By Euler's1 table there are B<t>(A) integers <AB and prime to A. In Euler's
7Zeitschrift fiir Phyeik u. Math, (eds., Baumgartner and Ettingshaueen), Wien, 5, 1829, 287-292. "Abh. Akad. Wiss. Berlin (Math.), 1832, 37-50.