Thread: Number of Generators

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?

Originally Posted by MathBird

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)

Thank you very much.