Number of generating elements in a finite cyclic group

Question

Let $G$ is finite cyclic group of order $37$. Then the number of elements in the set $\{g\in G\mid \langle g\rangle=G\}$ is equal to?

Is it that easy to say that it is 36? Or there is a theory behind it?

Answer 1

In a cyclic group of order $n$, the number of elements which generate the group is given by $\phi(n)$, where $\phi$ denotes the Euler's phi function.

Given any $n$, $\phi(n)$ provides the number of primes to $n$.

Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n}$ be the prime factorization of $n$, $p_1,p_2,\dots, p_n$ are distinct primes and $\alpha_1, \alpha_2, \dots, \alpha_n\in \mathbb{N}$; then

$\phi(n)=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n}(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_n})$.

For your example:

$\phi(37)=37(1-\frac{1}{37})=36.$