Suppose we pick an arbitrary element from a group. Then what are the chances that the element will generate the group? If the group is non-cyclic, then the chances are obviously zero. But in a cyclic group, there is a possibility that the element could generate the group. Therefore, the above question makes sense in the case of a cyclic group. For instance, consider the group \({\mathbb{Z}}_{4}\). Here elements 1, 3 generate the group while 2, 4 do not. Thus, the probability of generating \({\mathbb{Z}}_{4}\) is \(\frac{2}{4}\ =\ 0.5\). Similarly, we can also ask for the probability of generating other cyclic groups. This leads to the general question of the probability of finding generators of any cyclic group.
Theorem. Any infinite cyclic group has exactly 2 generators.
Proof. Consider infinite group \(G\) such that \(G\ =<\ a\ >\). Suppose \(\exists \ b \ \in \ G\) such that \(b\) generates \(G\). Then we must have \(b\ =\ a^{k}\) for some \(k\ \in \ \mathbb{Z}\). This means \(\exists \ n \ \in \ \mathbb{Z}\) such that \((a^{k})^{n} = a\). But since the order of \(a\) is not finite, therefore we know that for any \(i\), \(j\ \in\ \mathbb{Z}\), \({a}^{i}\ =\ {a}^{j} \Leftrightarrow\ i\ =\ j\). Therefore when \({({a}^{k})}^n\ =\ a\), we must have \(kn = 1\). This means \(k = \pm 1\) as \(k,\ n\ \in\ \mathbb{Z}\). Therefore \(b = a\), \({a}^{−1}\) . Also, we know that in this case \(a \neq {a}^{−1}\) . Thus \(G\) will have exactly 2 generators.
Therefore \(P(G) = 0\) when \(G\) is an infinite cyclic group, where \(P(G)\) denotes the probability of generating \(G\).
For generating a finite cyclic group, we need to find its generators. For a finite cyclic group \(G\ =\ <\ a\ >\), we know that \(G\ =\ <\ {a}^{k}\ >\) if and only if \(gcd(k, n)\ =\ 1\). Therefore, if \(|G|\ =\ n\) then \(G\) has \(\phi(n)\) generators where \(\phi\) denotes the Euler-Phi function. As a result, the probability of any randomly chosen element to be a generator of the group is \(\phi(n)/n\). Thus the probability of generating \(G\) which depends upon the generating capacity of its elements is \(\phi(n)/n\) . (It is assumed that all the elements are equally likely to be picked.)
As before, let \(P(G)\) denote the probability of generating \(G\). Now, let’s examine the behaviour of \(P(G)\) under different circumstances. (This goes without saying that \(G\) is cyclic in each case). Case 1: When \(|G|\ =\ p\), where \(p\) is prime. Here \[P(G)\ =\ \frac{\phi(p)}{p}=\frac{p-1}{p}=1-\frac{1}{p} \]
Case 2: When \(|G|\ =\ {p}^{n}\). Here, \[P(G)\ = \ \frac{\phi({p}^{n})}{{p}^{n}}=\frac{{p}^{n}(1-\frac{1}{p})}{{p}^{n}}=1-\frac{1}{p}\]
It is worth noting that whether the order of \(G\) is \(p\) or \({p}^{n}\), \(P(G)\) remains unchanged i.e. \(1 − \frac{1}{p}\) .
Case 3: When \(|G|\ =\ {p}^{m}.{q}^{n}\) where \(m\), \(n\ \in\ \mathbb{Z}\) and \(p\), \(q\) are prime. Here \[P(G)\ =\ \frac{\phi({p}^{m})({q}^{n})}{({p}^{m})({q}^{n})}=\frac{{p}^{m}(1-\frac{1}{p}).{q}^{n}(1-\frac{1}{q})}{{p}^{m}{q}^{n}}=\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\]
Case 4: When \(|G|\ =\ {\prod}_{i=1}^{k}{{p}_{i}}^{{m}_{i}}\) , where \({m}_{i}\ \in\ \mathbb{Z}\) and \({p}_{i}\) is prime \(\forall\ 1 \leq i \leq k\). Here \({p}_{i}\) must be
distinct while \({m}_{i}\) need not be distinct \(\forall\ 1 \leq i \leq k\).
This is the most general case since any finite group’s order can be broken down into the product of
powers of primes by using the Fundamental Theorem of Arithmetic. Here,
\[\begin{align}P(G)\ &=\ \frac{\phi ({\prod}_{i=1}^{k}{p}_{i}^{{m}_{i}})}{{\prod}_{i=1}^{k}{{p}_{i}}^{{m}_{i}}}\\\\ &=\frac{{\prod}_{i=1}^{k}\phi ({{p}_{i}}^{{m}_{i}})}{{\prod}_{i=1}^{k}{{p}_{i}}^{{m}_{i}}}\\\\ &=\frac{{\prod}_{i=1}^{k}{{p}_{i}}^{{m}_{i}}(1-\frac{1}{{p}_{i}})}{{\prod}_{i=1}^{k}{{p}_{i}}^{{m}_{i}}}\\\\ &= \displaystyle \prod^{k}_{i=1}\ 1-\frac{1}{{p}_{i}}\end{align}\]
For example, consider \({\mathbb{Z}}_{90}\). Now, \(\left|{\mathbb{Z}}_{90}\right| = 2 \cdot {3}^{2} \cdot 5\). Hence, \[P({\mathbb{Z}}_{90})=\left( 1-\frac{1}{2}\right)\left( 1-\frac{1}{3} \right) \left( 1- \frac{1}{5} \right) = \frac{4}{15}\]
Now, consider \({\mathbb{Z}}_{360}\). Now, \(\left|{\mathbb{Z}}_{360}\right| = 2 \cdot {3}^{2} \cdot 5\). Hence, \[P({\mathbb{Z}}_{360})=\left( 1-\frac{1}{2}\right)\left( 1-\frac{1}{3} \right) \left( 1- \frac{1}{5} \right) = \frac{4}{15}\]
Thus, it is very easy to see that \(P(G)\) rather than depending upon \(|G|\) actually depends upon prime factors of \(|G|\).
Let \(\xi (G)\ =\ \{ \ p \) \( | \ p \) divides \( |G| \) and \( p \) is prime \( \} \)
Therefore in general, for a finite cyclic group \(G\), \[P(G)= \displaystyle \prod_{p \in \xi (G)} \left( 1- \frac{1}{p}\right) \]
Theorem. For finite cyclic groups \(G\) and \(H\), if \(\xi (G)\ =\ \xi (H)\) then \(P(G)\ =\ P(H)\).
Proof. We have, \[P(G)= \displaystyle \prod_{p \in \xi (G)} \left( 1- \frac{1}{p}\right)=\ \displaystyle \prod_{p \in \xi (H)} \left( 1- \frac{1}{p}\right)=\ P(H) \]
The converse of this theorem also holds. Thus \(P(G) = P(H) \Leftrightarrow\ \xi (G)\ =\ \xi (H)\). The proof is easy and left to the reader.
Hence it is proved that \(P(G)\) depends directly on prime factors of \(|G|\) and not on \(|G|\) itself. This shows the importance of prime divisors of the order of a cyclic group in the probability of its generation via an arbitrary element.
Designed & Developed by: Vedant Goyal and Ujjawal Agarwal