CHAP. V] EULER'S ^-FUNCTION. 117 J. A. Grunert15 examined in a very elementary way the sets jt+1, jfc+2,..., jt+fc-1, O'+D* (j=0, l,...,p-l) and proved that <t>(pk)=p<t>(k) if the prime p divides fc, while $(pfc) = (p — 1)<K&) if the prune p does not divide k. 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(l- 1/p) integers < N and prime 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 g, while the difference is N'/q. If P, Q, R, . . . are relatively prune in pah's, any number prune 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 0(P)<KQ) . . . such sums [certain of which may exceed N]. To prove (4), take (pp. 70-71) a prune p of the form kN+l 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 <t>(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 E=eie2. . .en of integers relatively prune in pairs, and set E3-=E/ej. When x ranges over the values 1, . . ., eit the least positive residue modulo E of E&+ . . . -\-Enxn takes each of the values 1, . . . , E once and but once. In case re* is prime to et for i = 1, . . . , n, the residue of SEi£» is prime to E and conversely. Let dn> di2) ... be any chosen divisors >1 of e< which are relatively prime in pairs. Let ^(e,-) denote the number of integers ^et which are divisible by no one of the da, d&, ____ Let \//(E) be the number of integers ^E which are divisible by no one of the du, d12, d2i, . . •> including now all the d's. Then $(E) = \l/(ei) . . . \ls(en). In case dii} d^,. . . include all the prime divisors >1 of eit vKe,-) becomes 0(et-). Of the two proofs (pp. 69-73) -t 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 di, . . ., dm of y. By considering the xy numbers ny+r (0^n<x, l^r^y), it is proved (p. 74) that, when x and y are relatively prime, where ^(^2/) ^s ^ne number of integers ^ xy which are divisible neither by x nor by any one of the d's. These formulas lead (pp. 79-83) to the value oi<t>(Z). Set _ Z = pic'...p,>, 2 = p!...pM? n = Z/z, _ "Archiv. Math. Phys., 3, 1843, 196-203. "Jour, de Math<§matiques, 10, 1845, 37-43. "Encyklopadie der Zahlentheorie, Jour, fiir Math., 29, 1845, 58-95.