Average Probability of an Element Being a Generator in the Cyclic Group

Yoshihiro Tanaka

Faculty of Economics, Hokkaido University, Sapporo, Japan.

DOI: 10.4236/ajcm.2023.132012                

Abstract

All elements in the cyclic group   are generated by a generator g. The number of generators of  of  , namely   is known to be Euler’s totient function ; however, the average probability of an element being a generator has not been discussed before. Several analytic properties of   have been investigated for a long time. However, it seems that some issues still remain unresolved. In this study, we derive the average probability of an element being a generator using previous classical studies.

Keywords

Generator, Cyclic Group, Euler Product

1. Introduction

A cyclic group $C\left(n\right)$ is an elementary commutative group, and if $n=p$ (prime), $C\left(p\right)$ is known as one of the classifications of finite simple groups.

Every element in the cyclic group $C\left(n\right)=\left\{g^0\left(=e\right),g,g^2,\cdots ,g^{n-1}\right\}$ is generated by a generator g. Euler’s totient function $\phi \left(n\right)$ is defined by

$\phi \left(n\right)=\left|\left\{1\le k\le n|\gcd \left(k,n\right)=1\right\}\right|$ . (1)

Euler’s totient function $\phi \left(n\right)$ plays an intrinsically important role in the public key cipher RSA, which is essential in electronic commerce [1] .

The average probability of an element being a generator has not been discussed before. Several analytic properties of $\phi \left(n\right)$ have been investigated for a long time (e.g., [2] [3] ). However, it seems that some issues still remain unresolved.

Dirichlet [4] considered the mean values of sequences of integer values analytically; however, their understanding can be somewhat challenging because of their unfamiliarity.

In this paper, we derive the average probability of an element being a generator using the studies by Dirichlet [4] and Dirichlet and Dedekind [5] .

Throughout this paper, for a real number t, [t] denotes the integer part of t.

2. Preliminaries

As for the possibility that two arbitrary natural numbers are coprime, the following result is mentioned in [6] . We prove the result for the sake of convenience.

Lemma 1. The probability that two arbitrary natural numbers are coprime is $\frac{6}{{\pi }^2}$ .

Proof: Since the probability that two arbitrary natural numbers have a prime p as a common divisor is $1-\frac{1}{p^2}$ , the probability that two arbitrary natural numbers are coprime is ${\displaystyle {\prod }_{p:\text{prime}}\left(1-\frac{1}{p^2}\right)}$ . Noting that by the Euler product formula

${\displaystyle {\prod }_{p:\text{prime}}\left(1/\left(1-\frac{1}{p^2}\right)\right)}={\displaystyle {\sum }_{n=1}^{\infty }\frac{1}{n^2}}=\zeta \left(2\right),$

it holds that

${\displaystyle {\prod }_{p:\text{prime}}\left(1-\frac{1}{p^2}\right)}=\zeta {\left(2\right)}^{-1}=\frac{6}{{\pi }^2}$ . (2)

□

We also mention the following result.

Theorem 2. Choose two arbitrary natural numbers a and b, and consider an arithmetic progression $\left\{a,a+b,a+2b,\cdots \right\}$ . Then, the probability that the arithmetic progression includes an infinite number of primes is $\frac{6}{{\pi }^2}$ .

Proof: The proof follows from Lemma 1 and Dirichlet’s theorem on arithmetic progressions [7] . □

3. Main Result

In general, the cyclic group $C\left(n\right)=\left\{g^0\left(=e\right),g,g^2,\cdots ,g^{n-1}\right\}$ generated by a generator g has generators $g^i,i\in S\left(n\right)\subset \left\{1,2,\cdots ,n-1\right\}$ . Then, $C\left(n\right)$ is expressed as $C\left(n\right)=\left\{g^0\left(=e\right),g^i,g^{2i},\cdots ,g^{\left(n-1\right)i}\right\}$ .

As for $\left|S\left(n\right)\right|$ , which is the number of generators of the cyclic group $C\left(n\right)$ , we prove the following lemma.

Lemma 3. $\left|S\left(n\right)\right|=\phi \left(n\right)$ .

Proof Let g be a generator. If $g^k$ is a generator, it follows that $g={\left(g^k\right)}^z=g^{kz}$ , namely, $g^{kz-1}=e$ .

As we can write $kz-1=qn+r$ , $r<n$ ,

$g^{kz-1}=g^{qn+r}={\left(g^n\right)}^q\cdot g^r=g^r=e$ .

As $r=0$ because $r<n$ ,

$kz=1$ , mod n. (3)

