CHAP, vj EULEK'S ^-FUNCTION. 117
J. A. Grunert16 examined in a very elementary way the sets
jTfc+1, jAH-2,..., #+*-!, tf+1)* 0*=0, l,...,p-l) and proved that <l>(pk)=p<f>(k) if the prime p divides A;, while <t>(pk) = (p 1)0 (A;) if the prune p does not divide A;. From these results, (2) is easily deduced [cf. Crelle17 on <£(£)].
L. Poinsot16 gave Catalan's11 proof of (4) and proved the statements made by Euler2 in his proof of (3) . Thus to show that, of the N' ~N(1 - 1/p) integers <N and prune to p, exactly N'/'q are divisible by g, note that the set 1,. . ., N contains N/q multiples of q and the set p, 2p,. . . contains (N/p)/q multiples of q, while the difference is Nf/q.
If P, Q, R, . . . are relatively prime in pairs, any number prime to N=PQR . . . can be expressed in the form
pQR...+qPR...+rPQ... + ...,
where p is prune to P, q to Q, etc. If also p<P, q<Q, etc., no two of these sums are equal. Thus there are <£(P)<KQ) - such sums [certain of which may exceed N].
To prove (4), take (pp. 70-71) a prune p of the form kN+1 and any one of the N roots p of xN^l (mod p). Then there is a least integer d, a divisor of N, such that pd=l (mod p). The latter has 4>(d) such roots. Also p is a primitive root of the last congruence and of no other such congruence whose degree is a divisor of N.
A. L. Crelle17 considered the product J57=e1e2. . .en of integers relatively prime in pairs, and set E3-=E/ej. When x ranges over the values 1, . . ., ei} the least positive residue modulo E of E&I+ . . . +Enxn takes each of the values 1, . . .jE once and but once. In case £» is prime to ef for i = 1, . . . , n, the residue of 2E^ is prune to E and conversely. Let dib di2, ... be any chosen divisors >1 of et- which are relatively prime in pairs. Let \l/(et) denote the number of integers ^et- which are divisible by no one of the da, di2,. - .. Let \l/(E) be the number of integers ^E which are divisible by no one of the dn, di2) d2i, . . . , including now all the d's. Then \f/(E) = lK«i) ^(O« In case da, di2, . . . include all the prime divisors > 1 of eif \l/(ei) becomes $(e}). Of the two proofs (pp. 69-73) j one is based on the first result quoted, while the other is like that by Gauss.5
As before, let \[/(y) be the number of integers ^y which are divisible by no one of certain chosen relatively prime divisors dj, . . ., dm of y. By considering the xy numbers ny+r (Q^n<x, l^rgy), it is proved (p. 74) that, when x and y are relatively prime,
\l/(xy) = x\l/(y) , \[/2(xy) = (x - l)^(y) ,
where $2(xy) is the number of integers ^xy which are divisible neither by x nor by any one of the cf s. These formulas lead (pp. 79-83) to the value of<KZ). Set
"Archiv. Math. Phys., 3, 1843, 196-203.
"Jour, de Math6matiques, 10, 1845, 37-43.
"Encyklopadie der Zahlentheorie, Jour, fur Math., 29, 1845, 58-95.