Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-05T23:28:44.972Z Has data issue: false hasContentIssue false
  • English
  • Français

Congruences involving product of intervals and sets with small multiplicative doubling modulo a prime and applications

Published online by Cambridge University Press:  14 January 2016

J. CILLERUELO  and
M. Z. GARAEV
J. CILLERUELO
Affiliation:
Instituto de Ciencias Matemáticas (CSIC-UAM-UC3M-UCM) and Departamento de Matemáticas, Universidad Autónoma de Madrid, Madrid-28049, Spain. e-mail: [email protected]
M. Z. GARAEV
Affiliation:
Centro de Ciencias Matemáticas, Universidad Nacional Autónoma de México, Campus Morelia, C.P. 58089, Morelia, Michoacán, México. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we obtain new upper bound estimates for the number of solutions of the congruence

$$\begin{equation} x\equiv y r\pmod p;\quad x,y\in \mathbb{N},\quad x,y\le H,\quad r\in \mathcal{U}, \end{equation}$$
for certain ranges of H and |${\mathcal U}$|, where ${\mathcal U}$ is a subset of the field of residue classes modulo p having small multiplicative doubling. We then use these estimates to show that the number of solutions of the congruence
$$\begin{equation} x^n\equiv \lambda\pmod p; \quad x\in \mathbb{N}, \quad L<x<L+p/n, \end{equation}$$
 is at most $p^{\frac{1}{3}-c}$ uniformly over positive integers n, λ and L, for some absolute constant c > 0. This implies, in particular, that if f(x) ∈ $\mathbb{Z}$[x] is a fixed polynomial without multiple roots in $\mathbb{C}$, then the congruence xf(x) ≡ 1 (mod p), x ∈ $\mathbb{N}$, x ⩽ p, has at most $p^{\frac{1}{3}-c}$ solutions as p → ∞, improving some recent results of Kurlberg, Luca and Shparlinski and of Balog, Broughan and Shparlinski. We use our results to show that almost all the residue classes modulo p can be represented in the form xgy (mod p) with positive integers x < p5/8+ϵ and y < p3/8. Here g denotes a primitive root modulo p. We also prove that almost all the residue classes modulo p can be represented in the form xyzgt (mod p) with positive integers x, y, z, t < p1/4+ϵ.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 160 , Issue 3 , May 2016 , pp. 477 - 494
Copyright
Copyright © Cambridge Philosophical Society 2016 

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

REFERENCES

[1]Balog, A., Broughan, K. A. and Shparlinski, I. E.On the number of solutions of exponential congruences. Acta Arith. 148 (2011), 93–103.Google Scholar
[2]Betke, U., Henk, M. and Wills, J. M.Successive-minima-type inequalities. Discr. Comput. Geom. 9 (1993), 165–175.Google Scholar
[3]Bourgain, J., Konyagin, S. V. and Shparlinski, I. E. Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm. Int. Math. Res. Not. (2008), Art. ID rnn 090, 29 pp.Google Scholar
[4]Bourgain, J., Garaev, M. Z., Konyagin, S. V. and Shparlinski, I. E.On congruences with products of variables from short intervals and applications. Proc. Steklov Inst. Math. 280 (2013), 61–90.Google Scholar
[5]Burgess, D. A.On character sums and L-series. Proc. London Math. Soc. 12 (1962), 193–206.Google Scholar
[6]Burgess, D. A.On character sums and L-series. II. Proc. London Math. Soc. 13 (1963), 524–536.Google Scholar
[7]Cilleruelo, J. A note on product sets of fractions. Int. J. Number Theory. (to appear).Google Scholar
[8]Cilleruelo, J. and Garaev, M. Z.Least totients in arithmetic progressions. Proc. Amer. Math. Soc. 137 (2009), 2913–2919.Google Scholar
[9]Garaev, M. Z.A note on the least totient of a residue class. Quart. J. Math. 60 (2009), 53–56.Google Scholar
[10]Garaev, M. Z.On multiplicative congruences. Math. Zeitschrift. 272 (2012), 473–482.Google Scholar
[11]Garaev, M. Z. and Karatsuba, A. A.On character sums and the exceptional set of a congruence problema. J. Number Theory. 114 (2005), 182–192.Google Scholar
[12]Garaev, M. Z. and Karatsuba, A. A.The representation of residue classes by products of small integers. Proc. Edinburgh Math. Soc. 50 (2007), 363–375.Google Scholar
[13]Heath-Brown, D. R.The divisor function d 3(n) in an arithmetic progressions. Acta Arith. 47 (1986), 29–56.Google Scholar
[14]Huxley, M. N.A note on polynomial congruences. Recent progress in analytic number theory, Vol. 1 (Durham, 1979) (Academic Press, London-New York), 1981, 193–196.Google Scholar
[15]Konyagin, S. V. Estimates for trigonometric sums over subgroups and for Gauss sums. (Russian) IV International Conference ‘Modern Problems of Number Theory and its Applications’: part III (2002), 86–114.Google Scholar
[16]Konyagin, S. V. and Shparlinski, I. E.Character Sums with Exponential Functions and Their Applications (Cambridge University Press, Cambridge, 1999).Google Scholar
[17]Kurlberg, P., Luca, F. and Shparlinski, I. E.On the fixed points of the map x → xx modulo a prime. Math. Res. Letters. 22 (2015), 141–168.Google Scholar
[18]Montgomery, H. L.Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis (Amer. Math. Soc., Providence, RI, 1994).Google Scholar
[19]Nathanson, M. B.Additive number theory. Inverse problems and the geometry of sumsets. Grad. Texts in Math. Vol 165 (Springer-Verlag, New York 1996), 293 pp.Google Scholar
[20]Shkredov, I.Some new inequalities in additive combinatorics. Mosc. J. Comb. Number Theory. 3 (2011), 237–288.Google Scholar
[21]Shteinokov, Yu. N.Estimates of trigonometric sums over subgroups and some of their applications. Math. Notes 98 (2015), 667–684. Translated from Mat. Zametki 98 (2015), 606–625.Google Scholar
[22]Vinogradov, I. M.On the distribution of indices. Doklady Akad. Nauk SSSR. 20 (1926), 73–76 (in Russian).Google Scholar
[23]Vinogradov, I. M.An Introduction to the Theory of Numbers (Pergamon Press, London & New York, 1955).Google Scholar