Average order in cyclic groups

Joachim von zur Gathen; Arnold Knopfmacher; Florian Luca; Lutz G. Lucht; Igor E. Shparlinski

doi:10.5802/jtnb.436

Joachim von zur Gathen ¹ ; Arnold Knopfmacher ² ; Florian Luca ³ ; Lutz G. Lucht ⁴ ; Igor E. Shparlinski ⁵

¹ Fakultät für Elektrotechnik, Informatik und Mathematik Universität Paderborn, 33095 Paderborn, Germany
² The John Knopfmacher Centre for Applicable Analysis and Number Theory University of the Witwatersrand P.O. Wits 2050, South Africa
³ Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58180, Morelia, Michoacán, México
⁴ Institut für Mathematik TU Clausthal, Erzstraße 1 38678 Clausthal-Zellerfeld, Germany
⁵ Department of Computing Macquarie University Sydney, NSW 2109, Australia

Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 107-123.

Pour chaque entier naturel $n$ , nous déterminons l’ordre moyen $α (n)$ des éléments du groupe cyclique d’ordre $n$ . Nous montrons que plus de la moitié de la contribution à $α (n)$ provient des $ϕ (n)$ éléments primitifs d’ordre $n$ . Il est par conséquent intéressant d’étudier également la fonction $β (n) = α (n) / ϕ (n)$ . Nous déterminons le comportement moyen de $α$ , $β$ , $1 / β$ et considérons aussi ces fonctions dans le cas du groupe multiplicatif d’un corps fini.

For each natural number $n$ we determine the average order $α (n)$ of the elements in a cyclic group of order $n$ . We show that more than half of the contribution to $α (n)$ comes from the $ϕ (n)$ primitive elements of order $n$ . It is therefore of interest to study also the function $β (n) = α (n) / ϕ (n)$ . We determine the mean behavior of $α$ , $β$ , $1 / β$ , and also consider these functions in the multiplicative groups of finite fields.

MR Zbl

DOI : 10.5802/jtnb.436

Affiliations des auteurs :

Joachim von zur Gathen&hairsp;¹ ; Arnold Knopfmacher&hairsp;² ; Florian Luca&hairsp;³ ; Lutz G. Lucht&hairsp;⁴ ; Igor E. Shparlinski&hairsp;⁵

¹ Fakultät für Elektrotechnik, Informatik und Mathematik Universität Paderborn, 33095 Paderborn, Germany
² The John Knopfmacher Centre for Applicable Analysis and Number Theory University of the Witwatersrand P.O. Wits 2050, South Africa
³ Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58180, Morelia, Michoacán, México
⁴ Institut für Mathematik TU Clausthal, Erzstraße 1 38678 Clausthal-Zellerfeld, Germany
⁵ Department of Computing Macquarie University Sydney, NSW 2109, Australia

@article{JTNB_2004__16_1_107_0,
     author = {Joachim von zur Gathen and Arnold Knopfmacher and Florian Luca and Lutz G. Lucht and Igor E. Shparlinski},
     title = {Average order in cyclic groups},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {107--123},
     publisher = {Universit\'e Bordeaux 1},
     volume = {16},
     number = {1},
     year = {2004},
     doi = {10.5802/jtnb.436},
     mrnumber = {2145575},
     zbl = {1079.11003},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.436/}
}

TY  - JOUR
AU  - Joachim von zur Gathen
AU  - Arnold Knopfmacher
AU  - Florian Luca
AU  - Lutz G. Lucht
AU  - Igor E. Shparlinski
TI  - Average order in cyclic groups
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2004
SP  - 107
EP  - 123
VL  - 16
IS  - 1
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.436/
DO  - 10.5802/jtnb.436
LA  - en
ID  - JTNB_2004__16_1_107_0
ER  -

%0 Journal Article
%A Joachim von zur Gathen
%A Arnold Knopfmacher
%A Florian Luca
%A Lutz G. Lucht
%A Igor E. Shparlinski
%T Average order in cyclic groups
%J Journal de théorie des nombres de Bordeaux
%D 2004
%P 107-123
%V 16
%N 1
%I Université Bordeaux 1
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.436/
%R 10.5802/jtnb.436
%G en
%F JTNB_2004__16_1_107_0

