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
Published electronically: June 29, 2004
MathSciNet review: 2084412
Full-text PDF Free Access

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 \ |\ 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?)

  • J. H. H. Chalk, Polynomial congruences over incomplete residue systems, modulo $k$, Nederl. Akad. Wetensch. Indag. Math. 51 (1989), no. 1, 49–62. MR 993678
  • C. Cobeli, M. Vâjâitu, and A. Zaharescu, The sequence $n!\pmod p$, J. Ramanujan Math. Soc. 15 (2000), no. 2, 135–154. MR 1754715
  • Todd Cochrane and Zhiyong Zheng, A survey on pure and mixed exponential sums modulo prime powers, Number theory for the millennium, I (Urbana, IL, 2000) A K Peters, Natick, MA, 2002, pp. 273–300. MR 1956230
  • Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
  • P. Erdős and C. L. Stewart, On the greatest and least prime factors of $n!+1$, J. London Math. Soc. (2) 13 (1976), no. 3, 513–519. MR 409334, DOI
  • M. Z. Garaev and F. Luca, ‘On a theorem of A. Sárközy and applications’, Preprint, 2003.
  • Richard K. Guy, Unsolved problems in number theory, 2nd ed., Problem Books in Mathematics, Springer-Verlag, New York, 1994. Unsolved Problems in Intuitive Mathematics, I. MR 1299330
  • A. A. Karacuba, The distribution of products of shifted prime numbers in arithmetic progressions, Dokl. Akad. Nauk SSSR 192 (1970), 724–727 (Russian). MR 0269611
  • S. V. Konyagin and T. Steger, Polynomial congruences, Mat. Zametki 55 (1994), no. 6, 73–79, 158 (Russian, with Russian summary); English transl., Math. Notes 55 (1994), no. 5-6, 596–600. MR 1296013, DOI
  • L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0419394
  • Pär Kurlberg and Zeév Rudnick, The distribution of spacings between quadratic residues, Duke Math. J. 100 (1999), no. 2, 211–242. MR 1722952, DOI
  • W. C. Winnie Li, Number theory with applications, Series on University Mathematics, vol. 7, World Scientific Publishing Co., Inc., River Edge, NJ, 1996. MR 1390759
  • Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
  • F. Luca and I. E. Shparlinski, ‘Prime divisors of shifted factorials’, Preprint, 2003.
  • F. Luca and I. E. Shparlinski, ‘On the largest prime factor of $n!+2^n-1$’, Preprint, 2003.
  • F. Luca and P. Stănică, ‘Products of factorials modulo $p$’, Colloq. Math., 96 (2003), 191–205.
  • B. Rokowska and A. Schinzel, Sur un problème de M. Erdős, Elem. Math. 15 (1960), 84–85 (French). MR 117188
  • André Weil, Basic number theory, 3rd ed., Springer-Verlag, New York-Berlin, 1974. Die Grundlehren der Mathematischen Wissenschaften, Band 144. MR 0427267

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
MR Author ID: 632163

Florian Luca
Affiliation: Instituto de Matemáticas, Universidad Nacional Autónoma de México, C.P. 58180, Morelia, Michoacán, México
MR Author ID: 630217

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
MR Author ID: 192194

Received by editor(s): September 29, 2003
Published electronically: June 29, 2004
Article copyright: © Copyright 2004 American Mathematical Society