History Of The Theory Of Numbers - I

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.