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