Questions about cyclic groups (Paar-Pelzl).

Question

I want to solve this exercise, but it has been long since I studied groups and I am stuck. This is problem 8.3. in Paar-Pelzl 'Understanding Cryptography'. It refers to the previous two problems, so I put them here too:

Problem 8.1 Determine the order of all elements of the multiplicative groups of $\mathbb Z ^* _5$, $\mathbb Z ^* _7$ and $\mathbb Z ^* _{13}$.

Problem 8.2 We consider the group $\mathbb{Z}_{53}^{*}$ (the cyclic group of order $52$). What are the possible element orders? How many elements exist for each order?

This is the problem I want to solve:

Problem 8.3. We now study the groups from Problem 8.2.

1. How many elements does each of the multiplicative groups have?

2. Do all orders from above divide the number of elements in the corresponding multiplicative group?

3. Which of the elements from Problem 8.1. are primitive elements?

4. Verify for the groups that the number of primitive elements is given by $\phi(\vert\mathbb{Z}_{p}^{*}\vert)$.

This is what I get for Problem 8.3.:

1. I know that $\mathbb{Z}_{53}^{*}$ has order $52$. Its prime decomposition is $$52=13\cdot 2 \cdot 2.$$Then the subgroups of $\mathbb{Z}_{53}^{*}$ have cardinal $26$, $13$, $4$ and $2$. Is this right?

2. Can the order of a cyclic group be different than the number of elements? I thought it was the same thing.

3. We have the primitive elements $2,3\in \mathbb Z^* _5$, $3,5\in \mathbb Z^* _7$ and $2, 6, 7, 11\in \mathbb Z ^* _{13}$. I computed this programming it in the computer and trying all the powers modulo $n$ of each element in each group (and looking for loops). Is there an easier way to know the primitive elements?

4. I've looked in the bibliography and I don't know which function is this. I think maybe it is Euler's totient function, but then what I got in the previous part would be wrong.

Thank you for your help and sorry for my poor English.

Answer 1

1. The subgroups of a cyclic group of order $n$ have as orders all possible divisors of $n$, and they're all cyclic. Indeed, if $a$ is a generator, the subgroup generated by $a^k$ has order $$\frac{n}{n\wedge k},\quad\text{where }\;n\wedge k=\gcd(a,k).$$ Thus, if $d$ is any divisor of $n$, $a^{n/d}$ has order $d$.

Also $a^k$ generates the same the same subgroup as $a^{k'}$ if and only if $\gcd(n,k)=\gcd(n,k')$.

The number of divisors of $52=2^2\cdot 13$ is $(2+1)(1+1)=6$.

3. Once you've found one primitive element $a$, the other primitive elements can be obtained as powers $a^k$, where $k$ is coprime to the ordre of the multiplicative group.