Average order in cyclic groups

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

Journal de Théorie des Nombres de Bordeaux (2004)

  • Volume: 16, Issue: 1, page 107-123
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

von zur Gathen, Joachim, et al. "Average order in cyclic groups." Journal de Théorie des Nombres de Bordeaux 16.1 (2004): 107-123. <http://eudml.org/doc/249256>.

@article{vonzurGathen2004,
abstract = {For each natural number $n$ we determine the average order $\alpha (n)$ of the elements in a cyclic group of order $n$. We show that more than half of the contribution to $\alpha (n)$ comes from the $\varphi (n)$ primitive elements of order $n$. It is therefore of interest to study also the function $\beta (n)=\alpha (n)/\varphi (n)$. We determine the mean behavior of $\alpha $, $\beta $, $1/\beta $, and also consider these functions in the multiplicative groups of finite fields.},
affiliation = {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},
author = {von zur Gathen, Joachim, Knopfmacher, Arnold, Luca, Florian, Lucht, Lutz G., Shparlinski, Igor E.},
journal = {Journal de Théorie des Nombres de Bordeaux},
language = {eng},
number = {1},
pages = {107-123},
publisher = {Université Bordeaux 1},
title = {Average order in cyclic groups},
url = {http://eudml.org/doc/249256},
volume = {16},
year = {2004},
}

TY - JOUR
AU - von zur Gathen, Joachim
AU - Knopfmacher, Arnold
AU - Luca, Florian
AU - Lucht, Lutz G.
AU - Shparlinski, Igor E.
TI - Average order in cyclic groups
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2004
PB - Université Bordeaux 1
VL - 16
IS - 1
SP - 107
EP - 123
AB - For each natural number $n$ we determine the average order $\alpha (n)$ of the elements in a cyclic group of order $n$. We show that more than half of the contribution to $\alpha (n)$ comes from the $\varphi (n)$ primitive elements of order $n$. It is therefore of interest to study also the function $\beta (n)=\alpha (n)/\varphi (n)$. We determine the mean behavior of $\alpha $, $\beta $, $1/\beta $, and also consider these functions in the multiplicative groups of finite fields.
LA - eng
UR - http://eudml.org/doc/249256
ER -

References

top
  1. T. M. Apostol (1976), Introduction to Analytic Number Theory. Springer-Verlag, New York. Zbl0335.10001MR434929
  2. P. T. Bateman (1972) . The distribution of values of the Euler function. Acta Arithmetica 21, 329–345. Zbl0217.31901MR302586
  3. C. K. Caldwell & Y. Gallot (2000), Some results for n ! ± 1 and 2 · 3 · 5 ⋯ p ± 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. Zbl0319.10056MR434997
  5. P. D. T. A. Elliott (1985), Arithmetic functions and integer products, volume 272 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, New York. Zbl0559.10032MR766558
  6. K. Ford (1999), The number of solutions of φ ( x ) = m . Annals of Mathematics 150, 1–29. Zbl0978.11053MR1715326
  7. H. Halberstam & H.E. Richert (1974), Sieve Methods. Academic Press. Zbl0298.10026MR424730
  8. G. H. Hardy & E. M. Wright (1962), An introduction to the theory of numbers. Clarendon Press, Oxford. 1st edition 1938. Zbl0020.29201MR67125
  9. K.-H. Indlekofer (1980), A mean-value theorem for multiplicative functions. Mathematische Zeitschrift 172, 255–271. Zbl0416.10035MR581443
  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. Zbl0455.10036MR636199
  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. Zbl0031.15303MR22569
  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. Zbl0246.10033MR364132
  14. J. Knopfmacher (1973), A prime divisor function. Proceedings of the American Mathematical Society 40, 373–377. Zbl0267.10059MR327694
  15. J. Knopfmacher & J. N. Ridley (1974), Prime-Independent Arithmetical Functions. Annali di Matematica 101(4), 153–169. Zbl0293.10026MR392872
  16. W. LeVeque (1977), Fundamentals of Number Theory. Addison-Wesley. Zbl0368.10001MR480290
  17. H. L. Montgomery (1970), Primes in arithmetic progressions. Michigan Mathematical Journal 17, 33–39. Zbl0209.34804MR257005
  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. Zbl0656.10042MR983617
  19. A. G. Postnikov (1988), Introduction to analytic number theory. Volume 68 of Translations of Mathematical Monographs. American Mathematical Society, Providence, RI. Zbl0641.10001MR932727
  20. H. Riesel & R. C. Vaughan (1983), On sums of primes. Arkiv for Matematik 21(1), 46–74. Zbl0516.10044MR706639
  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. Zbl0714.11009MR1074537
  22. P. J. Stephens (1969), An Average Result for Artin’s Conjecture. Mathematika 16(31), 178–188. Zbl0186.08402MR498449
  23. A. Walfisz (1963), Weylsche Exponentialsummen in der neueren Zahlentheorie. Number 15 in Mathematische Forschungsberichte. VEB Deutscher Verlag der Wissenschaften, Berlin. Zbl0146.06003MR220685

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.