Equation (3) implies that the Diophantine equation $kz+nu=1$ has integer solutions z and u, which means k and n are coprimes by Bezout’s lemma. The converse is obvious.

Therefore, the theorem holds from the definition (1) of Euler’s totient function $\phi \left(n\right)$ . □

Consider $\text{P}\left(x\right)=\frac{\phi \left(x\right)}{x}$ for x (integer). We can see that $\text{P}\left(1\right)=1$ , $\text{P}\left(p\right)=\frac{p-1}{p}$ for p: prime, and $\text{P}\left(x\right)>x^{-\frac{1}{2}}$ for $x>6$ , $\text{P}\left(x\right)>x^{-\frac{1}{3}}$ for $x>30$ (see [8] ).

We can define $E\left(\text{P}\left(X\right)\right)$ , the average probability of $\text{P}\left(x\right)$ as follows.

$E\left(\text{P}\left(X\right)\right)=\underset{x\to \infty }{\lim }\frac{1}{x}\cdot {\displaystyle {\sum }_{i=1}^x\text{P}\left(i\right)}=\underset{x\to \infty }{\lim }\frac{1}{x}\cdot {\displaystyle {\sum }_{i=1}^x\frac{\left|S\left(i\right)\right|}{i}}=\underset{x\to \infty }{\lim }\frac{1}{x}\cdot {\displaystyle {\sum }_{i=1}^x\frac{\phi \left(i\right)}{i}}$ .

Let $\psi \left(x\right)={\displaystyle {\sum }_{i=1}^x\phi \left(i\right)}$ .

Then, the following result holds.

Theorem 4. $E\left(\text{P}\left(X\right)\right)=\frac{6}{{\pi }^2}=0.6079271\cdots$ .

Proof: First, we derive $\phi \left(n\right)$ along the lines of Dirichlet [4] . It is well-known that

${\displaystyle {\sum }_{\delta |n}\phi \left(\delta \right)}=n$ (4)

for example, in [5] . Summing up both sides for $n,n-1,\cdots ,1$ ,

${\displaystyle {\sum }_{s=1}^n\left[\frac{n}{s}\right]\phi \left(s\right)}=\frac{1}{2}{n}^2+\frac{1}{2}n$ . (5)

For $\left[\frac{n}{s}\right]=t$ , it follows that

$\left(\psi \left(\left[\frac{n}{t}\right]\right)-\psi \left(\left[\frac{n}{t+1}\right]\right)\right)t=\left(\phi \left(\left[\frac{n}{t+1}\right]+1\right)+\cdots +\phi \left(\left[\frac{n}{t}\right]\right)\right)t$

because $\left[\frac{n}{t+1}\right]<s\le \left[\frac{n}{t}\right]$ . We regard the right hand side as $\phi \left(\left[\frac{n}{t}\right]\right)t$ if $\left[\frac{n}{t+1}\right]+1=\left[\frac{n}{t}\right]$ , and as 0 if $\left[\frac{n}{t+1}\right]=\left[\frac{n}{t}\right]$ .

Therefore, (4) turns out to be

${\displaystyle {\sum }_{s=1}^n\left[\frac{n}{s}\right]\phi \left(s\right)}={\displaystyle {\sum }_{s=1}^n\psi \left(\left[\frac{n}{s}\right]\right)}$ . (6)

Hence,

${\displaystyle {\sum }_{s=1}^n\psi \left(\left[\frac{n}{s}\right]\right)}=\frac{1}{2}{n}^2+\frac{1}{2}n$ . (7)

We put

$\psi \left(n\right)=\frac{3}{{\pi }^2}{n}^2+\zeta \chi \left(n\right)$ , $\exists \zeta \text{for}n$ . (8)

By (7),

$\psi \left(n\right)=-{\displaystyle {\sum }_{s=2}^n\psi \left(\left[\frac{n}{s}\right]\right)}+\frac{1}{2}{n}^2+\frac{1}{2}n$ . (9)

By (8),

$\begin{array}{l}-{\displaystyle {\sum }_{s=2}^n\psi \left(\left[\frac{n}{s}\right]\right)}=-{\displaystyle {\sum }_{s=2}^n\left(\frac{3}{{\pi }^2}{\left[\frac{n}{s}\right]}^2+\zeta \chi \left(\left[\frac{n}{s}\right]\right)\right)}\\ =-\frac{3}{{\pi }^2}{\displaystyle {\sum }_{s=2}^n{\left(\frac{n}{s}-\epsilon \right)}^2}-{\displaystyle {\sum }_{s=2}^{\infty }\zeta \chi }\left(\left[\frac{n}{s}\right]\right),0\le \epsilon <1\\ =-\frac{3n^2}{{\pi }^2}{\displaystyle {\sum }_{s=2}^n\frac{1}{s^2}}+\frac{6n}{{\pi }^2}{\displaystyle {\sum }_{s=2}^n\frac{\epsilon }{s}}-\frac{3}{{\pi }^2}{\displaystyle {\sum }_{s=2}^n{\epsilon }^2}-{\displaystyle {\sum }_{s=2}^{\infty }\zeta \chi \left(\left[\frac{n}{s}\right]\right)}\\ =-\frac{3n^2}{{\pi }^2}\left(\frac{{\pi }^2}{6}-1+\tau \right)+\frac{6n}{{\pi }^2}{\displaystyle {\sum }_{s=2}^n\frac{\epsilon }{s}}-\frac{3}{{\pi }^2}{\displaystyle {\sum }_{s=2}^n{\epsilon }^2}-{\displaystyle {\sum }_{s=2}^{\infty }\zeta \chi \left(\left[\frac{n}{s}\right]\right)}\\ =-\frac{1}{2}{n}^2+\frac{3}{{\pi }^2}{n}^2+Pn\log n+B{\displaystyle {\sum }_{s=2}^{\infty }\chi }\left(\frac{n}{s}\right),\exists P,\exists B\end{array}$

Substituting this back into (9),

$\psi \left(n\right)=\frac{3}{{\pi }^2}{n}^2+Pn\log n+A{\displaystyle {\sum }_{s=2}^{\infty }\chi }\left(\frac{n}{s}\right)$ , $\exists P,\exists A$ (10)

From (8) and (10),

$\zeta \chi \left(n\right)=Pn\log n+A{\displaystyle {\sum }_{s=2}^{\infty }\chi }(\; n\; s\; )$

$\zeta =\frac{Pn\log n}{\chi \left(n\right)}+\frac{A}{\chi \left(n\right)}{\displaystyle {\sum }_{s=2}^{\infty }\chi }\left(\frac{n}{s}\right)$ .

We can write

$\chi \left(n\right)=n^{\delta }$ ,

where $\delta$ is a constant satisfying

${\displaystyle {\sum }_{s=2}^n\frac{1}{s^{\delta }}}<{\displaystyle {\sum }_{s=2}^{\infty }\frac{1}{s^{\delta }}}=q$ , $1<\delta <2$ .

Hence,

$\zeta =\frac{Pn\log n}{\chi \left(n\right)}+\frac{A}{n^{\delta }}{\displaystyle {\sum }_{s=2}^{\infty }{\left(\frac{n}{s}\right)}^{\delta }}=\frac{Pn\log n}{n^{\delta }}+Aq$

for $\forall k>0$ , $\frac{Pn\log n}{n^{\delta }}<k$ , $n\ge N$ ,

Which implies

$A^{\prime }<k+Aq$ , $\exists A^{\prime }$ .

Especially, if we use $\delta$ satisfying

${\displaystyle {\sum }_{s=2}^{\infty }\frac{1}{s^{\delta }}}=1$ , (11)

we obtain

$A^{\prime }<A$ , $n\gg N$ .

Therefore, it follows that

$\psi \left(n\right)=\frac{3}{{\pi }^2}{n}^2+A^{\prime }{n}^{\delta }$ , $1<\delta <2$ .

Thus,

$\begin{array}{c}\phi \left(x\right)=\psi \left(x\right)-\psi \left(x-1\right)=\frac{3}{{\pi }^2}\left(x^2-{\left(x-1\right)}^2\right)+A^{\prime }\left(x^{\delta }-{\left(x-1\right)}^{\delta }\right)\\ =\frac{6}{{\pi }^2}x+o\left(x\right),x:\text{integer}\end{array}$

this is because ${\left(x-1\right)}^{\delta }=x^{\delta }+\delta x^{\delta -1}\left(-1\right)+\cdots$ by the Taylor expansion.

Hence,

$E\left(\text{P}\left(X\right)\right)=\underset{x\to \infty }{\lim }\frac{1}{x}\cdot {\displaystyle {\sum }_{i=1}^x\frac{\phi \left(i\right)}{i}}=\frac{6}{{\pi }^2}+\underset{x\to \infty }{\lim }\frac{1}{x}\cdot x\cdot o\left(1\right)=\frac{6}{{\pi }^2}$ . (12)

□

