EULER'S ^-FUNCTION, GENERALIZATIONS, FAREY SERIES. NUMBER <f>(n) OF INTEGERS <n AND PRIME TO n.
L. Euler,1 in connection with his generalization of Fermat's theorem, investigated the number <p(ri) of positive integers not exceeding n which are relatively prime to n, without then using a functional notation for #(n). He began with the theorem that, if the n terms a, a+d,..., a+(n—i)d hi arithmetical progression are divided by n, the remainders are 0, 1,..., n—1 in some order, provided d is prime to n; in fact, no two of the terms have the same remainder.
If p is a prime, <Kpm) =pm~1(p-l), since p, 2p,..., p^-p are the only ones of the pm positive integers gpm not prime to pm. To prove that
(1) <t>(AE) =<KA)4>(#) (A, B relatively prime),
let 1, a,..., co be the integers <A and prime to A. Then the integers <AB and prime to A are
1 a ... w
A+l A+a ... A+w
2A+1 2A+a ...
The terms in any column form an arithmetical progression whose difference A is prime to jB, and hence include <f>(B) integers prime to B. The number of columns is <j>(A). Hence there are <f>(A)(t>(B) positive integers <AB, prime to both A and B, and hence prime to AB. If p, . . . , s are distinct primes, the two theorems give
(2) <Kpx. • .^-p^Op-l). . .^(s-l).
Euler2 later used irN to denote <t>(N) and gave a different proof of (2). First, let N=pnq, where p, q are distinct primes. Among the AT— 1 integers <N there are pn— 1 multiples of q, and pn~lq— 1 multiples of p, these sets having in common the p71""1— 1 multiples of pq. Hence
A simpler proof is then given for the modified form of (2) : (3)
where p, <?, r, . . . , s are the distinct primes dividing N. There are JV/p multiples <N of p and hence N'=N(p—I)/p integers <J\T and prime to f. Of these, N'/q are divisible by '#; excluding them, we have N" = N'(q — l)/q numbers < N and prime to both p and q. The rth part of these are said
Wovi Comm. Ac. Petrop., 8, 1760-1, 74; Comm. Arith., 1, 274. Opera postuma, I, 492-3. •Acta Ac. Petrop., 4 II (or 8), 1780 (1755), 18; Comm. Arith., 2, 127-133. He took <£(1)=0.