## Character sums and congruences with $n!$

HTML articles powered by AMS MathViewer

- by Moubariz Z. Garaev, Florian Luca and Igor E. Shparlinski PDF
- Trans. Amer. Math. Soc.
**356**(2004), 5089-5102 Request permission

## 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

- 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**, DOI 10.1016/S1385-7258(89)80016-2 - 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**, DOI 10.1007/BFb0093404 - 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 10.1112/jlms/s2-13.3.513 - 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**, DOI 10.1007/978-1-4899-3585-4 - 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 10.1007/BF02110354 - L. Kuipers and H. Niederreiter,
*Uniform distribution of sequences*, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. 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 10.1215/S0012-7094-99-10008-1 - 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**, DOI 10.1142/2716 - 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., Die Grundlehren der mathematischen Wissenschaften, Band 144, Springer-Verlag, New York-Berlin, 1974. MR**0427267**, DOI 10.1007/978-3-642-61945-8

## 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
- 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
- MR Author ID: 630217
- Email: fluca@matmor.unam.mx
**Igor E. Shparlinski**- Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
- MR Author ID: 192194
- Email: igor@ics.mq.edu.au
- Received by editor(s): September 29, 2003
- Published electronically: June 29, 2004
- © Copyright 2004 American Mathematical Society
- 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
- MathSciNet review: 2084412