114 HlSTOEY OF THE THEOEY OF NlJMBEES. [CHAP. V
[cf. Poinsot16] to be divisible by r; after excluding them we get N"(r—T)/r numbers; etc.
Euler3 noted in a posthumous paper that, if p, g, r are distinct primes, there are r multiples ^pqr of pq, and qr multiples of p, and a single multiple of pqr, whence
In general, if M is any number not divisible by the prime p, and if p, denotes the number of integers £M and prime to M, there are M-p integers ^M and not prime to M and hence pn(M—ti) integers ^Mpn and not prime to M and therefore not prune to Mpn. Of the Mpn~l multiples ^Mpn of p} exclude the pn~1(M— ja) which are not prune to M ; we obtain pn~lp, multiples of p which are prune to M. Hence
4>(pnM) =pnM-pn(M-tj) -pn-1M = Pn~1(p~l)M.
A. M. Legendre4 noted that, if 6, . . . , co are any odd prunes not dividing A, the number of terms of the progression A +B, 2A+B, . . ., nA+B which are divisible by no one of the primes 0, . . . , co is approximately n(l — 1/6) . . . (1 — 1/co), and exactly that number if n is divisible by 0, . . . , co.
C. F. Gauss6 introduced the symbol <t>(N). He expressed Euler' s1 proof of (1) hi a different form. Let a be any one of the <t>(A) integers < A and prune to A, while /3 is any one of the <t>(B) integers <B and prime to B. There is one and but one positive integer x<AB such that x^a (mod A), x=p (mod B). Since this x is prime to A and to B, it is prime to AB.
Making the agreement that <£(!) = 1, Gauss proved
(4) S$(d) = JV (d ranging over the divisors of N).
For each d, multiply the integers ^d and prime to d by N/d] we obtain S0(d) integers ^N, proved to be distinct and to include 1, 2, . . . , N.
A. M. Legendre6 proved (3) as follows: First, let N~pM, where p is a prime which may or may not divide M; then Mp—M of the numbers 1,. . ., N are not divisible by p. Second, let N = pqM, where p and q are distinct primes. Then 1,. . ., N include M numbers divisible by both p and q] Mp—M numbers divisible by q and not by p] Mq — M numbers divisible by p and not by q. Hence there remain N(l — 1/p) (I — l/q) numbers divisible by neither p nor q. Third, a like argument is said to apply to N=pqrM, etc.
Legendre (p. 412) proved that if A} C are relatively prime and if 0,X,ju, . . . , co are odd primes not dividing A , the number of terms kA — C(k = l,...,ri), which are divisible by no one of 0, . . . , w, is
^Tractatus de numerorum, Comm. Arith., 2, 515-8. Opera postuma, I, 1862, 16-17.
fEssai sur la thSorie des nombrea, 1798, p. 14.
*Disquisitiones Arithmetics, 1801, Arts. 38, 39.
•Th&>rie des nombres, ed. 2, 1808, 7-8; German trans, of ed. 3 by Maser, 8-10.