The number of generators of a group G is the number of positive integers < n which are relatively prime to n. How can this be proved?
The above is true only when G is finite and has an element of order = order of the group = n. i.e is G is cyclic.
G then = {e, a, a^2, a^3 ,......., a^n-1}
An element is a generator IFF its order = n
Let a^k be generator. If order of a^k = m then m is smallest number such that n | mk
n | mk implies (n/gcd(n,k)) | m
So smallest such m = n/gcd(n,k). For this to be n gcd(n,k) should be 1. Hence k is relatively prime to n (and obviously it is < n)