Multiplicative Subgroup Generator

Check if a member of a cyclic group can act as a generator here!

Test Number
Modulo Number

Explaining what a generator is will make more sense by starting with explaining what a cyclic group is. A cyclic group is a group that can be generated by a single element $g$, referred to as a generator. In other words, a generator $g$ is essentially an element from a cyclic group $G$ such that you can produce a subgroup containing all elements inside $G$. Note that a multiplicative group $(\mathbb{Z}_n^{*}, \cdot\ )$, or simply $\mathbb{Z}_n^{*}$ is cyclic if and only if $n$ is prime. Here, any $\mathbb{Z}_n^{*}$ comprises of natural numbers up to just before $n$, with the first natural number 1 being the identity element.

For instance, 4 is a generator of $G=\mathbb{Z}_5^{*}$, where $\mathbb{Z}_5^{*}$ is equal to the set of all integers from 1 to 4 (the last integer before 5), i.e., $\left\{1, 2, 3, 4\right\}$. We can show this by working out the following: $$ \displaylines{ 2^1 \mod 5 \equiv 2 \\ 2^2 \mod 5 \equiv 4 \\ 2^3 \mod 5 \equiv 8 \mod 5 \equiv 3 \\ \\ 2^4 \mod 5 \equiv 2(2^3 \mod 5) \mod 5 \\\equiv 2(3) \mod 5 \equiv 6 \mod 5 \equiv 1 \\ \langle 2\rangle = \left\{2, 4, 3, 1\right\} } $$ Here, we can see that constantly multiplying 2 modulo 5 until the number 1 is reached gives us a subgroup of 4 elements, all make up the set of numbers 1 to 4 (just before 5). 2 isn't a generator of $\mathbb{Z}_7^{*}$, though, since this does not generate all 6 natural numbers under 7: $$ \displaylines{ 2^1 \mod 7 \equiv 2 \\ 2^2 \mod 7 \equiv 4 \\ 2^3 \mod 7 \equiv 8 \mod 7 \equiv 1 \\ \langle 2\rangle = \left\{2, 4, 1\right\} } $$ This goes to show that not every element inside $\mathbb{Z}_p^{*}$, where $p$ is prime, can become a generator. In fact, for any multiplicative group $\mathbb{Z}_p$, the number of generators is equal to $\varphi(p-1)$. For instance, $\mathbb{Z}_{23}^{*}$ contains $\varphi(22)$ generators, which is equal to 10: $$ \varphi(22) = \varphi(2\times 11) = 1\times 10 = 10 $$ Here, Euler's phi ($\varphi$) function is used, which is explained as follows:

Let $n\in \mathbb{N}$. Then Euler's $\varphi$-function is defined by the cardinality of the units modulo n, i.e., $\varphi(n) = \left|\mathbb{Z}_n^{*}\right|$.
  • If $p$ and $q$ are relatively prime (i.e., $gcd(p,q) = 1)$ and $n=pq$, then $\varphi(n) = \varphi(p)\times\varphi(q)$.
  • If $p$ is prime, then $\varphi(p) = p-1$. This is because all natural numbers 1, 2, ..., $p-1$ are relatively prime to $p$. Note that 0 isn't relatively prime to $p$.
  • If $p$ is prime and $a\in\mathbb{Z}^+$, then $\varphi(p^a) = p^a-p^{a-1}$.

If a generator $g$ exists in a group $\mathbb{Z}_n^{*}$, $g$ is called a primitive root modulo $n$.

You may also notice that the results of all subgroups generated by each element in a multiplicative group $\mathbb{Z}_n^{*}$ is a factor of $(n-1)$. This fits perfectly alongside Lagrange's Theorem, which mentions that for any subgroup $H$ of a group $G$, $H$ will have an order (i.e., cardinality, the number of elements) that divides that of $G$. Essentially this means that you can divide the cardinality of $G$ by that of $H$, and it will not leave a remainder.

Taking the earlier example of $\langle2\rangle$ producing a subgroup of 3 elements in $\mathbb{Z_7^{*}}$, $\mathbb{Z_7^{*}}$ contains 6 elements. 3 divides 6, or rather, you can divide 6 by 3 and leave no remainder behind. $\langle6\rangle$ produces a subgroup of 2 elements under $\mathbb{Z}_7^{*}$, which also divides 6, and so on.