We conducted an elementary computational experiment, in which we computed $\frac{1}{x}\cdot {\displaystyle {\sum }_{i=1}^x\frac{\phi \left(i\right)}{i}},x=1,\cdots ,120$ using Python (Figure 1). Figure 1 shows the validity of the result.

Figure 1. Average probability of an element being a generator.

4. Conclusions

In this study, we have proved that the average probability of an element being a generator in the cyclic group is $6/{\pi }^2$ . It is interesting that this value is equal to the value of Lemma 1. This is evident in the following discussion.

Consider $\left(j,k\right),j=1,\cdots ,x;k=1,\cdots ,x$ . Note that $\left(j,j\right)$ is coprime for $j=1$ and not coprime for $j=2,\cdots ,x$ . Then,

$\begin{array}{l}\mathrm{Pr}\left\{\left(j,k\right)\text{are}\text{coprime}\text{integers}|j=1,\cdots ,x;k=1,\cdots ,x\right\}\\ ={\displaystyle {\sum }_{k=1}^x\mathrm{Pr}}\left\{\left(\left(j,k\right),j\le k\right)\text{arecoprimeintegers}|j=1,\cdots ,k\right\}\\ +{\displaystyle {\sum }_{j=1}^x\mathrm{Pr}}\left\{\left(\left(j,k\right),j\ge k\right)\text{arecoprimeintegers}|k=1,\cdots ,j\right\}\\ -{\displaystyle {\sum }_{j=1}^x\mathrm{Pr}}\left\{\left(j,j\right)\text{arecoprime}\text{integers}\right\}\end{array}$

$\begin{array}{l}=\frac{1}{2}\left(1+\frac{1}{x}\right)\cdot \frac{1}{x}\cdot {\displaystyle {\sum }_{k=1}^x\frac{\phi \left(k\right)}{k}}+\frac{1}{2}\left(1+\frac{1}{x}\right)\cdot \frac{1}{x}\cdot {\displaystyle {\sum }_{j=1}^x\frac{\phi \left(j\right)}{j}}-\frac{1}{x^2}\\ =\frac{1}{x}\cdot {\displaystyle {\sum }_{i=1}^x\frac{\phi \left(i\right)}{i}}+\frac{1}{x^2}\cdot {\displaystyle {\sum }_{i=1}^x\frac{\phi \left(i\right)}{i}}-\frac{1}{x^2}\\ \underset{x\to \infty }{\to }\underset{x\to \infty }{\lim }\frac{1}{x}\cdot {\displaystyle {\sum }_{i=1}^x\frac{\phi \left(i\right)}{i}}=E(P(\; X\; ))\end{array}$

We would like to further clarify the asymptotic property of $\text{P}\left(x\right)=\phi \left(x\right)/x$ itself, which seems like $\phi \left(x\right)/x\stackrel{P}{\to }6/{\pi }^2$ when $x\to \infty$ , in our future work.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Wang, S.D. (2022) A Study of the Use of Euler Totient Function Is RSA Cryptosystem and the Future of RSA Cryptosystem. Journal of Physics: Conference Series, 2386, Article ID: 012030. https://doi.org/10.1088/1742-6596/2386/1/012030
[2]	Haukkanen, P. (2002) On an Inequality Related to the Legendre Totient Function. Journal of Inequalities in Pure and Applied Mathematics, 3, Article 37.
[3]	Zhai, W.G. (2020) On a Sum Involving the Euler Function. Journal of Number Theory, 211, 199-219. https://doi.org/10.1016/j.jnt.2019.10.003
[4]	Dirichlet, G.L. (1849) über die Bestimmung der mittleren Werthe in der Zahlentheorie. Verlag nicht ermittelbar, Berlin. (Reprinted in G. Lejeune Dirichlet’s Werke, Chelsea Publishing Company, New York, 1969).
[5]	Dirichlet, G.L. and Dedekind, R. (1879) Vorlesungen über Zahlentheorie Braunschweig. Cambridge University Press, Cambridge.
[6]	Chen, Y.-P. (2012) A Probabilistic Look at Series Involving Euler’s Totient Function. Integers, 12, 649-657. https://doi.org/10.1515/integers-2011-0125
[7]	Dirichlet, G.L. (1837) Beweis des Satzes, dass jede unbegrentze arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält. Abhandlungen der Königlichen Preussischen Akademie der Wissenschaften zu Berlin, 48, 45-71. arXiv:0808.1408v2 (2014).
[8]	Kendall, R. and Osborn, R. (1965) Two Simple Lower Bounds for the Euler ϕ-Function. Texas Journal of Science, 17, 324-326.