Joachim von zur Gathen; Arnold Knopfmacher; Florian Luca; Lutz G. Lucht; Igor E. Shparlinski. Average order in cyclic groups. Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 107-123. doi : 10.5802/jtnb.436. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.436/

[1] T. M. Apostol (1976), Introduction to Analytic Number Theory. Springer-Verlag, New York. | MR | Zbl

[2] P. T. Bateman (1972) . The distribution of values of the Euler function. Acta Arithmetica 21, 329–345. | MR | Zbl

[3] C. K. Caldwell & Y. Gallot (2000), Some results for $n! \pm 1$ and $2 \cdot 3 \cdot 5 \dots p \pm 1$ . Preprint.

[4] J. R. Chen (1973), On the representation of a large even integer as a sum of a prime and a product of at most two primes. Scientia Sinica 16, 157–176. | MR | Zbl

[5] P. D. T. A. Elliott (1985), Arithmetic functions and integer products, volume 272 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, New York. | MR | Zbl

[6] K. Ford (1999), The number of solutions of $φ (x) = m$ . Annals of Mathematics 150, 1–29. | MR | Zbl

[7] H. Halberstam & H.E. Richert (1974), Sieve Methods. Academic Press. | MR | Zbl

[8] G. H. Hardy & E. M. Wright (1962), An introduction to the theory of numbers. Clarendon Press, Oxford. 1st edition 1938. | MR | Zbl

[9] K.-H. Indlekofer (1980), A mean-value theorem for multiplicative functions. Mathematische Zeitschrift 172, 255–271. | MR | Zbl

[10] K.-H. Indlekofer (1981), Limiting distributions and mean-values of multiplicative arithmetical functions. Journal für die reine und angewandte Mathematik 328, 116–127. | MR | Zbl

[11] W. Keller (2000). Private communication.

[12] D. G. Kendall & R. A. Rankin (1947), On the number of Abelian groups of a given order. Quarterly Journal of Mathematics 18, 197–208. | MR | Zbl

[13] J. Knopfmacher (1972), Arithmetical properties of finite rings and algebras, and analytic number theory. II. Journal für die reine und angewandte Mathematik 254, 74–99. | MR | Zbl

[14] J. Knopfmacher (1973), A prime divisor function. Proceedings of the American Mathematical Society 40, 373–377. | MR | Zbl

[15] J. Knopfmacher & J. N. Ridley (1974), Prime-Independent Arithmetical Functions. Annali di Matematica 101(4), 153–169. | MR | Zbl

[16] W. LeVeque (1977), Fundamentals of Number Theory. Addison-Wesley. | MR | Zbl

[17] H. L. Montgomery (1970), Primes in arithmetic progressions. Michigan Mathematical Journal 17, 33–39. | MR | Zbl

[18] H. L. Montgomery (1987), fluctuations in the mean of Euler’s phi function. Proceedings of the Indian Academy of Sciences (Mathematical Sciences) 97(1-3), 239–245. | MR | Zbl

[19] A. G. Postnikov (1988), Introduction to analytic number theory. Volume 68 of Translations of Mathematical Monographs. American Mathematical Society, Providence, RI. | MR | Zbl

[20] H. Riesel & R. C. Vaughan (1983), On sums of primes. Arkiv for Matematik 21(1), 46–74. | MR | Zbl

[21] I. E. Shparlinski (1990), Some arithmetic properties of recurrence sequences. Matematicheskie Zametki 47(6), 124–131. (in Russian); English translation in Mathematical Notes 47, (1990), 612–617. | MR | Zbl

[22] P. J. Stephens (1969), An Average Result for Artin’s Conjecture. Mathematika 16(31), 178–188. | MR | Zbl

[23] A. Walfisz (1963), Weylsche Exponentialsummen in der neueren Zahlentheorie. Number 15 in Mathematische Forschungsberichte. VEB Deutscher Verlag der Wissenschaften, Berlin. | MR | Zbl

Cité par Sources :