×
Garaev, Moubariz Z.; Luca, Florian; Shparlinski, Igor E.

Character sums and congruences with \(n!\). (English) Zbl 1060.11046

Trans. Am. Math. Soc. 356, No. 12, 5089-5102 (2004).
The authors are interested in the distribution of the values of \(n!\) modulo a prime \(p\), possibly when \(n\) is of restricted size mod \(p\). They show, for example, that every \(a \not\equiv 0 \bmod p\) is representable as a product of seven factorials \(\prod n_ i!\), with \(n_ i \ll p^ {11/12+\varepsilon}\), and that if one only requires most integers to be representable then a product of four of these factorials is enough. If the factorials are restricted by \(n_ i \ll p^ {1/2+\varepsilon}\) then they need \(5 + \lfloor\varepsilon^ {-1}\rfloor\) factorials. They also show that when \(n \ll p^ {5/6+\varepsilon}\) the products of three such factorials are uniformly distributed mod \(p\).
Other results in the paper are that there is a value of \(n\) with \(n \ll p^ {1/2+\varepsilon}\) and \(n!\) a primitive root mod \(p\), and an inference from the behaviour of a sum of Legendre symbols \(\sum\bigl( n!/p\bigr)\) to a result on the distribution of quadratic nonresidues mod \(p\).
These results are derived via estimates for character sums involving factorials, for which they invoke Weil’s bounds.
Some of the results of this paper have been applied, in preprints by Luca and Shparlinski, to improvements on a result [J. Lond.Math.Soc., II. Ser.13, 513–519 (1976; Zbl 0332.10028)] of P. Erdős and C. Stewart on the prime factors of \(n!\pm 1\), and to other questions about expressions of the form \(n!+f(n)\), for polynomials \(f\).
Some other aspects of the behaviour of \(n!\), mod \(p\) are discussed in the paper [J. Ramanujan Math. Soc. 15, No. 2, 135–154 (2000; Zbl 0962.11005)] by C. Cobeli, M. Vâjâitu and A. Zaharescu.
Reviewer: George Greaves (Cardiff)

Cited in 5 Reviews
Cited in 14 Documents

MSC:

11L40 Estimates on character sums
11B65 Binomial coefficients; factorials; \(q\)-identities
11A07 Congruences; primitive roots; residue systems

Keywords:

products of factorials; quadratic nonresidues; uniform distribution

Citations:

Zbl 0332.10028; Zbl 0962.11005
PDF BibTeX XML Cite
\textit{M. Z. Garaev} et al., Trans. Am. Math. Soc. 356, No. 12, 5089--5102 (2004; Zbl 1060.11046)
Full Text: DOI arXiv

References:

[1] J. H. H. Chalk, Polynomial congruences over incomplete residue systems, modulo \?, Nederl. Akad. Wetensch. Indag. Math. 51 (1989), no. 1, 49 – 62. · Zbl 0683.10031
[2] C. Cobeli, M. Vâjâitu, and A. Zaharescu, The sequence \?!\pmod\?, J. Ramanujan Math. Soc. 15 (2000), no. 2, 135 – 154. · Zbl 0962.11005
[3] 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. · Zbl 1032.11035
[4] Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. · Zbl 0877.11043
[5] P. Erdős and C. L. Stewart, On the greatest and least prime factors of \?!+1, J. London Math. Soc. (2) 13 (1976), no. 3, 513 – 519. · Zbl 0332.10028
[6] M. Z. Garaev and F. Luca, ‘On a theorem of A. Sárközy and applications’, Preprint, 2003.
[7] 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. · Zbl 0805.11001
[8] A. A. Karacuba, The distribution of products of shifted prime numbers in arithmetic progressions, Dokl. Akad. Nauk SSSR 192 (1970), 724 – 727 (Russian).
[9] 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. · Zbl 0830.11003
[10] L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. · Zbl 0281.10001
[11] Pär Kurlberg and Zeév Rudnick, The distribution of spacings between quadratic residues, Duke Math. J. 100 (1999), no. 2, 211 – 242. · Zbl 0985.11038
[12] W. C. Winnie Li, Number theory with applications, Series on University Mathematics, vol. 7, World Scientific Publishing Co., Inc., River Edge, NJ, 1996. · Zbl 0849.11006
[13] 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. · Zbl 1139.11053
[14] F. Luca and I. E. Shparlinski, ‘Prime divisors of shifted factorials’, Preprint, 2003. · Zbl 1098.11047
[15] F. Luca and I. E. Shparlinski, ‘On the largest prime factor of \(n!+2^n-1\)’, Preprint, 2003. · Zbl 1097.11006
[16] F. Luca and P. Stanica, ‘Products of factorials modulo \(p\)’, Colloq. Math., 96 (2003), 191-205. · Zbl 1042.11002
[17] B. Rokowska and A. Schinzel, Sur un problème de M. Erdős, Elem. Math. 15 (1960), 84 – 85 (French). · Zbl 0089.26603
[18] André Weil, Basic number theory, 3rd ed., Springer-Verlag, New York-Berlin, 1974. Die Grundlehren der Mathematischen Wissenschaften, Band 144. · Zbl 0326.12001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.