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 (Cn) 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 Cn has order d iff it is a generator of the subgroup of Cn of order d. Therefore N(d), the number of elements of order d in Cn, is equal to the number of generators in Cd. To complete the proof we need only show that this is φ(d).
We can represent Cd 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
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 Cd is φ(d).