How do you determine the number and distribution of element orders in a cyclic group $\mathbb{Z}_p^*$?
In a cyclic group of order $n$, for each divisor $d$ of $n$, there are exactly $\varphi(d)$ elements of order $d$. The sum of all $\varphi(d)$ equals $n$.
* In $\mathbb{Z}_{19}^*$ (order 18), each divisor $d$ of 18 has exactly $\varphi(d)$ elements of order $d$ — and the counts sum back to 18, accounting for every element (Lagrange). *
Key facts for $\mathbb{Z}_p^* = \{1, 2, ..., p-1\}$ with $|G| = p - 1$:
- Element orders can only be divisors of $p - 1$ (Lagrange)
- For each divisor $d$ of $p - 1$: exactly $\varphi(d)$ elements have order $d$
- Verification: $\sum_{d | n} \varphi(d) = n$ (accounts for all elements)
Example: $\mathbb{Z}_7^*$, order 6, divisors of 6: $\{1, 2, 3, 6\}$
| Order $d$ | $\varphi(d)$ | # Elements | Which elements |
|---|---|---|---|
| 1 | $\varphi(1) = 1$ | 1 | Element 1 |
| 2 | $\varphi(2) = 1$ | 1 | Element 6 |
| 3 | $\varphi(3) = 2$ | 2 | Elements 2, 4 |
| 6 | $\varphi(6) = 2$ | 2 | Elements 3, 5 (generators!) |
| Total | 6 | ✓ |
For $\mathbb{Z}_{19}^*$, order 18, divisors: $\{1, 2, 3, 6, 9, 18\}$:
- Generators (order 18): $\varphi(18) = 6$ elements → $\{2, 3, 10, 13, 14, 15\}$
- These are the primitive elements — crucial for Diffie-Hellman parameter selection
Tip: The inverse of any element can be computed as $a^{\text{ord}(a)-1} \mod p$. For generators: $a^{p-2} \mod p$ (which is Fermat's theorem).
Go deeper:
Multiplicative group mod n (Wikipedia) — the structure of ℤ_n* and its element orders.