Average order in cyclic groups
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.

@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 = {jtnb.centre-mersenne.org/item/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/item/JTNB_2004__16_1_107_0/

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

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

[3] C. K. Caldwell & Y. Gallot (2000), Some results for n!±1 and 2·3·5p±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 434997 | Zbl 0319.10056

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

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

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

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

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

[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 636199 | Zbl 0455.10036

[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 22569 | Zbl 0031.15303

[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 364132 | Zbl 0246.10033

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

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

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

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

[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 983617 | Zbl 0656.10042

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

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

[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 1074537 | Zbl 0714.11009

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

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