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

In the present paper we obtain new upper bound estimates for the number of solutions of the congruence $$ x\equiv y r\pmod p;\quad x,y\in \mathbb{N},\quad x,y\le H,\quad r\in\cU, $$ for certain ranges of $H$ and $|\cU|$, where $\cU$ is a subset of the field of residue classes modulo $p$ having small multiplicative doubling. We then use this estimate to show that the number of solutions of the congruence $$ x^n\equiv \lambda\pmod p; \quad x\in \N, \quad L 0$. This implies, in particular, that if $f(x)\in \Z[x]$ is a fixed polynomial without multiple roots in $\C$, then the congruence $ x^{f(x)}\equiv 1\pmod p, \,x\in \mathbb{N}, \,x\le p,$ has at most $p^{\frac{1}{3}-c}$ solutions as $p\to\infty$, 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 \pmod p$ with positive integers $xmodulo $p$. We also prove that almost all the residue classes modulo $p$ can be represented in the form $xyzg^t \pmod p$ with positive integers $x,y,z,t

Keywords:

• Algebra
• Residue (complex analysis)
• Mathematical analysis
• Prime (order theory)
• Primitive root modulo n
• Multiplicative function
• Upper and lower bounds
• Mathematics
• Congruence relation
• Integer
• Polynomial
• Discrete mathematics
• Combinatorics
• Modulo
• Lambda

• Correction
• Source
• Cite
• Save
• Machine Reading By IdeaReader