Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T07:22:09.071Z Has data issue: false hasContentIssue false
  • English
  • Français

Subproducts of small residue classes

Part of: Exponential sums and character sums Elementary number theory

Published online by Cambridge University Press:  13 January 2021

Greg Martin  and
Amir Parvardi
Greg Martin*
Affiliation:
Department of Mathematics, University of British Columbia, Room 121, 1984 Mathematics Road, Vancouver, BCV6T 1Z2, Canada e-mail: [email protected]
Amir Parvardi
Affiliation:
Department of Mathematics, University of British Columbia, Room 121, 1984 Mathematics Road, Vancouver, BCV6T 1Z2, Canada e-mail: [email protected]
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

For any prime p, let $y(p)$ denote the smallest integer y such that every reduced residue class (mod p) is represented by the product of some subset of $\{1,\dots ,y\}$ . It is easy to see that $y(p)$ is at least as large as the smallest quadratic nonresidue (mod p); we prove that $y(p) \ll _\varepsilon p^{1/(4 \sqrt e)+\varepsilon }$ , thus strengthening Burgess’ classical result. This result is of intermediate strength between two other results, namely Burthe’s proof that the multiplicative group (mod p) is generated by the integers up to $O_\varepsilon (p^{1/(4 \sqrt e)+\varepsilon })$ , and Munsch and Shparlinski’s result that every reduced residue class (mod p) is represented by the product of some subset of the primes up to $O_\varepsilon (p^{1/(4 \sqrt e)+\varepsilon })$ . Unlike the latter result, our proof is elementary and similar in structure to Burgess’ proof for the least quadratic nonresidue.

Keywords

residue classesmultiplicative groupcharacter sums

MSC classification

Primary: 11A07: Congruences; primitive roots; residue systems
Secondary: 11L40: Estimates on character sums
Type
Article
Information
Canadian Mathematical Bulletin , Volume 65 , Issue 1 , March 2022 , pp. 1 - 8
Check for updates
Copyright
© Canadian Mathematical Society 2021

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Booker, A. R. and Pomerance, C., Squarefree smooth numbers and euclidean prime generators . Proc. Amer. Math. Soc. 145(2017), no. 12, 5035–5042. MR3717934.CrossRefGoogle Scholar
Burgess, D. A., The distribution of quadratic residues and non-residues . Mathematika 4(1957), 106–112. MR0093504.CrossRefGoogle Scholar
Burthe, R. J. Jr., Upper bounds for least witnesses and generating sets. Acta Arith. 80(1997), no. 4, 311–326. MR1450926.10.4064/aa-80-4-311-326CrossRefGoogle Scholar
Montgomery, H. L. and Vaughan, R. C., Multiplicative number theory. I. Classical theory. Cambridge Studies in Advanced Mathematics, 97, Cambridge University Press, Cambridge, 2007. MR2378655.Google Scholar
Munsch, M. and Shparlinski, I. E., On smooth square-free numbers in arithmetic progressions . J. Lond. Math. Soc. (2) 101(2020), no. 3, 1041–1067. MR4111934.CrossRefGoogle Scholar
Parvardi, A., Various problems on subproducts of residue classes modulo a prime. Master’s thesis, University of British Columbia, 2019.Google Scholar
Pollack, P., The average least quadratic nonresidue modulo m and other variations on a theme of Erdos . J. Number Theory 132(2012), no. 6, 1185–1202.10.1016/j.jnt.2011.12.015CrossRefGoogle Scholar