Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Character sums and congruences with $n!$


Authors: Moubariz Z. Garaev, Florian Luca and Igor E. Shparlinski
Journal: Trans. Amer. Math. Soc. 356 (2004), 5089-5102
MSC (2000): Primary 11A07, 11B65, 11L40
DOI: https://doi.org/10.1090/S0002-9947-04-03612-8
Published electronically: June 29, 2004
MathSciNet review: 2084412
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We estimate character sums with $n!$, on average, and individually. These bounds are used to derive new results about various congruences modulo a prime $p$ and obtain new information about the spacings between quadratic nonresidues modulo $p$. In particular, we show that there exists a positive integer $n\ll p^{1/2+\varepsilon}$ such that $n!$ is a primitive root modulo $p$. We also show that every nonzero congruence class $a \not \equiv 0 \pmod p$can be represented as a product of 7 factorials, $a \equiv n_1! \ldots n_7! \pmod p$, where $\max \{n_i \vert i=1,\ldots, 7\}=O(p^{11/12+\varepsilon})$, and we find the asymptotic formula for the number of such representations. Finally, we show that products of 4 factorials $n_1!n_2!n_3!n_4!,$ with $\max\{n_1, n_2, n_3, n_4\}=O(p^{6/7+\varepsilon})$ represent ``almost all'' residue classes modulo p, and that products of 3 factorials $n_1!n_2!n_3!$ with $\max\{n_1, n_2, n_3\}=O(p^{5/6+\varepsilon})$ are uniformly distributed modulo $p$.


References [Enhancements On Off] (What's this?)

  • 1. J. H. H. Chalk, `Polynomial congruences over incomplete residue systems modulo $k$', Proc. Kon. Ned. Acad. Wetensch., A92 (1989), 49-62. MR 90e:11050
  • 2. C. Cobeli, M. Vâjâitu and A. Zaharescu, `The sequence $n! \pmod p$', J. Ramanujan Math. Soc., 15 (2000), 135-154. MR 2001g:11153
  • 3. T. Cochrane and Z. Y. Zheng, `A survey on pure and mixed exponential sums modulo prime powers', Proc. Illinois Millennial Conf. on Number Theory, Vol.1, A.K. Peters, Natick, MA, 2002, pp. 271-300. MR 2004b:11120
  • 4. M. Drmota and R. Tichy, Sequences, discrepancies and applications, Springer-Verlag, Berlin, 1997. MR 98j:11057
  • 5. P. Erdos and C. Stewart, `On the greatest and least prime factors of $n!+1$', J. London Math. Soc., 13 (1976), 513-519.MR 53:13093
  • 6. M. Z. Garaev and F. Luca, `On a theorem of A. Sárközy and applications', Preprint, 2003.
  • 7. R. K. Guy, Unsolved problems in number theory, Springer-Verlag, New York, 1994. MR 96e:11002
  • 8. A. A. Karatsuba, `The distribution of products of shifted prime numbers in arithmetic progressions', Dokl. Akad. Nauk SSSR, 192 (1970), 724-727; English transl., Soviet Math. Dokl., 11 (1970), 701-711. MR 42:4506
  • 9. S. V. Konyagin and T. Steger, `Polynomial congruences', Matem. Zametki, 55 (1994), no. 1, 73-79; English transl., Math. Notes, 55 (1994), 596-600. MR 96e:11043
  • 10. L. Kuipers and H. Niederreiter, Uniform distribution of sequences, John Wiley, NY, 1974. MR 54:7415
  • 11. P. Kurlberg and Z. Rudnick, `The distribution of spacings between quadratic residues', Duke Math. J., 100 (1999), 211-242.MR 2000k:11109
  • 12. W.-C. W. Li, Number theory with applications, World Scientific, Singapore, 1996. MR 98b:11001
  • 13. R. Lidl and H. Niederreiter, Finite fields, Cambridge University Press, Cambridge, 1997. MR 97i:11115
  • 14. F. Luca and I. E. Shparlinski, `Prime divisors of shifted factorials', Preprint, 2003.
  • 15. F. Luca and I. E. Shparlinski, `On the largest prime factor of $n!+2^n-1$', Preprint, 2003.
  • 16. F. Luca and P. Stanica, `Products of factorials modulo $p$', Colloq. Math., 96 (2003), 191-205.
  • 17. B. Rokowska, A. Schinzel, `Sur une probléme de M. Erdos', Elem. Math., 15 (1960), 84-85. MR 22:7970
  • 18. A. Weil, Basic number theory, Springer-Verlag, New York, 1974.MR 55:302

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 11A07, 11B65, 11L40

Retrieve articles in all journals with MSC (2000): 11A07, 11B65, 11L40


Additional Information

Moubariz Z. Garaev
Affiliation: Instituto de Matemáticas, Universidad Nacional Autónoma de México, C.P. 58180, Morelia, Michoacán, México
Email: garaev@matmor.unam.mx

Florian Luca
Affiliation: Instituto de Matemáticas, Universidad Nacional Autónoma de México, C.P. 58180, Morelia, Michoacán, México
Email: fluca@matmor.unam.mx

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
Email: igor@ics.mq.edu.au

DOI: https://doi.org/10.1090/S0002-9947-04-03612-8
Received by editor(s): September 29, 2003
Published electronically: June 29, 2004
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society