Type: Article

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

Cilleruelo, J; Garaev, M. Z.;

Abstract:

In this paper we obtain new upper bound estimates for the number of solutions of the congruence x equivalent to yr (mod p); x, y is an element of N, x, y <= H, r is an element of u, for certain ranges of H and vertical bar U vertical bar, where 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 x(n) equivalent to lambda (mod p); x is an element of N, L < x < L + p/n, is at most p(1/3-c) uniformly over positive integers n, lambda and L, for some absolute constant c > 0. This implies, in particular, that if f (x) is an element of Z [x] is a fixed polynomial without multiple roots in C, then the congruence x(f(x)) equivalent to 1 (mod p), x is an element of N, x <= p, has at most p(1/3-c) solutions as p -> infinity, 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 xg(y) (mod p) with positive integers x < p(5/8+epsilon) and y < p(3/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 xyzg(t) (mod p) with positive integers x, y, z, t < p(1/4+)epsilon.