Average order in cyclic groups
Journal de théorie des nombres de Bordeaux, Volume 16 (2004) no. 1, pp. 107-123.

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.

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.

DOI: 10.5802/jtnb.436
Joachim von zur Gathen 1; Arnold Knopfmacher 2; Florian Luca 3; Lutz G. Lucht 4; Igor E. Shparlinski 5

1 Fakultät für Elektrotechnik, Informatik und Mathematik Universität Paderborn, 33095 Paderborn, Germany
2 The John Knopfmacher Centre for Applicable Analysis and Number Theory University of the Witwatersrand P.O. Wits 2050, South Africa
3 Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58180, Morelia, Michoacán, México
4 Institut für Mathematik TU Clausthal, Erzstraße 1 38678 Clausthal-Zellerfeld, Germany
5 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
DA  - 2004///
SP  - 107
EP  - 123
VL  - 16
IS  - 1
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.436/
UR  - https://www.ams.org/mathscinet-getitem?mr=2145575
UR  - https://zbmath.org/?q=an%3A1079.11003
UR  - https://doi.org/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://doi.org/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, Volume 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!±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 | 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

Cited by Sources: