If k is some positive integer, φ(k) is defined as the number of positive integers less than or equal to k whose greatest common divisor (gcd) with k is one. Thus φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2 and so on.

Let d, n be positive integers and let ‘d|n’ signify ‘d divides n’. The theorem

is not difficult to prove (for example Hardy and Wright, 5th ed. Theorem 63). The proof I like best however is not the simplest, but it shows how φ is related to the structure of the abstract finite cyclic groups, of which the additive groups of integers (modulo n) are concrete examples.

By the the latter groups I mean the set of integers 0, 1, … , n-1 and the binary operation ° which is defined such that a°b is the remainder on dividing a+b by n. We call this addition (modulo n).

We define the order of a as the least positive integer i such that ai is divisible by n, that is, the remainder on dividing ai by n is 0, the identity element.

Now every element of a group has some order and if N(d) is the number of elements of order d then

where n is the order of the group. But an element of order d generates a subgroup of order d and so by Lagrange’s theorem, d|n. Thus

Now the cyclic group of order n (C_{n}) is known to have exactly one subgroup of order d for each divisor d of n, and each subgroup is necessarily cyclic. An element of C_{n} has order d iff it is a generator of the subgroup of C_{n} of order d. Therefore N(d), the number of elements of order d in C_{n}, is equal to the number of generators in C_{d}. To complete the proof we need only show that this is φ(d).

We can represent C_{d }as consisting of the integers 0, 1, … , d-1 with the binary operation being addition modulo d. If gcd(k,d)=1 then none of the integers k, 2k, … ,(d-1)k is divisible by d, and they are all distinct (mod d) and since there are d-1 of them and dk=0 (mod d) then k is a generator. On the other hand, if k is a generator it has order d. But

(mod d)

so the order of k is no greater than d/gcd(k,d) and if gcd(k,d) were not one, we would have a contradiction. Therefore k is a generator iff gcd(k,d)=1 and so the number of generators in C_{d} is φ(d).